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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
| #include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char TElemType;
typedef struct BiTNode
//--------------------------------------------------------------------------------------------------------------
//二叉树的顺序存储结构
/*
完全二叉树：
存储的基础：
1，对于一个从上到下，从左到右的编号的完全二叉树
假设他的结点为2m,或者2m+1,则它的双亲结点为m.
2，同理，如果结点为2m。那么根据计算可以知道
他的子结点是{
1),左节点，4m,
2)，右结点,4m+1
}
这样很简单，无需附加信息
//--------------------------------------------------------------------------------------------------------------------------------
普通的二叉树
这时候比较麻烦，无法单独仅仅存储它本身
这时候可以补全它的结点，使得它为完全二叉树，这样的结点为xu'jie'dian
虚结点的值为空。
*/
#define MAX_TREE_SIZE 100 //二叉树的最大结点数
typedef int SqBiTree[MAX_TREE_SIZE]; //这里把树的结点数据类型简单的存储为int类型 int == TreeElementType
SqBiTree bt; //
//从小标为0的结点开始存储树的根节点，将值为为#的结点记作空结点，但是这样仍然很难记录结点之间的关系
//如此这样存储，对于比较空的二叉树，空间利用率太小了
//----------------------------------------------------------------
//二叉和三叉都行
//二叉链表表示法的实现，显然二叉的空间利用率更好
/*
对于n个结点，有2n个指针域，那么就有n-1，个分支，就有n-1个非空指针域，就有n+1个空的指针域
*/
//C语言实现
typedef struct BiTNode
{
TElemType data;
BiTNode *lchild, *rchild; //指向左右的孩子,当某结点不存在左右孩子的时候，其为空NULL
} BiTNode, *BiTNode;
//----------------------------------------------------------------
//二叉树的遍历，每个结点被访问一次
/*
可以记根节点为D,左子树为L,右子树为R
根据自左到右的遍历规则，那么有
DLR//先序遍历
LDR//中序遍历
LRD//后序遍历
*/
//先序遍历
void PreOrder(BiTNode bt)
{
if (bt) //只要树(子树)根节点不是空
{
printf("%c", bt->data); //输出根节点的值
PreOrder(bt->lchild); //左子树的值
PreOrder(bt->rchild); //右子树的值
}
} //递归定义，这里要注意理解输出的过程中的不断的递归
//中序遍历
void InOrder(BiTNode bt)
{
if (bt)
{
InOrder(bt->lchild); //先输出左子树
printf("%c", bt->data); //当左子树全部输出之后，再输出根节点的值
InOrder(bt->rchild); //输出右子树
}
} //这里的递归输出相对复杂，记得多理解一下
//后序遍历
void PostOrder(BiTNode bt)
{
if (bt)
{
PostOrder(bt->lchild); //输出左子树
PostOrder(bt->rchild); //右子树
printf("%c", bt->data); //跟结点
//其实这里的每一种遍历输出都是挺麻烦的，注意实践检验和验证
}
}
//----------------------------------------------------------------
//二叉树的递归算法设计
/*
例题一：
假设二叉树中所有的结点的值为整数，采用二叉链表存储结构，求该二叉树b中所有结点值之和
*/
int SUM(BiTNode *bt)
{
int sun;
if (bt)
{
sun = SUM(bt->rchild) + SUM(bt->lchild) + SUM(bt); //不为空，就连续递归，返回下一层的值
}
else
sun = 0; //如果结点为空，就返回0；
return sun;
}
//销毁二叉树
/*
分析：显然，这里不能先销毁根节点，所以只能是后序遍历的顺序了
*/
void DestroyBTree(BiTNode b)
{ //不要傻乎乎的以为这里只是销毁了两层结点，这是一个递归算法，只要是根结点的子树，都会被释放
if (b) //只要根结点不为空
{
DestroyBTree(b->lchild); //先销毁左子树
DestroyBTree(b->rchild); //然后是右子树
free(b); //最后销毁根结点
}
else
return;
}
//-----------------------------------------------------------------------------
//实例的解决，创建二叉树
/*
如果节点为空，就构造虚结点，从而满足二叉树*/
void CreateBiTree(BiTNode &T)
{
//线序排序,还是一个递归定义
TElemType ch;
printf("请输入结点的值");
scanf("%c", &ch);
if (ch == '#') //建立一个
T = NULL;
else
{
T = (BiTNode)malloc(sizeof(BiTNode));
if (!T)
exit(-1);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
//调用函数
int main()
{
BiTNode bt;
printf("\n创建二叉树，请输入结点的值：\n");
CreateBiTree(bt);
printf("\n先序遍历序列:\n");
PreOrder(bt);
printf("\n后序遍历:\n");
PostOrder(bt);
printf("\n");
}
//求二叉树的高度
int bt_Height(BiTNode *bt)
{
if (bt = NULL)
{
return 0;
}
else
{
if (bt->lchild == NULL && bt->rchild == NULL)
return 1;
else
return 1 + max(bt_Height(bt->lchild), bt_Height(bt->rchild));
//或者利用return (hl>hr)?:hl+1:hr+1//也就是三目运算符
}
}
//求二叉树的叶子结点的个数
int LeafCount(BiTNode *T)
{
int lnum, rnum;
if (T == NULL)
return 0;
else if (T->lchild == NULL && T->rchild == NULL)
return 1;
else
{
lnum = LeafCount(T->lchild);
rnum = LeafCount(T->rchild);
return (lnum + rnum);
}
}
//交换二叉树的左右子树
/*
由于每个结点都是以链表的形式存储，所以实质上还是对指针的操作*/
int Exchange(BiTNode *T)
{
if (T != NULL) //出口
{
if (T->lchild != NULL || T->rchild != NULL)
{
BiTNode *s = T->lchild; //先设置一个指向左子树的指针
T->lchild = T->rchild; //交换左右子树的地址
T->rchild = s; //交换左右子树的地址
Exchange(T->lchild); //递归
Exchange(T->rchild); //递归
}
}
}
//计算单分支结点的个数
int DegreeOne(BiTNode *bt)
{
int lnum, rnum, n;
if (bt == NULL) //判断根节点是否为空
return 0;
else
{ //先判断树根是否为单分支结点
if ((b->lchild == NULL && b->rchild != NULL) || (b->lchild != NULL && b->rchild != NULL))
n = 1;
else
n = 0;
}
lnum = DegreeOne(bt->lchild); //递归
rnum = DegreeOne(bt->rchild); //递归
return (lnum + rnum + n);
}
//若每个结点存储的是一个单个的字符，求二叉树中最小值的结点
void FindMinNode(BiTNode *bt, char &min) //传地址就不用直接返回参数了
{
if (bt == NULL)
return NULL;
else
{
if (bt->data < min) //循环体
min = bt->data; //循环体
FindMinNode(bt->lchild, min); //递归调用
FindMaxNode(bt->rchild, min); //递归调用
}
}
|