二叉树的二叉链表表示与实现
分类:
IT文章
•
2022-07-19 22:58:53
http://blog.csdn.net/algorithm_only/article/details/6973848
前面几节讲到的结构都是一种线性的数据结构,今天要说到另外一种数据结构——树,其中二叉树最为常用。二叉树的特点是每个结点至多只有两棵子树,且二叉树有左右字子树之分,次序不能任意颠倒。
二叉树的存储结构可以用顺序存储和链式存储来存储。二叉树的顺序存储结构由一组连续的存储单元依次从上到下,从左到右存储完全二叉树的结点元素。对于一般二叉树,应将其与完全二叉树对应,然后给每个结点从1到i编上号,依次存储在大小为i-1的数组中。这种方法只适用于完全二叉树,对非完全二叉树会浪费较多空间,最坏情况一个深度为k的二叉树只有k个结点,却需要长度为2的k次方减一长度的一位数组。事实上,二叉树一般使用链式存储结构,由二叉树的定义可知,二叉树的结点由一个数据元素和分别指向其左右孩子的指针构成,即二叉树的链表结点中包含3个域,这种结点结构的二叉树存储结构称之为二叉链表。
typedef struct tnode {
elemtype data;
struct tnode *lchild;
struct tnode *rchild;
}*bitree, bitnode;
1 int create_bitree(bitree *bt)
2 {
3 elemtype data;
4
5 scanf("%d", &data);
6 if (0 == data) {
7 *bt = NULL;
8 } else {
9 *bt = (bitree)malloc(sizeof(bitnode));
10 if (!(*bt))
11 exit(OVERFLOW);
12 (*bt)->data = data;
13 create_bitree(&(*bt)->lchild);
14 create_bitree(&(*bt)->rchild);
15 }
16 return OK;
17 }
View Code
按先序次序输入二叉树的结点值,0表示空树。
1 void preorder(bitree bt, int (*visit)(elemtype e))
2 {
3 if (bt) {
4 visit(bt->data);
5 preorder(bt->lchild, visit);
6 preorder(bt->rchild, visit);
7 }
8 }
9
10
11 void inorder(bitree bt, int (*visit)(elemtype e))
12 {
13 if (bt) {
14 inorder(bt->lchild, visit);
15 visit(bt->data);
16 inorder(bt->rchild, visit);
17 }
18 }
19
20 void postorder(bitree bt, int (*visit)(elemtype e))
21 {
22 if (bt) {
23 postorder(bt->lchild, visit);
24 postorder(bt->rchild, visit);
25 visit(bt->data);
26 }
27 }
View Code
二叉树的递归算法较简单,代码简洁清晰,但递归算法效率低,执行速度慢,在下一节将说到二叉树非递归遍历算法。
1 int get_tree_depth(bitree bt)
2 {
3 int ldepth, rdepth;
4
5 if (!bt)
6 return 0;
7 else if (!bt->lchild && !bt->rchild)
8 return 1;
9 else {
10 ldepth = get_tree_depth(bt->lchild);
11 rdepth = get_tree_depth(bt->rchild);
12
13 return (ldepth > rdepth ? ldepth : rdepth) + 1;
14 }
15 }
View Code
树的深度即树的结点中最大层次,分别递归求左右子树的深度,较大子树深度为树的深度。
1 int get_num_of_leave(bitree bt)
2 {
3 if (!bt)
4 return 0;
5 else if (!bt->lchild && !bt->rchild)
6 return 1;
7 else
8 return (get_num_of_leave(bt->lchild) + get_num_of_leave(bt->rchild));
9 }
递归求左右子树的叶子数,左右子树的叶子结点之和为树的叶子结点数。
1 void free_bitree(bitree *bt)
2 {
3 if (*bt) {
4 if ((*bt)->lchild)
5 free_bitree(&(*bt)->lchild);
6 if ((*bt)->rchild)
7 free_bitree(&(*bt)->rchild);
8 free(*bt);
9 *bt = NULL;
10 }
11 }
全部实现:
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <string>
4 #include <string.h>
5 #include <iostream>
6 #include <vector>
7 #include <stack>
8 using namespace std;
9 #define debug(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
10 typedef char elemtype;
11 //二叉链表结构
12 typedef struct tnode {
13 elemtype data;
14 struct tnode *lchild;
15 struct tnode *rchild;
16 }*bitree, bitnode;
17
18 int create_bitree(bitree *bt)
19 {
20 elemtype data;
21 scanf("%c", &data);
22 if ('#' == data) {
23 *bt = NULL;
24 } else {
25 *bt = (bitree)malloc(sizeof(bitnode));
26 if (!(*bt))
27 perror("bt malloc");
28 (*bt)->data = data;
29 create_bitree(&(*bt)->lchild);
30 create_bitree(&(*bt)->rchild);
31 }
32 return 1;
33 }
34
35 void preorder(bitree bt, int (*visit)(elemtype e))
36 {
37 if (bt) {
38 visit(bt->data);
39 preorder(bt->lchild, visit);
40 preorder(bt->rchild, visit);
41 }
42 }
43
44
45 void inorder(bitree bt, int (*visit)(elemtype e))
46 {
47 if (bt) {
48 inorder(bt->lchild, visit);
49 visit(bt->data);
50 inorder(bt->rchild, visit);
51 }
52 }
53
54 void postorder(bitree bt, int (*visit)(elemtype e))
55 {
56 if (bt) {
57 postorder(bt->lchild, visit);
58 postorder(bt->rchild, visit);
59 visit(bt->data);
60 }
61 }
62
63 int print(elemtype e){
64 printf("%c", e);
65 return 1;
66 }
67
68 int get_tree_depth(bitree bt)
69 {
70 int ldepth, rdepth;
71
72 if (!bt)
73 return 0;
74 else if (!bt->lchild && !bt->rchild)
75 return 1;
76 else {
77 ldepth = get_tree_depth(bt->lchild);
78 rdepth = get_tree_depth(bt->rchild);
79
80 return (ldepth > rdepth ? ldepth : rdepth) + 1;
81 }
82 }
83
84 void free_bitree(bitree *bt)
85 {
86 if (*bt) {
87 if ((*bt)->lchild)
88 free_bitree(&(*bt)->lchild);
89 if ((*bt)->rchild)
90 free_bitree(&(*bt)->rchild);
91 free(*bt);
92 *bt = NULL;
93 }
94 }
95 typedef int (*func)(bitree bt);
96 int main(void) {
97 bitree bt;
98 create_bitree(&bt);
99 printf("pre:");
100 preorder(bt, print);
101 printf("
");
102 printf("in:");
103 inorder(bt, print);
104 printf("
");
105 printf("post:");
106 postorder(bt, print);
107 printf("
");
108 free_bitree(&bt);
109 return 0;
110 }
View Code
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <error.h>
4 #include <iostream>
5 #include <string>
6 #include <vector>
7 #include <stack>
8 #include <unistd.h>
9 #include <time.h>
10 using namespace std;
11 #define debug(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
12 typedef char elemtype;
13 typedef struct Bitree{
14 elemtype data;
15 struct Bitree *lchild;
16 struct Bitree *rchild;
17 }STBitree,*bitree;
18
19 vector<STBitree *>::iterator vbi;
20 vector<elemtype>::iterator vei;
21
22 //前序创建二叉树
23 STBitree *precreate();
24 //打印二叉树
25 int print_bitree(elemtype e);
26 //递归-前序,中序,后序遍历二叉树
27 void preorder(bitree bt, int (*visit)(elemtype e));
28 void inorder(bitree bt, int (*visit)(elemtype e));
29 void postorder(bitree bt, int (*visit)(elemtype e));
30 //非递归-前序,中序,后序遍历二叉树
31 void nrpreorder(bitree root);
32 void nrinorder(bitree root);
33 void nrpostorder(bitree root);
34 void nrpostorderfunc(bitree root, int (*visit)(elemtype e));
35 //根到某个子节点的路径
36 vector<elemtype> rc_path(bitree root, elemtype ekey);
37 //最低公共祖先节点
38 elemtype lca(STBitree *root, elemtype node1, elemtype node2);
39 //释放二叉树
40 void free_bitree(STBitree *bt);
41
42 int main()
43 {
44 STBitree *root;
45 //printf("%lu %lu
", sizeof(STBitree),sizeof(bitree));
46 cout << "create biBtree:";
47 root = precreate();
48 vector<elemtype> ve;
49 lca(root, 'd','c');
50 // cout << "preorder:";
51 // preorder(root, print_bitree);
52 // cout << '
';
53 // cout << "inorder:";
54 // inorder(root, print_bitree);
55 // cout << '
';
56 // cout << "postorder:";
57 // postorder(root, print_bitree);
58 // cout << '
';
59 // cout << "nrpostorder:";
60 // nrpostorderfunc(root, print_bitree);
61 // cout << '
';
62 free_bitree(root);
63 }
64
65 STBitree *precreate(){
66 STBitree *root;
67 char ch;
68 scanf("%c", &ch);
69 if(ch == '#'){
70 root = NULL;
71 }
72 else {
73 root = (STBitree *)malloc(sizeof(STBitree));
74 root->data = ch;
75 root->lchild=precreate();
76 root->rchild=precreate();
77 }
78 return root;
79 }
80
81 int print_bitree(elemtype e){
82 cout << e;
83 return 0;
84 }
85
86 void preorder(bitree bt, int (*visit)(elemtype e))
87 {
88 if (bt) {
89 visit(bt->data);
90 preorder(bt->lchild, visit);
91 preorder(bt->rchild, visit);
92 }
93 }
94
95 void inorder(bitree bt, int (*visit)(elemtype e))
96 {
97 if (bt) {
98 inorder(bt->lchild, visit);
99 visit(bt->data);
100 inorder(bt->rchild, visit);
101 }
102 }
103
104 void postorder(bitree bt, int (*visit)(elemtype e))
105 {
106 if (bt) {
107 postorder(bt->lchild, visit);
108 postorder(bt->rchild, visit);
109 visit(bt->data);
110 }
111 }
112
113 vector<elemtype> rc_path(bitree root, elemtype ekey){
114 stack<bitree> sbt;
115 bitree pCur, pLastVisit;
116 vector<elemtype> ve;
117 pCur = root;
118 pLastVisit = NULL;
119 ve.clear();
120 while (pCur) {
121 sbt.push(pCur);
122 ve.push_back(pCur->data);
123 pCur = pCur->lchild;
124 }
125
126 while (!sbt.empty()) {
127 pCur = sbt.top();
128 sbt.pop();
129 ve.pop_back();
130 if(pCur->rchild == NULL || pLastVisit == pCur->rchild){
131 if(pCur->data == ekey){
132 ve.push_back(pCur->data);
133 // for (vei = ve.begin(); vei != ve.end(); ++vei) {
134 // cout << *vei ;
135 // }
136 return ve;
137 }
138 pLastVisit = pCur;
139 }
140 if(pCur->lchild == pLastVisit){
141 sbt.push(pCur);
142 ve.push_back(pCur->data);
143 pCur = pCur->rchild;
144 while (pCur) {
145 sbt.push(pCur);
146 ve.push_back(pCur->data);
147 pCur = pCur->lchild;
148 }
149 }
150 }
151 }
152
153 elemtype lca(STBitree *root, elemtype node1, elemtype node2){
154 vector<STBitree *> vb;
155 vector<elemtype> ve1;
156 vector<elemtype> ve2;
157 vb.clear();
158 if(root == NULL){
159 return 0;
160 }
161 ve1 = rc_path(root, node1);
162 ve2 = rc_path(root, node2);
163 int idx = 0,preidx = 0;
164 while (ve1[idx] == ve2[idx]) {
165 ++idx;
166 }
167 --idx;
168 cout << ve1[idx];
169 return ve1[idx];
170 }
171
172 void nrpostorder(bitree root){
173 stack<bitree> sbt;// ab#deg###f#h##c##
174 //pCur当前访问节点,pLastVisit上次访问节点 // ab#de##f##c##
175 bitree pCur,pLastVisit;
176 if (root == NULL) {
177 return;
178 }
179 pCur = root;
180 pLastVisit = NULL;
181 while (pCur) {
182 sbt.push(pCur);
183 //vb.push_back(pCur);
184 pCur = pCur->lchild;
185 }
186 // cout << "[从根到最左节点:";
187 // for (vbi = vb.begin(); vbi != vb.end(); ++vbi) {
188 // cout << (*vbi)->data;
189 // }
190 // cout << "]
";
191 while (!sbt.empty()) {
192 pCur = sbt.top();
193 //debug(pCur);
194 sbt.pop();//ab#d##c##
195 // vb.pop_back();
196 // cout << "前栈中元素:";
197 // for (vbi = vb.begin(); vbi != vb.end(); ++vbi) {
198 // cout << (*vbi)->data << endl;
199 // }
200 // cout << '
';
201 //当前节点的右孩子是上次访问的节点pl或者当前节点的右孩子为空,则说明说明可以直接访问该节点了.
202 if((pLastVisit == pCur->rchild) || (pCur->rchild == NULL)){
203 cout << pCur->data;
204 pLastVisit = pCur;
205 }
206 if(pCur->lchild == pLastVisit){
207 sbt.push(pCur);
208 pCur = pCur->rchild;
209 while (pCur) {
210 sbt.push(pCur);
211 pCur = pCur->lchild;
212 }
213 }
214 //N@20161118
215 // if(pCur->rchild != NULL){
216 // if(pLastVisit != pCur->rchild){
217 // sbt.push(pCur);
218 // pCur = pCur->rchild;
219 // while (pCur) {
220 // sbt.push(pCur);
221 // pCur = pCur->lchild;
222 // }
223 // }
224 // }
225 // cout << "后栈中元素:";
226 // for (vbi = vb.begin(); vbi != vb.end(); ++vbi) {
227 // cout << (*vbi)->data << endl;
228 // }
229 // cout << '
';
230 }
231 }
232
233 void nrpostorderfunc(bitree root, int (*visit)(elemtype e)){
234 stack<bitree> sbt;// ab#deg###f#h##c##
235 //pCur当前访问节点,pLastVisit上次访问节点 // ab#de##f##c##
236 bitree pCur,pLastVisit;
237 if (root == NULL) {
238 return;
239 }
240 pCur = root;
241 pLastVisit = NULL;
242 while (pCur) {
243 sbt.push(pCur);
244 //vb.push_back(pCur);
245 pCur = pCur->lchild;
246 }
247 // cout << "[从根到最左节点:";
248 // for (vbi = vb.begin(); vbi != vb.end(); ++vbi) {
249 // cout << (*vbi)->data;
250 // }
251 // cout << "]
";
252 while (!sbt.empty()) {
253 pCur = sbt.top();
254 //debug(pCur);
255 sbt.pop();//ab#d##c##
256 // vb.pop_back();
257 // cout << "前栈中元素:";
258 // for (vbi = vb.begin(); vbi != vb.end(); ++vbi) {
259 // cout << (*vbi)->data << endl;
260 // }
261 // cout << '
';
262 //当前节点的右孩子是上次访问的节点pl或者当前节点的右孩子为空,则说明说明可以直接访问该节点了.
263 if((pLastVisit == pCur->rchild) || (pCur->rchild == NULL)){
264 //cout << pCur->data;
265 visit(pCur->data);
266 pLastVisit = pCur;
267 }
268 if(pCur->lchild == pLastVisit){
269 sbt.push(pCur);
270 pCur = pCur->rchild;
271 while (pCur) {
272 sbt.push(pCur);
273 pCur = pCur->lchild;
274 }
275 }
276 //N@20161118
277 // if(pCur->rchild != NULL){
278 // if(pLastVisit != pCur->rchild){
279 // sbt.push(pCur);
280 // pCur = pCur->rchild;
281 // while (pCur) {
282 // sbt.push(pCur);
283 // pCur = pCur->lchild;
284 // }
285 // }
286 // }
287 // cout << "后栈中元素:";
288 // for (vbi = vb.begin(); vbi != vb.end(); ++vbi) {
289 // cout << (*vbi)->data << endl;
290 // }
291 // cout << '
';
292 }
293 }
294
295 void free_bitree(STBitree *bt)
296 {
297 if (bt) {
298 if ((*bt).lchild)
299 free_bitree((*bt).lchild);
300 if ((*bt).rchild)
301 free_bitree((*bt).rchild);
302 free(bt);
303 bt = NULL;
304 }
305 }