C二叉树操作图解(建树,遍历,销毁)

后面有图解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <stdlib.h>
#define maxn 100
typedef char DataType; //定义数据类型

typedef struct BiNode
{
DataType data;
struct BiNode *Lchild,*Rchild;
} BiTree;

//前序遍历------顺序:根->左->右
void QPreOrder(BiNode *root)
{
if(root == NULL) return;
else
{
printf("%c ",root->data); //根
QPreOrder(root->Lchild); //左
QPreOrder(root->Rchild); //右

}
}

//后序遍历------:顺序:左->右->根
void HPreOrder(BiNode *root)
{
if(root == NULL) return;
else
{
HPreOrder(root->Lchild); //左
HPreOrder(root->Rchild); //右
printf("%c ",root->data); //根

}
}
//中序遍历------顺序:左->根->右
void ZPreOrder(BiNode *root)
{
if(root == NULL) return;
else
{
ZPreOrder(root->Lchild); //左
printf("%c ",root->data); //根
ZPreOrder(root->Rchild); //右

}
}

//建树
BiNode *CreatBiTree(BiNode *root)
{
char chr;
scanf("%c",&chr);
if(chr == '#') root = NULL;//遇到#说明孩子为NULL,返回上一结点
else{
root = (BiNode *)malloc(sizeof(BiNode));
root->data = chr;
root->Lchild = CreatBiTree(root->Lchild); //从左至右建树
root->Rchild = CreatBiTree(root->Rchild);
}
return root;
}

//销毁树
void DesTree(BiNode *root)
{
if(root == NULL) return ;
DesTree(root->Lchild);
DesTree(root->Rchild);
free(root); //从最右依次free至根节点
}
int main()
{
BiNode *root = NULL;
root = CreatBiTree(root);
printf("前序遍历结果:\n");
QPreOrder(root);
printf("\n");
printf("中序遍历结果:\n");
ZPreOrder(root);
printf("\n");
printf("后序遍历结果:\n");
HPreOrder(root);
printf("\n");
return 0;
}

比如说,我要构造下图的二叉树 那么我们的输入应该是:

ABDG##H###CE#I##F##

解析: 从A->G:未遇见特殊字符’#’,依次建立左子树. G->H:G后读入特殊字符’#’,则G左孩子为空; 继续读入下一个字符; 依然是’#’,则G右孩子为空. 此时G左右孩子已输入,返回上一层D. 读入字符’H’写入D右孩子. 其他的以此类推即可 关于遍历: 依照上图

前序遍历结果:

A B D G H C E I F

中序遍历结果:

G D H B A E I C F

后序遍历结果:

G H D B I E F C A

觉得文章不错的话可以请我喝一杯茶哟~
  • 本文作者: bestsort
  • 本文链接: https://bestsort.cn/2019/04/21/66/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-SA 许可协议。转载请注明出处!并保留本声明。感谢您的阅读和支持!
-------------本文结束感谢您的阅读-------------