使用链式存储结构定义二叉树的数据类型，编写程序实现以下功能： （1） 创建一个二叉树（输入二叉树的前序序列，空节点用#表示。示例ABC##D#E##F##）； （2） 二叉树的先序递归遍历； （3） 二叉树的中序递归遍历； （4） 二叉树的后序递归遍历； （5） 计算二叉树的深度； （6） 统计二叉树中的结点的个数； （7） 在二叉树中查找值为x的节点； 效果截图： 程序代码：

#include<iostream>
#include<string>
using namespace std;

// 二叉树的结点定义
struct BinaryTreeNode {
    char ch; // 结点的值
    BinaryTreeNode* left; // 左子树
    BinaryTreeNode* right; // 右子树
};

// 创建二叉树
BinaryTreeNode* createBinaryTree(string& s, int& index) {
    if (index >= s.length()) return NULL;
    if (s[index] == '#') {
        index++;
        return NULL;
    }
    BinaryTreeNode* root = new BinaryTreeNode;
    root->ch = s[index++];
    root->left = createBinaryTree(s, index);
    root->right = createBinaryTree(s, index);
    return root;
}

// 先序遍历
void preOrderTraversal(BinaryTreeNode* root) {
    if (root == NULL) return;
    cout << root->ch << " ";
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

// 中序遍历
void inOrderTraversal(BinaryTreeNode* root) {
    if (root == NULL) return;
    inOrderTraversal(root->left);
    cout << root->ch << " ";
    inOrderTraversal(root->right);
}

// 后序遍历
void postOrderTraversal(BinaryTreeNode* root) {
    if (root == NULL) return;
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    cout << root->ch << " ";
}

// 计算树的深度
int treeDepth(BinaryTreeNode* root) {
    if (root == NULL) return 0;
    int leftDepth = treeDepth(root->left);
    int rightDepth = treeDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

// 统计结点个数
int countNodes(BinaryTreeNode* root) {
    if (root == NULL) return 0;
    int leftCount = countNodes(root->left);
    int rightCount = countNodes(root->right);
    return leftCount + rightCount + 1;
}

// 查找值为x的结点
BinaryTreeNode* findNode(BinaryTreeNode* root, char x) {
    if (root == NULL) return NULL;
    if (root->ch == x) return root;
    BinaryTreeNode* leftNode = findNode(root->left, x);
    if (leftNode != NULL) return leftNode;
    BinaryTreeNode* rightNode = findNode(root->right, x);
    if (rightNode != NULL) return rightNode;
    return NULL;
}

int main() {
    string s = "ABC##D#E##F##";
    int index = 0;
    BinaryTreeNode* root = createBinaryTree(s, index);

    cout << "先序遍历：";
    preOrderTraversal(root);
    cout << endl;

    cout << "中序遍历：";
    inOrderTraversal(root);
    cout << endl;

    cout << "后序遍历：";
    postOrderTraversal(root);
    cout << endl;

    cout << "树的深度：" << treeDepth(root) << endl;

    cout << "结点个数：" << countNodes(root) << endl;

    cout << "查找结点值为D的结点：" << findNode(root, 'D')->ch << endl;

    return 0;
}