二叉树链式结构的实现_"谦虚遍// 通过前序遍历的数组\"abd##e#h##cf##g##\"构建二叉树 btnode*

二叉树的遍历

前序、中序以及后序遍历

学习二叉树结构，最简单就是遍历，所谓二叉树遍历是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上其他运算的基础。

二叉树遍历的分类：
前序遍历—访问根结点的操作发生在遍历其左右子树之前（根左右）
中序遍历—访问根结点的操作发生在遍历其左右子树之中（左根右）
后序遍历—访问根结点的操作发生在遍历其左右子树之后（根左右）

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%d ", root->data);
	BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->data);
}
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

下面主要分析前序递归遍历

前序遍历结果：1 2 3 4 5 6
中序遍历结果：3 2 1 5 4 6
后序遍历结果：3 2 5 6 4 1

层序遍历

层序遍历：1 2 4 3 5 6

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 层序遍历---利用队列的思想，每次保存孩子结点
void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == NULL)
		return;
	//定义一个队列
	Queue q;
	//初始化队列，把根结点入栈
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode *cur = QueueFront(&q); 
		printf("%c ", cur->data);
		QueuePop(&q);
		//只要孩子不为空，就入栈
		if (cur->left)
		{
			QueuePush(&q, cur->left);
		}
		if (cur->right)
		{
			QueuePush(&q, cur->right);
		}
	}
	QueueDestroy(&q);
}
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

结点个数以及高度

// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
// 二叉树高度
int BinaryHeight(BTNode* root);

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	//左子树结点+右子树结点+根结点
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	//左子树叶子结点+右子树叶子结点个数
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL || k <= 0)
		return 0;
	if (k == 1)
		return 1;
	//对于第一层，求第k层结点个数
	//对于第二层，求第k-1层结点个数
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;

	BTNode *ret = NULL;
	if (ret = BinaryTreeFind(root->left, x))
		return ret;
	return BinaryTreeFind(root->right, x);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	int flag = 0;
	while (!QueueEmpty(&q))
	{
		BTNode *cur = QueueFront(&q); //往下遍历
		QueuePop(&q);
		if (NULL == cur)   //如果cur是空的，就把flag置为1
			flag = 1;
		if (flag && cur)   //现在又发现非空情况，不是完全二叉树
		{
			QueueDestroy(&q);
			return false;
		}
		if (cur)
		{
			QueuePush(&q, cur->left);
			QueuePush(&q, cur->right);
		}
	}
	QueueDestroy(&q);
	return true;
}
// 二叉树高度
int BinaryHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	//二叉树高度等于左子树和右子树中高的树加1
	return BinaryHeight(root->left) > BinaryHeight(root->right) ? BinaryHeight(root->left) + 1 : BinaryHeight(root->right) + 1;
}

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

二叉树的创建和销毁

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int size, BTDataType x);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
//开辟一个值为val的新节点
BTNode* BuyBTNode(BTDataType val)
{
	BTNode *newnode = (BTNode*)malloc(sizeof(BTNode));
	if (!newnode)
	{
		assert(0);
		return NULL;
	}
	newnode->data = val;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
//
BTNode* _BinaryTreeCreate(BTDataType* a, int size, int* index,BTDataType x)
{
	BTNode *root = NULL;
	if (a[*index] == x)
	{
		return NULL;
	}
	if((*index) < size)
	{
		//创建根结点
		root = BuyBTNode(a[*index]);
		//创建根的左子树
		(*index)++;
		root->left = _BinaryTreeCreate(a, size, index,x);
		//创建右子树
		(*index)++;
		root->right = _BinaryTreeCreate(a, size, index, x);
		
	}
	return root;
	
}
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int size, BTDataType x)
{
	int index = 0;
	return _BinaryTreeCreate(a, size, &index, x);
}
// 二叉树销毁--先销毁孩子结点，最后销毁双亲结点
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
		return;
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
	*root = NULL;
}
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

附录：总代码

HeadFile.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
1
2
3
4
5

BinaryTree.h文件

#pragma once
#include"HeadFile.h"
typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int size, BTDataType x);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
// 二叉树高度
int BinaryHeight(BTNode* root);
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

BinaryTree.c文件

