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

在C++中，我们可以按照以下步骤来实现这些功能：

1. **创建二叉链表并前序遍历输入**
- 定义`Node`结构体，包含一个字符`data`、左右指针`left`和`right`。
- 创建一个前序遍历函数`buildTree(char data[], int start, int end)`，它接受一个字符数组、起始和结束索引，构建一个二叉树。
- 通过遍历数组，每次插入当前元素作为根节点，并递归地对左子树和右子树进行相同操作。

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

Node* buildTree(char data[], int start, int end) {
    if (start > end)
        return nullptr;
    Node* root = new Node{data[start], nullptr, nullptr};
    int mid = findMiddle(start, end);
    root->left = buildTree(data, start + 1, mid);
    root->right = buildTree(data, mid + 1, end);
    return root;
}

**前序遍历输出：**

void printPreOrder(Node* root) {
    if (root != nullptr) {
        cout << root->data; // 输出根节点
        printPreOrder(root->left); // 遍历左子树
        printPreOrder(root->right); // 遍历右子树
    }
}

2. **中序遍历递归算法**
- 中序遍历的递归函数`inorderTraversal(Node* root)`：

   void inorderTraversal(Node* root) {
       if (root != nullptr) {
           inorderTraversal(root->left);
           cout << root->data; // 输出根节点
           inorderTraversal(root->right);
       }
   }

3. **计算二叉树高度（递归）**
- 可以编写一个`height`函数，递归计算树的高度，最简单的方式是从叶子开始计数每个层级直到根节点。

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

4. **计算二叉树的叶子数（递归）**
- 计算叶子节点的数量，当节点没有子节点时才是叶子。

   int countLeaves(Node* root) {
       if (root == nullptr)
           return 0;
       else if (root->left == nullptr && root->right == nullptr)
           return 1;
       else
           return countLeaves(root->left) + countLeaves(root->right);
   }