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

在C++中，我们可以使用结构体表示二叉树节点，每个节点包含一个字符数据域以及指向左右子节点的指针。以下是实现这一功能的基本步骤：

1. **二叉树节点结构体**:

struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char ch) : data(ch), left(nullptr), right(nullptr) {}
};

2. **前序遍历输入并构建二叉树**:
前序遍历通常是根节点 -> 左子树 -> 右子树。可以用递归的方式实现：

void buildTree(TreeNode*& root, const std::string& str, int start = 0) {
    if (start >= str.length()) return;
    root = new TreeNode(str[start]);
    start++;
    buildTree(root->left, str, start);
    buildTree(root->right, str, start);
}

这里假设`str`是以空格分隔的字符串，代表前序遍历的序列。

3. **广义表形式输出**:
前序遍历的广义表输出可以按照“当前节点 -> 左子树 -> 右子树”的顺序打印：

void printPreorder(TreeNode* root) {
    if (root != nullptr) {
        std::cout << root->data;
        printPreorder(root->left);
        printPreorder(root->right);
    }
}

4. **中序遍历递归算法**:
中序遍历是左子树 -> 根节点 -> 右子树，同样用递归实现：

void printInOrder(TreeNode* root) {
    if (root != nullptr) {
        printInOrder(root->left);
        std::cout << root->data;
        printInOrder(root->right);
    }
}

5. **计算二叉树高度**:
使用递归方法计算最大深度（高度）：

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

6. **计算叶子节点个数**:
叶子节点是没有子节点的节点，递归计数即可：

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