#include"BinaryTree.h"
#include"queue.h"
#include"HeadFile.h"
/*
 *typedef char BTDataType;
 *
 *typedef struct BinaryTreeNode
 *{
 *	BTDataType data;
 *	struct BinaryTreeNode* left;
 *	struct BinaryTreeNode* right;
 *}BTNode;
*/
BTNode* BuyBTNode(BTDataType val)
{
	BTNode *newnode = (BTNode*)malloc(sizeof(BTNode));
	if (!newnode)
	{
		assert(0);
		return NULL;
	}
	newnode->data = val;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
//
BTNode* _BinaryTreeCreate(BTDataType* a, int size, int* index,BTDataType x)
{
	BTNode *root = NULL;
	if (a[*index] == x)
	{
		return NULL;
	}
	if((*index) < size)
	{
		//创建根结点
		root = BuyBTNode(a[*index]);
		//创建根的左子树
		(*index)++;
		root->left = _BinaryTreeCreate(a, size, index,x);
		//创建右子树
		(*index)++;
		root->right = _BinaryTreeCreate(a, size, index, x);
		
	}
	return root;
	
}

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int size, BTDataType x)
{
	int index = 0;
	return _BinaryTreeCreate(a, size, &index, x);
}
// 二叉树销毁--先销毁孩子结点，最后销毁双亲结点
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
		return;
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
	free(*root);
	*root = NULL;
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL || k <= 0)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;

	BTNode *ret = NULL;
	if (ret = BinaryTreeFind(root->left, x))
		return ret;
	return BinaryTreeFind(root->right, x);
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}
// 层序遍历---利用队列的思想，每次保存孩子结点
void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == NULL)
		return;
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode *cur = QueueFront(&q); //往下遍历
		//打印双亲
		printf("%c ", cur->data);
		QueuePop(&q);
		if (cur->left)
		{
			QueuePush(&q, cur->left);
		}
		if (cur->right)
		{
			QueuePush(&q, cur->right);
		}
	}
	QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	int flag = 0;
	while (!QueueEmpty(&q))
	{
		BTNode *cur = QueueFront(&q); //往下遍历
		QueuePop(&q);
		if (NULL == cur)   //如果cur是空的，就把flag置为1
			flag = 1;
		if (flag && cur)   //现在又发现非空情况，不是完全二叉树
		{
			QueueDestroy(&q);
			return false;
		}
		if (cur)
		{
			QueuePush(&q, cur->left);
			QueuePush(&q, cur->right);
		}
	}
	QueueDestroy(&q);
	return true;
}
// 二叉树高度
int BinaryHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BinaryHeight(root->left) > BinaryHeight(root->right) ? BinaryHeight(root->left) + 1 : BinaryHeight(root->right) + 1;
}
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

main.c文件

#include"BinaryTree.h"
#include"HeadFile.h"
void test1()
{
	BTDataType a[] = "ABD##E#H##CF##G##";
	BTNode *root = BinaryTreeCreate(a, sizeof(a) / sizeof(a[0]), '#');
	printf("结点个数 = %d\n",BinaryTreeSize(root));
	printf("叶子结点个数 = %d\n", BinaryTreeLeafSize(root));
	printf("第%d层结点个数 = %d\n", 1, BinaryTreeLevelKSize(root, 1));
	printf("第%d层结点个数 = %d\n", 3, BinaryTreeLevelKSize(root, 3));
	printf("第%d层结点个数 = %d\n", 5, BinaryTreeLevelKSize(root, 5));
	if (BinaryTreeFind(root, 'E'))
	{
		printf("查找%c的结点值为 = %c\n", 'E', BinaryTreeFind(root, 'E')->data);
	}
	if (BinaryTreeFind(root, 'W'))
	{
		printf("查找%c的结点值为 = %c\n", 'W', BinaryTreeFind(root, 'W')->data);
	}
	printf("先序遍历:");
	BinaryTreePrevOrder(root);
	printf("\n");

	printf("中序遍历:");
	BinaryTreeInOrder(root);
	printf("\n");	

	printf("后序遍历:");
	BinaryTreePostOrder(root);
	printf("\n");

	printf("层次遍历:");
	BinaryTreeLevelOrder(root);
	printf("\n");

	printf("该二叉树是完全二叉树：%d\n", BinaryTreeComplete(root));
	printf("该二叉树的高度是：%d\n", BinaryHeight(root));

	BinaryTreeDestory(&root);
}
void test2()
{
	BTDataType a[] = "ABD##E##CF##G##";
	BTNode *root = BinaryTreeCreate(a, sizeof(a) / sizeof(a[0]), '#');
	printf("结点个数 = %d\n", BinaryTreeSize(root));
	printf("叶子结点个数 = %d\n", BinaryTreeLeafSize(root));
	printf("第%d层结点个数 = %d\n", 1, BinaryTreeLevelKSize(root, 1));
	printf("第%d层结点个数 = %d\n", 3, BinaryTreeLevelKSize(root, 3));
	printf("第%d层结点个数 = %d\n", 5, BinaryTreeLevelKSize(root, 5));
	if (BinaryTreeFind(root, 'E'))
	{
		printf("查找%c的结点值为 = %c\n", 'E', BinaryTreeFind(root, 'E')->data);
	}
	if (BinaryTreeFind(root, 'W'))
	{
		printf("查找%c的结点值为 = %c\n", 'W', BinaryTreeFind(root, 'W')->data);
	}
	printf("先序遍历:");
	BinaryTreePrevOrder(root);
	printf("\n");

	printf("中序遍历:");
	BinaryTreeInOrder(root);
	printf("\n");

	printf("后序遍历:");
	BinaryTreePostOrder(root);
	printf("\n");

	printf("层次遍历:");
	BinaryTreeLevelOrder(root);
	printf("\n");

	printf("该二叉树是完全二叉树：%d\n", BinaryTreeComplete(root));
	printf("该二叉树的高度是：%d\n", BinaryHeight(root));

	BinaryTreeDestory(&root);
}
int main()
{
	test1();
	test2();
	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