算法与数据结构，二叉树求解

4.关键字按顺序输入，输入序列为（zero,one,two,three,four,five,six,seven,eight,nine)。请通过比较字符串大小，完成二叉排序树的创建。并求出该树的度，分支结点，和内部结点。

以下是C++代码实现：

#include <iostream>
#include <string>

using namespace std;

// 二叉搜索树节点定义
struct BinarySearchTree {
    string data;
    BinarySearchTree* left;
    BinarySearchTree* right;
};

// 创建二叉搜索树
BinarySearchTree* createSearchTree(string arr[], int n) {
    BinarySearchTree* root = NULL;
    for (int i = 0; i < n; i++) {
        BinarySearchTree* node = new BinarySearchTree;
        node->data = arr[i];
        node->left = NULL;
        node->right = NULL;
        if (root == NULL) {
            root = node;
        } else {
            BinarySearchTree* cur = root;
            while (cur != NULL) {
                if (node->data < cur->data) {
                    if (cur->left == NULL) {
                        cur->left = node;
                        break;
                    } else {
                        cur = cur->left;
                    }
                } else {
                    if (cur->right == NULL) {
                        cur->right = node;
                        break;
                    } else {
                        cur = cur->right;
                    }
                }
            }
        }
    }
    return root;
}

// 计算度、分支结点和内部结点的数量
void calculate(BinarySearchTree* root, int& degree, int& branch, int& internal) {
    if (root == NULL) {
        return;
    }
    if (root->left != NULL && root->right != NULL) {
        degree = 2;
        branch++;
        internal++;
        calculate(root->left, degree, branch, internal);
        calculate(root->right, degree, branch, internal);
    } else if (root->left != NULL) {
        degree = 1;
        branch++;
        internal++;
        calculate(root->left, degree, branch, internal);
    } else if (root->right != NULL) {
        degree = 1;
        branch++;
        internal++;
        calculate(root->right, degree, branch, internal);
    } else {
        degree = 0;
        internal++;
    }
}

int main() {
    string arr[] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    int n = sizeof(arr) / sizeof(arr[0]);

    BinarySearchTree* root = createSearchTree(arr, n);

    int degree = 0;
    int branch = 0;
    int internal = 0;
    calculate(root, degree, branch, internal);

    cout << "Degree: " << degree << endl;
    cout << "Branch nodes: " << branch << endl;
    cout << "Internal nodes: " << internal << endl;

    return 0;
}

该程序创建了一个二叉搜索树，节点中存储了输入的关键字。通过字符串的比较，每个关键字会被插入到正确的位置上。然后，通过递归遍历二叉树，计算树的度、分支结点和内部结点的数量。