帮我编写一个二叉树的基本操作程序。要求:(1)写出二叉树的数据类型定义(2)编写二叉树的基本操作函数 CreateBiTree(BiTree *T);(3)先序遍历,递归方法 re_PreOrder(BiTree *tree);(4)中序遍历,递归方法 re_MidOrder(BiTree *tree);(5)后序遍历,递归方法 re_PostOrder(BiTree *tree),在完成这几个函数的编程后,在主程序中分别用先序、中序、后序遍历二叉树,要求动态显示二叉树的建立过程 程序用C语言编程
时间: 2024-01-22 18:20:46 浏览: 65
二叉树的数据类型定义如下:
```c
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
```
其中,`data` 是节点存储的数据,`lchild` 和 `rchild` 分别是该节点的左子树和右子树。
二叉树的基本操作函数 `CreateBiTree(BiTree *T)` 可以按照先序遍历的方式输入二叉树的节点数据,如果该节点不存在,则输入一个特定的字符(例如 `#`)表示该节点为空。具体代码如下:
```c
void CreateBiTree(BiTree *T) {
char ch;
scanf("%c", &ch);
if (ch == '#') {
*T = NULL;
} else {
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = ch;
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
}
```
先序遍历的递归方法 `re_PreOrder(BiTree *tree)` 可以按照先访问根节点、再遍历左子树、最后遍历右子树的顺序,输出二叉树的节点数据。具体代码如下:
```c
void re_PreOrder(BiTree tree) {
if (tree) {
printf("%c ", tree->data);
re_PreOrder(tree->lchild);
re_PreOrder(tree->rchild);
}
}
```
中序遍历的递归方法 `re_MidOrder(BiTree *tree)` 可以按照先遍历左子树、再访问根节点、最后遍历右子树的顺序,输出二叉树的节点数据。具体代码如下:
```c
void re_MidOrder(BiTree tree) {
if (tree) {
re_MidOrder(tree->lchild);
printf("%c ", tree->data);
re_MidOrder(tree->rchild);
}
}
```
后序遍历的递归方法 `re_PostOrder(BiTree *tree)` 可以按照先遍历左子树、再遍历右子树、最后访问根节点的顺序,输出二叉树的节点数据。具体代码如下:
```c
void re_PostOrder(BiTree tree) {
if (tree) {
re_PostOrder(tree->lchild);
re_PostOrder(tree->rchild);
printf("%c ", tree->data);
}
}
```
最后,在主程序中可以先调用 `CreateBiTree` 函数创建二叉树,再依次调用 `re_PreOrder`、`re_MidOrder` 和 `re_PostOrder` 函数进行遍历,并动态显示二叉树的建立过程。具体代码如下:
```c
int main() {
BiTree T;
printf("请按先序遍历的方式输入二叉树的节点数据,用 # 表示空节点:\n");
CreateBiTree(&T);
printf("先序遍历结果:\n");
re_PreOrder(T);
printf("\n中序遍历结果:\n");
re_MidOrder(T);
printf("\n后序遍历结果:\n");
re_PostOrder(T);
return 0;
}
```
阅读全文