假设二叉树采用二叉链存储结构，二叉树中结点值为单个字符（如'a','b',...）且所有结点值不同。设计二叉树的基本运算程序。 （1）创建一棵二叉树； （2）输出一棵二叉树；

（1）创建一棵二叉树的基本运算程序可以按照以下步骤进行：

1. 定义二叉树的结点结构，包括结点值和左右子树指针。
2. 创建一个空的二叉树根节点。
3. 输入二叉树的结点值，以某个特定值（如'#'）表示空结点。
4. 根据输入的结点值构建二叉树，可以使用递归或循环方式。
- 如果输入的结点值为特定值，则将应的子树指针置为空。
- 如果输入的结点值不为空，则创建一个新的结点，并将其值赋给新结点，然后归创建左右子树。
5. 返回创建好的二叉树。

（2）输出一棵二叉树的基本运算程序可以按照以下步骤进行：

1. 判断当前结点是否为空，如果为空则返回。
2. 输出当前结点的值。
3. 递归输出左子树。
4. 递归输出右子树。

相关问题

假设二叉树采用二叉链存储结构，二叉树中结点值为单个字符（如'a','b',...）且所有结点值不同。设计二叉树的基本运算程序。 （1）创建一棵二叉树； （2）输出一棵二叉树；

假设二叉树采用二叉链存储结构，我们可以设计以下基本运算程序：

1. 创建一棵二叉树：
- 创建一个空的根结点。
- 通过用户输入的方式逐个插入结点，构建二叉树。可以使用递归或循环方式实现。
- 每次插入结点时，需要判断插入的位置是左子树还是右子树。

2. 输出一棵二叉树：
- 可以使用递归方式进行中序遍历，输出二叉树的结点值。
- 具体步骤如下：
- 如果当前结点为空，则返回。
- 递归输出左子树。
- 输出当前结点的值。
- 递归输出右子树。

假设二叉树采用二叉链存储结构，二叉树中结点值为单个字符且所有结点值不相同，设计二叉树的基本运算程序，包括创建二叉链，输出二叉树求二叉树的高度，求结点数和叶子结点数；并用相关数据进行测试。

二叉树基本运算程序：

#include <iostream>
using namespace std;

// 二叉树结点
struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};

// 创建二叉树
void createBinaryTree(TreeNode*& root) {
    char val;
    cin >> val;
    if (val == '#') {
        root = NULL;
    } else {
        root = new TreeNode(val);
        createBinaryTree(root->left);
        createBinaryTree(root->right);
    }
}

// 输出二叉树
void printBinaryTree(TreeNode* root, int depth) {
    if (root == NULL) {
        return;
    }
    printBinaryTree(root->right, depth+1);
    for (int i = 0; i < depth; i++) {
        cout << "  ";
    }
    cout << root->val << endl;
    printBinaryTree(root->left, depth+1);
}

// 求二叉树高度
int getHeight(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);
    return max(leftHeight, rightHeight) + 1;
}

// 求二叉树结点数
int getNodeNum(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    return getNodeNum(root->left) + getNodeNum(root->right) + 1;
}

// 求二叉树叶子结点数
int getLeafNum(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return getLeafNum(root->left) + getLeafNum(root->right);
}

int main() {
    TreeNode* root;
    createBinaryTree(root);
    printBinaryTree(root, 0);
    cout << "Height: " << getHeight(root) << endl;
    cout << "NodeNum: " << getNodeNum(root) << endl;
    cout << "LeafNum: " << getLeafNum(root) << endl;
    return 0;
}

测试数据：

输入：A B # C # # D E # # F G # # H # #

输出：

      H
        G
          F
A
          E
        D
          C
      B
Height: 4
NodeNum: 8
LeafNum: 4