【数据结构和算法】二叉树的链式结构（二叉树的创建、销毁；二叉树的前中后序遍历；求二叉树的高度；求二叉树节点、叶子节点、第K层节点的个数；查找二叉树节点；判断是否是完全二叉树）_销毁二叉树

1.结构的声明及定义

typedef char BTDataType;

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

1
2
3
4
5
6
7
8

---

2.通过前序遍历的数组构建二叉树

char a[] = "ABD##E#H##CF##G##";
int i = 0;
BTNode *root = BinaryTreeCreat(a, sizeof(a) / sizeof(a[0]), &i);

BTNode* BinaryTreeCreat(BTDataType *arr, int sz, int *i){

	if (*i >= sz || arr[*i] == '#')
	{
		(*i)++;
		return NULL;
	}

	BTNode *cur = BuyBTNode(arr[(*i)++]);
	cur->left = BinaryTreeCreat(arr, sz, i);
	cur->right = BinaryTreeCreat(arr, sz, i);
	
	return cur;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

关键点：

1. 遇到‘#’或数组结束都要返回NULL
2. 返回NULL之前(*i)++不能忘;
3. 数组的顺序就是二叉树前序遍历的顺序

---

3.销毁二叉树

void BinaryTreeDestroy(BTNode *root){

	if (root == NULL)
	{
		return;
	}

	BinaryTreeDestroy(root->left);
	BinaryTreeDestroy(root->right);
	free(root);
}
1
2
3
4
5
6
7
8
9
10
11

销毁的顺序：先销毁左树，再销毁右树，最后销毁根节点。

---

4.前序遍历

void PreOrder(BTNode *root){
	if (root == NULL)
	{
		return;
	}

	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10

---

5.中序遍历

void InOrder(BTNode *root){
	if (root == NULL)
	{
		return;
	}
	
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10

---

6.后序遍历

void PostOrder(BTNode *root){
	if (root == NULL)
	{
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}
1
2
3
4
5
6
7
8
9
10

---

7.层序遍历

void LevelOrder(BTNode *root){

	if (root == NULL)
	{
		return;
	}

	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode *front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->data);

		if (front->left != NULL)
		{
			QueuePush(&q, front->left);
		}

		if (front->right != NULL)
		{
			QueuePush(&q, front->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

原理：利用了队列先进先出的性质，按序取出上一层节点的同时已经将下一层节点（上一层的左右节点）入队，循环往复直到遍历完整个二叉树。

关键点：

1. 要在循环外将根节点入队。
2. 队列为空时结束循环。
3. 遍历方法：1.队头节点出队；2.将队头节点的左右节点节点入队（空节点不入队）
4. 函数返回前记得销毁队列。

---

8.二叉树的高度/深度

int TreeDepth(BTNode *root){
	if (root == NULL)
	{
		return 0;
	}

	int leftDepth = TreeDepth(root->left);
	int rightDepth = TreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
}
1
2
3
4
5
6
7
8
9
10
11

二叉树的深度=左右子树最深的高度+1；

---

9.节点总个数

int TreeSize(BTNode *root){
	if (root == NULL)
	{
		return 0;
	}

	return TreeSize(root->left) + TreeSize(root->right) + 1;
}
1
2
3
4
5
6
7
8

二叉树的节点数=左树的节点+右树的节点+1；

---

10.叶子节点的个数

int LeafSize(BTNode *root){
	if (root == NULL)
	{
		return 0;
	}

	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return LeafSize(root->left) + LeafSize(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

二叉树的叶子节点=左树的叶子节点+右树的叶子节点；

---

11.第K层节点的个数

int LevelKSize(BTNode *root, int k){
	assert(k > 0);
	if (root == NULL){
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}

	return LevelKSize(root->left, k - 1) + LevelKSize(root->right, k - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

第K层节点的个数=左树第(k-1)层的节点数+右树第(k-1)层的节点数；

注意判断(k>0)

---

12.查找值为x的节点

BTNode* BinaryTreeFind(BTNode *root, BTDataType val){
	if (root == NULL)
	{
		return NULL;
	}

	if (root->data == val)
	{
		return root;
	}
	
	BTNode *ret = BinaryTreeFind(root->left, val);
	if (ret == NULL)
	{
		ret = BinaryTreeFind(root->right, val);
	}
	return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

注意：左树找到了就不要在右树找了，找不到再从右树找。

---

13.判断完全二叉树

bool BinaryTreeComplete(BTNode *root){
	if (root == NULL)
	{
		return false;
	}

	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode *front = QueueFront(&q);
		QueuePop(&q);

		//方法一：
		if (front == NULL)
		{
			if (!QueueEmpty(&q) && QueueFront(&q)!=NULL)
			{
				QueueDestroy(&q);
				return false;
			}
		}
		//方法二：
		/*if (front == NULL)
		{
			break;
		}*/
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}

	/*while (!QueueEmpty(&q))
	{
		BTNode *front = QueueFront(&q);
		QueuePop(&q);

		if (front != NULL)
		{
		QueueDestroy(&q);
		return false;
		}
	}*/

	QueueDestroy(&q);
	return true;
}
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

原理：完全二叉树的特点就是最后一层的节点是连续的（节点之间不会出现空节点）。话句话说出现空节点之后不能再出现非空节点。根据这一特点，当层序遍历到空节点时，队列中的节点若全是空节点就是完全二叉树，反之就是非完全二叉树。

关键点：

1. 与层序遍历不同，判断完全二叉树时要将空节点也入队。
2. 方法一：遍历到空节点时，检查队头是否也是空节点。（注意判断队列是否为空）
3. 方法二：遍历到空节点时，跳出循环。重新启动一个循环检查队列中的节点是否都是空节点。
4. 函数返回前记得销毁队列。