用c++实现数据库二叉树的基本操作 1．数据域为字符的一棵二叉树用前序遍历方式输入，创建一个采用二叉链 表存储的二叉树，并按广义表的形式输出这棵二叉树。 2．在1的基础上完成这棵二叉树的中序遍历的递归算法。 3．求二叉树的高度。 4．求二叉树的叶子个数。

在C++中，我们可以使用结构体（struct）来表示二叉树节点，并结合指针来实现基本的操作。首先，我们定义一个`Node`结构，包含字符数据和左右子节点：

struct Node {
    char data;
    Node* left;
    Node* right;
};

### 1. 创建二叉树并前序遍历输出

void insert(Node** root, char value) {
    if (*root == nullptr) {
        *root = new Node{value, nullptr, nullptr};
    } else if (value < (*root)->data) {
        insert(&(*root)->left, value);
    } else {
        insert(&(*root)->right, value);
    }
}

void preorderTraversal(Node* root, std::vector<char>& output) {
    if (root != nullptr) {
        output.push_back(root->data);
        preorderTraversal(root->left, output);
        preorderTraversal(root->right, output);
    }
}

前序遍历时，先访问根节点，然后递归地遍历左子树和右子树。

### 2. 中序遍历递归算法

void inorderTraversal(Node* root, std::vector<char>& output) {
    if (root != nullptr) {
        inorderTraversal(root->left, output);
        output.push_back(root->data);
        inorderTraversal(root->right, output);
    }
}

中序遍历则是先遍历左子树，然后访问根节点，最后遍历右子树。

### 3. 求二叉树高度

int height(Node* root) {
    if (root == nullptr) return 0;
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return std::max(leftHeight, rightHeight) + 1;
}

通过递归计算左子树和右子树的最大高度加1得到整个树的高度。

### 4. 求二叉树的叶子节点个数

int countLeaves(Node* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1; // 叶子节点条件
    return countLeaves(root->left) + countLeaves(root->right);
}

如果当前节点无左右子节点，则是叶子节点，返回1；否则分别递归计数。