(1)编写二叉树的基本操作函数。 ①创建一棵二叉树 CreateBiTree(BiTree *T); ②先序遍历,递归方法 re_PreOrder(BiTree * tree ) ③中序遍历,递归方法 re_MidOrder(BiTree * tree ) ④后序遍历,递归方法 re_PostOrder(BiTree * tree ) (2)调用上述函数实现下列操作。 用递归方法分别先序、中序和后序遍历二叉树; 注意 要求动态显示二叉树的建立过程。
时间: 2024-02-13 18:03:00 浏览: 76
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
5星 · 资源好评率100%
以下是一个基于C语言的二叉树实现,包括创建二叉树和三种遍历方式的递归实现。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
// 创建二叉树
void CreateBiTree(BiTree *T) {
int ch;
scanf("%d", &ch);
if (ch == -1) {
*T = NULL;
}
else {
*T = (BiTree)malloc(sizeof(BiTNode));
if (!*T) {
printf("内存分配失败!\n");
exit(0);
}
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
// 先序遍历
void re_PreOrder(BiTree tree) {
if (tree) {
printf("%d ", tree->data);
re_PreOrder(tree->lchild);
re_PreOrder(tree->rchild);
}
}
// 中序遍历
void re_MidOrder(BiTree tree) {
if (tree) {
re_MidOrder(tree->lchild);
printf("%d ", tree->data);
re_MidOrder(tree->rchild);
}
}
// 后序遍历
void re_PostOrder(BiTree tree) {
if (tree) {
re_PostOrder(tree->lchild);
re_PostOrder(tree->rchild);
printf("%d ", tree->data);
}
}
int main() {
BiTree T = NULL;
printf("请输入二叉树的结点数据(-1表示空结点):\n");
CreateBiTree(&T);
printf("\n先序遍历:");
re_PreOrder(T);
printf("\n中序遍历:");
re_MidOrder(T);
printf("\n后序遍历:");
re_PostOrder(T);
return 0;
}
```
在上述代码中,CreateBiTree函数用于创建二叉树,re_PreOrder、re_MidOrder和re_PostOrder分别是先序、中序和后序遍历的递归实现。在主函数中,首先调用CreateBiTree函数创建二叉树,然后依次调用三种遍历函数输出结果。
需要注意的是,上述代码没有实现动态显示二叉树的建立过程,如果需要实现该功能,可以在CreateBiTree函数中添加相应的输出语句。
阅读全文