数据结构-二叉树的构建与遍历_数据结构中二叉树的建立

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、二叉树的定义

图例：

二叉树是每个结点最多有两个子树的树结构，常被用于实现二叉查找树和二叉堆。二叉树是链式存储结构，用的是二叉链，本质上是链表。结构体定义二叉树节点：

typedef struct BTNode
{
	char element;
	struct BTNode* left;
	struct BTNode* right;
}BTNode,*BTNodePtr;
1
2
3
4
5
6

二、二叉树的建立

BTNodePtr constructBTNode(char paraChar)
{
	BTNodePtr resultPtr = (BTNodePtr)malloc(sizeof(struct BTNode));
	resultPtr->element = paraChar;
	resultPtr->left = NULL;
	resultPtr->right = NULL;
	return resultPtr;
}
1
2
3
4
5
6
7
8

三、二叉树的遍历

1.先序遍历

先序遍历的过程是首先访问根结点，然后先序遍历根的左子树，最后先序遍历根的右子树。对于根的左子树和右子树，遍历的过程相同。
代码如下（示例）：

void preorder(BTNodePtr tempPtr)//先序遍历 
{
	if (tempPtr == NULL)
	{
		return;
	}

	printf("%c", tempPtr->element);
	preorder(tempPtr->left);
	preorder(tempPtr->right);
}
1
2
3
4
5
6
7
8
9
10
11

2.中序遍历

中序遍历的过程是首先中序遍历左子树，然后访问根结点，最后中序遍历根的右子树。对于根的左子树和右子树，遍历的过程相同。
代码如下（示例）：

void inorder(BTNodePtr tempPtr)//中序遍历 
{
	if (tempPtr == NULL) 
	{
		return;
	}

	inorder(tempPtr->left);
	printf("%c", tempPtr->element);
	inorder(tempPtr->right);
}
1
2
3
4
5
6
7
8
9
10
11

3.后序遍历

后序遍历的过程是首先后序遍历左子树，然后后序遍历根的右子树，最后访问根结点。

void postorder(BTNodePtr tempPtr)//后序遍历 
{
	if (tempPtr == NULL) 
	{
		return;
	}

	postorder(tempPtr->left);
	postorder(tempPtr->right);
	printf("%c", tempPtr->element);
}
1
2
3
4
5
6
7
8
9
10
11

4.层序遍历

在进行层次遍历时，对一层结点访问完后再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层地进行，先遇到的结点先访问，先上到下，先左到右。实现层次遍历用队列比较方便，因为是先进先出（FIFO）。首先把队首元素入队，然后再输出队首元素，并且把队首元素的左结点和右结点入队（如果有的话），以此类推，输出的序列就是层次遍历。

void levelwise(BTNodePtr paraTreePtr)
{
	char tempString[100];
	int i = 0;
	QueuePtr tempQueuePtr = initQueue();
	BTNodePtr tempNodePtr;
	enqueue(tempQueuePtr, paraTreePtr);
	while(!isQueueEmpty(tempQueuePtr)) 
	{
		tempNodePtr = dequeue(tempQueuePtr);
		
		tempString[i] = tempNodePtr->element;
		i ++;

		if (tempNodePtr->left != NULL)
		{
			enqueue(tempQueuePtr, tempNodePtr->left);
		}
		if (tempNodePtr->right != NULL)
		{
			enqueue(tempQueuePtr, tempNodePtr->right);
		}
	}
	tempString[i] = '\0';

	printf("Levelwise: %s\r\n", tempString);
}
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

四、二叉树的叶、节点、深度

1、求叶子数目

