二叉树的抽象数据结构
1 typedef struct Node
2 {
3 char data;
4 struct Node* Lchild;
5 struct Node* Rchild;
6 }BTNode;//Binary Tree Node
打印二叉树的叶子结点
1 void PrintLeafNode(BTNode* A)
2 {/*打印二叉树的叶子结点*/
3 if (A == NULL)
4 {
5 return;
6 }
7 else if ((!A->Lchild) && (!A->Rchild))
8 {
9 printf("%c", A->data);
10 return;
11 }
12 else
13 {
14 PrintLeafNode(A->Lchild);
15 PrintLeafNode(A->Rchild);
16 }
17 }
View Code
二叉树相似性判定(所谓二叉树 A 和 B 相似，是指 A 和 B 要么均为空二叉树、要么 A 的左子树与 B 的左子树相似，且 A 的右子树与 B 的右子树相似)
1 int Like(BTNode* A, BTNode* B)
2 {/*二叉树相似性判定*/
3 int Like1 = 0;
4 int Like2 = 0;
5 if (A == NULL && B == NULL)
6 {
7 return 1;
8 }
9 else if (A == NULL || B == NULL)
10 {
11 return 0;
12 }
13 else
14 {
15 Like1 = Like(A->Lchild, B->Lchild);
16 Like2 = Like(A->Rchild, B->Rchild);
17 return Like1 && Like2;
18 }
19 }
View Code
求二叉树高度
1 int DepthTree(BTNode* A)
2 {/*求二叉树高度*/
3 int Depth = 0;
4 int DepthLeft = 0;
5 int DepthRight = 0;
6 if (A)
7 {
8 DepthLeft = DepthTree(A->Lchild);
9 DepthRight = DepthTree(A->Rchild);
10 Depth = 1 + (DepthLeft > DepthRight ? DepthLeft : DepthRight);
11 }
12 return Depth;
13 }
View Code
统计二叉树的结点数
1 int CountNode(BTNode* A)
2 {/*统计二叉树的结点数*/
3 int sum = 0;
4 if (A)
5 {
6 sum++;
7 sum += CountNode(A->Lchild);
8 sum += CountNode(A->Rchild);
9 }
10 return sum;
11 }
View Code
统计叶子结点数目
1 int CountLeafNode(BTNode* A)
2 {/*统计叶子结点数目*/
3 int sum = 0;
4 if (A)
5 {
6 if (!A->Lchild && !A->Rchild)
7 {
8 sum++;
9 }
10 sum += CountLeafNode(A->Lchild);
11 sum += CountLeafNode(A->Rchild);
12 }
13 return sum;
14 }
View Code
求结点的双亲
1 char Parent(BTNode* A, char ChildNode)
2 {/*求结点的双亲*/
3 char ParentNode = '\0';
4 if (A == NULL)
5 {
6 return '\0';
7 }
8 else if (A->Lchild && A->Lchild->data == ChildNode)
9 {
10 return A->data;
11 }
12 else if (A->Rchild && A->Rchild->data == ChildNode)
13 {
14 return A->data;
15 }
16 else
17 {
18 ParentNode = Parent(A->Lchild, ChildNode);
19 if (ParentNode != '\0')
20 {
21 return ParentNode;
22 }
23 else
24 {/*递归在右子树中找*/
25 return Parent(A->Rchild, ChildNode);
26 }
27 }
28 }
View Code
源代码
1 #define _CRT_SECURE_NO_WARNINGS
2 #include <stdio.h>
3 #include <stdlib.h>
4
5 typedef struct Node
6 {
7 char data;
8 struct Node* Lchild;
9 struct Node* Rchild;
10 }BTNode;//Binary Tree Node
11
12 BTNode* CreateBinaryTree();
13 void PrintLeafNode(BTNode* A);
14 int Like(BTNode* A, BTNode* B);
15 int DepthTree(BTNode* A);
16 int CountNode(BTNode* A);
17 int CountLeafNode(BTNode* A);
18 char Parent(BTNode* A, char ChildNode);
19
20
21 int main(void)
22 {
23 char ChildNode = '\0';
24 char ParentNode = '\0';
25 BTNode* A = NULL;
26 BTNode* B = NULL;
27
28 printf("请输入该二叉树先序遍历序列(用^表示空子树,叶子结点要跟两个^)：\n");
29 A = CreateBinaryTree();
30
31 printf("树的高度：%d\n", DepthTree(A));
32 printf("树总结点数：%d\n", CountNode(A));
33 printf("叶子结点数：%d\n", CountLeafNode(A));
34
35 printf("叶子结点为：");
36 PrintLeafNode(A);
37
38 printf("\n请输入要查询双亲的结点：");
39 scanf(" %c", &ChildNode);/* %c前有一个空格用于吸收空白字符 */
40 ParentNode = Parent(A, ChildNode);
41 if (ParentNode == '\0')
42 {
43 printf("查询失败\n");
44 }
45 else
46 {
47 printf("%c的双亲结点是%c", ChildNode, ParentNode);
48 }
49
50 printf("\n请输入另一个二叉树先序遍历序列(用^表示空子树,叶子结点要跟两个^)：\n");
51 B = CreateBinaryTree();
52 if (Like(A, B))
53 {
54 printf("二叉树A和B相似\n");
55 }
56 else
57 {
58 printf("二叉树A和B不相似\n");
59 }
60
61 system("pause");
62 return 0;
63 }
64
65 BTNode* CreateBinaryTree()
66 {
67 BTNode* A = NULL;
68 char ch = '\0';
69 scanf(" %c", &ch);
70 if (ch == '^')
71 {
72 return NULL;
73 }
74 else
75 {
76 A = (BTNode*)calloc(1, sizeof(BTNode));
77 A->data = ch;
78 A->Lchild = CreateBinaryTree();
79 A->Rchild = CreateBinaryTree();
80 return A;
81 }
82 }
83
84 void PrintLeafNode(BTNode* A)
85 {/*打印二叉树的叶子结点*/
86 if (A == NULL)
87 {
88 return;
89 }
90 else if ((!A->Lchild) && (!A->Rchild))
91 {
92 printf("%c", A->data);
93 return;
94 }
95 else
96 {
97 PrintLeafNode(A->Lchild);
98 PrintLeafNode(A->Rchild);
99 }
100 }
101
102 int Like(BTNode* A, BTNode* B)
103 {/*二叉树相似性判定*/
104 int Like1 = 0;
105 int Like2 = 0;
106 if (A == NULL && B == NULL)
107 {
108 return 1;
109 }
110 else if (A == NULL || B == NULL)
111 {
112 return 0;
113 }
114 else
115 {
116 Like1 = Like(A->Lchild, B->Lchild);
117 Like2 = Like(A->Rchild, B->Rchild);
118 return Like1 && Like2;
119 }
120 }
121
122 int DepthTree(BTNode* A)
123 {/*求二叉树高度*/
124 int Depth = 0;
125 int DepthLeft = 0;
126 int DepthRight = 0;
127 if (A)
128 {
129 DepthLeft = DepthTree(A->Lchild);
130 DepthRight = DepthTree(A->Rchild);
131 Depth = 1 + (DepthLeft > DepthRight ? DepthLeft : DepthRight);
132 }
133 return Depth;
134 }
135
136 int CountNode(BTNode* A)
137 {/*统计二叉树的结点数*/
138 int sum = 0;
139 if (A)
140 {
141 sum++;
142 sum += CountNode(A->Lchild);
143 sum += CountNode(A->Rchild);
144 }
145 return sum;
146 }
147
148 int CountLeafNode(BTNode* A)
149 {/*统计叶子结点数目*/
150 int sum = 0;
151 if (A)
152 {
153 if (!A->Lchild && !A->Rchild)
154 {
155 sum++;
156 }
157 sum += CountLeafNode(A->Lchild);
158 sum += CountLeafNode(A->Rchild);
159 }
160 return sum;
161 }
162
163 char Parent(BTNode* A, char ChildNode)
164 {/*求结点的双亲*/
165 char ParentNode = '\0';
166 if (A == NULL)
167 {
168 return '\0';
169 }
170 else if (A->Lchild && A->Lchild->data == ChildNode)
171 {
172 return A->data;
173 }
174 else if (A->Rchild && A->Rchild->data == ChildNode)
175 {
176 return A->data;
177 }
178 else
179 {
180 ParentNode = Parent(A->Lchild, ChildNode);
181 if (ParentNode != '\0')
182 {
183 return ParentNode;
184 }
185 else
186 {/*递归在右子树中找*/
187 return Parent(A->Rchild, ChildNode);
188 }
189 }
190 }
View Code