1、按照先序遍历的顺序创建一个二叉链表； 2、对已建立的二叉树实现先序遍历、中序遍历、后序遍历、求深度、求结点数量等操作。 3、最好用菜单形式对应各个操作，使其编程一个完整的小软件。

### 实验任务概述 #### 1. 创建二叉链表 - **任务**: 按照先序遍历的顺序创建一个二叉链表。 - **示例输入**: `ABC##DE#G##F###` - **示例输出**: - 先序遍历: `ABCDEGF` - 中序遍历: `CBEGDFA` - 后序遍历: `CGEFDBA` #### 2. 实现二叉树的各种操作 - **先序遍历**: 遍历顺序为根节点 -> 左子树 -> 右子树。 - **中序遍历**: 遍历顺序为左子树 -> 根节点 -> 右子树。 - **后序遍历**: 遍历顺序为左子树 -> 右子树 -> 根节点。 - **求深度**: 计算二叉树的最大深度。 - **求结点数量**: 统计二叉树中的所有结点数。 - **销毁二叉树**: 释放二叉树占用的所有内存，并在销毁后进行任何操作时提示“二叉树未创建”。 #### 3. 设计菜单驱动程序 - **功能**: 使用菜单形式提供上述各种操作，使其成为一个完整的交互式小软件。 - **参考界面**: ``` ***********系统菜单************ 1. 创建二叉树 2. 先序遍历 3. 中序遍历 4. 后序遍历 5. 求二叉树的深度 6. 求二叉树结点数量 7. 销毁二叉树 ******************************* 请输入操作代码: ``` ### 示例代码框架 ```c #include <stdio.h> #include <stdlib.h> typedef struct TreeNode { char data; struct TreeNode *left; struct TreeNode *right; } TreeNode; TreeNode* createBinaryTree(char *preorder); void preOrderTraversal(TreeNode *root); void inOrderTraversal(TreeNode *root); void postOrderTraversal(TreeNode *root); int treeDepth(TreeNode *root); int countNodes(TreeNode *root); void destroyTree(TreeNode *root); int main() { char preorder[] = "ABC##DE#G##F###"; TreeNode *root = NULL; int choice; while (1) { printf("***********系统菜单************\n"); printf("1. 创建二叉树\n"); printf("2. 先序遍历\n"); printf("3. 中序遍历\n"); printf("4. 后序遍历\n"); printf("5. 求二叉树的深度\n"); printf("6. 求二叉树结点数量\n"); printf("7. 销毁二叉树\n"); printf("*******************************\n"); printf("请输入操作代码: "); scanf("%d", &choice); switch (choice) { case 1: root = createBinaryTree(preorder); break; case 2: if (root != NULL) { preOrderTraversal(root); printf("\n"); } else { printf("二叉树未创建。\n"); } break; case 3: if (root != NULL) { inOrderTraversal(root); printf("\n"); } else { printf("二叉树未创建。\n"); } break; case 4: if (root != NULL) { postOrderTraversal(root); printf("\n"); } else { printf("二叉树未创建。\n"); } break; case 5: if (root != NULL) { printf("深度为 %d\n", treeDepth(root)); } else { printf("二叉树未创建。\n"); } break; case 6: if (root != NULL) { printf("结点数量为 %d\n", countNodes(root)); } else { printf("二叉树未创建。\n"); } break; case 7: if (root != NULL) { destroyTree(root); root = NULL; printf("二叉树已销毁。\n"); } else { printf("二叉树未创建。\n"); } break; default: printf("无效的操作代码，请重新输入。\n"); } } return 0; } TreeNode* createBinaryTree(char *preorder) { static int index = 0; if (preorder[index] == '#' || preorder[index] == '\0') { index++; return NULL; } TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode)); node->data = preorder[index++]; node->left = createBinaryTree(preorder); node->right = createBinaryTree(preorder); return node; } void preOrderTraversal(TreeNode *root) { if (root != NULL) { printf("%c ", root->data); preOrderTraversal(root->left); preOrderTraversal(root->right); } } void inOrderTraversal(TreeNode *root) { if (root != NULL) { inOrderTraversal(root->left); printf("%c ", root->data); inOrderTraversal(root->right); } } void postOrderTraversal(TreeNode *root) { if (root != NULL) { postOrderTraversal(root->left); postOrderTraversal(root->right); printf("%c ", root->data); } } int treeDepth(TreeNode *root) { if (root == NULL) { return 0; } int leftDepth = treeDepth(root->left); int rightDepth = treeDepth(root->right); return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; } int countNodes(TreeNode *root) { if (root == NULL) { return 0; } return countNodes(root->left) + countNodes(root->right) + 1; } void destroyTree(TreeNode *root) { if (root != NULL) { destroyTree(root->left); destroyTree(root->right); free(root); } } ``` ### 注意事项 - **递归**: 在实现二叉树的遍历和深度计算时，使用递归方法可以简化代码。 - **内存管理**: 确保在销毁二叉树时正确释放所有分配的内存，避免内存泄漏。 - **输入验证**: 在实际应用中，应增加输入验证，确保输入格式正确。