请编制C程序,利用二叉树的链式存储方式实现以下功能,二叉树的建立、先序、中序、后序和层次遍历、求二叉树的深度等操作。 要求: (1)根据屏幕菜单的选择,进行二叉树的建立、先序、中序、后序和层次遍历、求二叉树的深度;最后在屏幕菜单中选择0,即可结束程序的运行。 (2)二叉树中存储的数据在键盘上输入,栈中存储的数据类型定义为字符型char,先序、中序、后序和层次遍历后要输出相应结点值,求二叉树深度后要输出深度的值。 (3)遍历算法可以用递归函数实现,也可以用非递归,每个算法前要给出适当的注释说明,程序中相应的位置加入输入输出提示语句。 源代码
时间: 2024-02-27 13:55:30 浏览: 59
很抱歉,由于时间和版权的限制,我无法在此处提供完整的源代码。但是,以下是一个简单的二叉树的链式存储的示例代码,包括二叉树的创建、先序遍历、中序遍历、后序遍历、层次遍历和求二叉树深度的功能。你可以根据这个示例代码来编写你自己的程序。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建二叉树
TreeNode *createBinaryTree() {
char data;
TreeNode *node;
scanf("%c", &data);
if (data == '#') {
node = NULL;
} else {
node = (TreeNode *)malloc(sizeof(TreeNode));
node->data = data;
node->left = createBinaryTree();
node->right = createBinaryTree();
}
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);
}
}
// 层次遍历二叉树
void levelOrderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
TreeNode *queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
TreeNode *node = queue[front++];
printf("%c ", node->data);
if (node->left != NULL) {
queue[rear++] = node->left;
}
if (node->right != NULL) {
queue[rear++] = node->right;
}
}
}
// 求二叉树深度
int getDepth(TreeNode *root) {
if (root == NULL) {
return 0;
}
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
int main() {
int choice;
TreeNode *root = NULL;
printf("请选择操作:\n");
printf("1. 创建二叉树\n");
printf("2. 先序遍历\n");
printf("3. 中序遍历\n");
printf("4. 后序遍历\n");
printf("5. 层次遍历\n");
printf("6. 求二叉树深度\n");
printf("0. 退出\n");
do {
printf("请输入选择:");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("请输入二叉树的先序遍历序列:");
getchar();
root = createBinaryTree();
break;
case 2:
printf("先序遍历序列为:");
preOrderTraversal(root);
printf("\n");
break;
case 3:
printf("中序遍历序列为:");
inOrderTraversal(root);
printf("\n");
break;
case 4:
printf("后序遍历序列为:");
postOrderTraversal(root);
printf("\n");
break;
case 5:
printf("层次遍历序列为:");
levelOrderTraversal(root);
printf("\n");
break;
case 6:
printf("二叉树的深度为:%d\n", getDepth(root));
break;
case 0:
printf("程序已退出!\n");
break;
default:
printf("输入有误,请重新输入!\n");
break;
}
} while (choice != 0);
return 0;
}
```
阅读全文