int LeafCount(BTNodePtr tempPtr)
{
	if(tempPtr == NULL)
	{
		return 0;
	}
	else if(tempPtr->left == NULL && tempPtr->right == NULL)
	{
		return 1;
	}
	else
	{
		return LeafCount(tempPtr->left)+LeafCount(tempPtr->right);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2、求节点数目

int Nodecount(BTNodePtr tempPtr) 
{
	if(tempPtr == NULL)
	{
		return 0;
	}
	else
	{
		return Nodecount(tempPtr->left)+Nodecount(tempPtr->right)+1;
	}
}
1
2
3
4
5
6
7
8
9
10
11

3、求二叉树深度

int Depth(BTNodePtr tempPtr)
{
	int m,n;
	if(tempPtr == NULL)
	{
		return 0;
	}
	else
	{
		m=Depth(tempPtr->left);
		n=Depth(tempPtr->right);
		if(m>n)
		{
			return m+1;
		}
		else
		{
			return n+1;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

五、辅助函数

typedef struct BTNodePtrQueue
{
	BTNodePtr* nodePtr;
	int front;
	int rear;
}BTNodePtrQueue,*QueuePtr;//队列结构体

QueuePtr initQueue()
{
	QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
	resultQueuePtr->front = 0;
	resultQueuePtr->rear = 1;
	resultQueuePtr->nodePtr = (BTNodePtr*)malloc(sizeof(struct BTNode)*QUEUE_SIZE);
	return resultQueuePtr;
}//初始化队列

BTNodePtr stringToBTree(char* paraString)
{
	int i;
	char ch;

	QueuePtr tempQueuePtr = initQueue();

	BTNodePtr resultHeader;
	BTNodePtr tempParent, tempLeftChild, tempRightChild;
	i = 0;
	ch = paraString[i];
	resultHeader = constructBTNode(ch);
	enqueue(tempQueuePtr, resultHeader);

	while(!isQueueEmpty(tempQueuePtr)) 
	{
		tempParent = dequeue(tempQueuePtr);

		i ++;
		ch = paraString[i];
		if (ch == '#')
		{
			tempParent->left = NULL;
		} 
		else 
		{
			tempLeftChild = constructBTNode(ch);
			enqueue(tempQueuePtr, tempLeftChild);
			tempParent->left = tempLeftChild;
		}

		i ++;
		ch = paraString[i];
		if (ch == '#') 
		{
			tempParent->right = NULL;
		} 
		else 
		{
			tempRightChild = constructBTNode(ch);
			enqueue(tempQueuePtr, tempRightChild);
			tempParent->right = tempRightChild;
		}
	}

	return resultHeader;
}//二叉树赋值

void enqueue(QueuePtr paraQueueptr,BTNodePtr paraBTNodePtr)
{
	printf("front=%d ,rear=%d.\r\n",paraQueueptr->front,paraQueueptr->rear);
	if((paraQueueptr->rear + 1) % QUEUE_SIZE == paraQueueptr->front % QUEUE_SIZE)
	{
		printf("Error, trying to enqueue %c. queue full.\r\n", paraBTNodePtr->element);
		return;
	}
	paraQueueptr->nodePtr[paraQueueptr->rear] = paraBTNodePtr;
	paraQueueptr->rear = (paraQueueptr->rear + 1) % QUEUE_SIZE;
	printf("enqueue %c ends.\r\n", paraBTNodePtr->element);
}//进队

BTNodePtr dequeue(QueuePtr paraQueuePtr)
{
	if (isQueueEmpty(paraQueuePtr)) 
	{
		printf("Error, empty queue\r\n");
		return NULL;
	}

	paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE;

	printf("dequeue %c ends.\r\n", paraQueuePtr->nodePtr[paraQueuePtr->front]->element);
	return paraQueuePtr->nodePtr[paraQueuePtr->front];
}//出队

bool isQueueEmpty(QueuePtr paraQueueptr)
{
	if((paraQueueptr->front + 1) % QUEUE_SIZE == paraQueueptr->rear) 
	{
		return true;
	}
	return false;
}//队列判空
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

六、完整代码

#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>

#define QUEUE_SIZE 5

typedef struct BTNode
{
	char element;
	struct BTNode* left;
	struct BTNode* right;
}BTNode,*BTNodePtr;

typedef struct BTNodePtrQueue
{
	BTNodePtr* nodePtr;
	int front;
	int rear;
}BTNodePtrQueue,*QueuePtr;

QueuePtr initQueue()
{
	QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
	resultQueuePtr->front = 0;
	resultQueuePtr->rear = 1;
	resultQueuePtr->nodePtr = (BTNodePtr*)malloc(sizeof(struct BTNode)*QUEUE_SIZE);
	return resultQueuePtr;
}

bool isQueueEmpty(QueuePtr paraQueueptr)
{
	if((paraQueueptr->front + 1) % QUEUE_SIZE == paraQueueptr->rear) 
	{
		return true;
	}
	return false;
}

void enqueue(QueuePtr paraQueueptr,BTNodePtr paraBTNodePtr)
{
	printf("front=%d ,rear=%d.\r\n",paraQueueptr->front,paraQueueptr->rear);
	if((paraQueueptr->rear + 1) % QUEUE_SIZE == paraQueueptr->front % QUEUE_SIZE)
	{
		printf("Error, trying to enqueue %c. queue full.\r\n", paraBTNodePtr->element);
		return;
	}
	paraQueueptr->nodePtr[paraQueueptr->rear] = paraBTNodePtr;
	paraQueueptr->rear = (paraQueueptr->rear + 1) % QUEUE_SIZE;
	printf("enqueue %c ends.\r\n", paraBTNodePtr->element);
}

BTNodePtr dequeue(QueuePtr paraQueuePtr)
{
	if (isQueueEmpty(paraQueuePtr)) 
	{
		printf("Error, empty queue\r\n");
		return NULL;
	}

	paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE;

	printf("dequeue %c ends.\r\n", paraQueuePtr->nodePtr[paraQueuePtr->front]->element);
	return paraQueuePtr->nodePtr[paraQueuePtr->front];
}

BTNodePtr constructBTNode(char paraChar)
{
	BTNodePtr resultPtr = (BTNodePtr)malloc(sizeof(struct BTNode));
	resultPtr->element = paraChar;
	resultPtr->left = NULL;
	resultPtr->right = NULL;
	return resultPtr;
}

BTNodePtr stringToBTree(char* paraString)
{
	int i;
	char ch;

	QueuePtr tempQueuePtr = initQueue();

	BTNodePtr resultHeader;
	BTNodePtr tempParent, tempLeftChild, tempRightChild;
	i = 0;
	ch = paraString[i];
	resultHeader = constructBTNode(ch);
	enqueue(tempQueuePtr, resultHeader);

	while(!isQueueEmpty(tempQueuePtr)) 
	{
		tempParent = dequeue(tempQueuePtr);

		i ++;
		ch = paraString[i];
		if (ch == '#')
		{
			tempParent->left = NULL;
		} 
		else 
		{
			tempLeftChild = constructBTNode(ch);
			enqueue(tempQueuePtr, tempLeftChild);
			tempParent->left = tempLeftChild;
		}

		i ++;
		ch = paraString[i];
		if (ch == '#') 
		{
			tempParent->right = NULL;
		} 
		else 
		{
			tempRightChild = constructBTNode(ch);
			enqueue(tempQueuePtr, tempRightChild);
			tempParent->right = tempRightChild;
		}
	}

	return resultHeader;
}

void levelwise(BTNodePtr paraTreePtr)
{
	char tempString[100];
	int i = 0;
	QueuePtr tempQueuePtr = initQueue();
	BTNodePtr tempNodePtr;
	enqueue(tempQueuePtr, paraTreePtr);
	while(!isQueueEmpty(tempQueuePtr)) 
	{
		tempNodePtr = dequeue(tempQueuePtr);
		
		tempString[i] = tempNodePtr->element;
		i ++;

		if (tempNodePtr->left != NULL)
		{
			enqueue(tempQueuePtr, tempNodePtr->left);
		}
		if (tempNodePtr->right != NULL)
		{
			enqueue(tempQueuePtr, tempNodePtr->right);
		}
	}
	tempString[i] = '\0';

	printf("Levelwise: %s\r\n", tempString);
}

void preorder(BTNodePtr tempPtr)//先序遍历 
{
	if (tempPtr == NULL)
	{
		return;
	}

	printf("%c", tempPtr->element);
	preorder(tempPtr->left);
	preorder(tempPtr->right);
}

void inorder(BTNodePtr tempPtr)//中序遍历 
{
	if (tempPtr == NULL) 
	{
		return;
	}

	inorder(tempPtr->left);
	printf("%c", tempPtr->element);
	inorder(tempPtr->right);
}

void postorder(BTNodePtr tempPtr)//后序遍历 
{
	if (tempPtr == NULL) 
	{
		return;
	}

	postorder(tempPtr->left);
	postorder(tempPtr->right);
	printf("%c", tempPtr->element);
}

int LeafCount(BTNodePtr tempPtr)
{
	if(tempPtr == NULL)
	{
		return 0;
	}
	else if(tempPtr->left == NULL && tempPtr->right == NULL)
	{
		return 1;
	}
	else
	{
		return LeafCount(tempPtr->left)+LeafCount(tempPtr->right);
	}
}

int Depth(BTNodePtr tempPtr)
{
	int m,n;
	if(tempPtr == NULL)
	{
		return 0;
	}
	else
	{
		m=Depth(tempPtr->left);
		n=Depth(tempPtr->right);
		if(m>n)
		{
			return m+1;
		}
		else
		{
			return n+1;
		}
	}
}

int Nodecount(BTNodePtr tempPtr) 
{
	if(tempPtr == NULL)
	{
		return 0;
	}
	else
	{
		return Nodecount(tempPtr->left)+Nodecount(tempPtr->right)+1;
	}
}


int main()
{
	BTNodePtr tempHeader;
	tempHeader = constructBTNode('c');
	printf("There is only one node. Preorder visit: ");
	preorder(tempHeader);
	printf("\r\n\n");
	
	char* tempString = "acde#bf######";
	tempHeader = stringToBTree(tempString);
	printf("先序: ");
	preorder(tempHeader);//先序：中左右 
	
	printf("\r\n\n");
	printf("中序: ");  
	inorder(tempHeader);//中序：左中右 
	
	printf("\r\n\n");
	printf("后序: ");
	postorder(tempHeader);//后序：左右中 
	
	printf("\r\n\n");
	printf("Lvelwise: ");  
	levelwise(tempHeader);//层序 
	
	printf("\r\n\n");
	int k;
	k = LeafCount(tempHeader);
	printf("树的叶子有：%d",k);
	
	printf("\r\n\n");
	int l;
	l = Depth(tempHeader);
	printf("树的深度：%d",l);
	
	printf("\r\n\n");
	int n;
	n = Nodecount(tempHeader);
	printf("树的节点数：%d",n);
	return 0;
}
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
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278

运行结果：

There is only one node. Preorder visit: c

front=0 ,rear=1.
enqueue a ends.
dequeue a ends.
front=1 ,rear=2.
enqueue c ends.
front=1 ,rear=3.
enqueue d ends.
dequeue c ends.
front=2 ,rear=4.
enqueue e ends.
dequeue d ends.
front=3 ,rear=0.
enqueue b ends.
front=3 ,rear=1.
enqueue f ends.
dequeue e ends.
dequeue b ends.
dequeue f ends.
先序: acedbf

中序: ecabdf

后序: ecbfda

Lvelwise: front=0 ,rear=1.
enqueue a ends.
dequeue a ends.
front=1 ,rear=2.
enqueue c ends.
front=1 ,rear=3.
enqueue d ends.
dequeue c ends.
front=2 ,rear=4.
enqueue e ends.
dequeue d ends.
front=3 ,rear=0.
enqueue b ends.
front=3 ,rear=1.
enqueue f ends.
dequeue e ends.
dequeue b ends.
dequeue f ends.
Levelwise: acdebf


树的叶子有：3

树的深度：3

树的节点数：6
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