【数据结构】非线性表----二叉树详解

二叉树与普通的树的本质上的区别实际上只有一个——子结点的数量。

普通的树：任意数量的子结点
二叉树：只有两个子结点，也称为左孩子和右孩子结点。

二叉树一共有五种形态：
1.空二叉树。
2.只有一个根结点。
3.根结点只有左子树。
4.根结点只有右子树。
5.根结点既有左子树又有右子树。

那么根据这五种形态就可以延申一个问题：如果有三个结点的二叉树，它能够有几种形态呢？
我们根据以上的五种形态，可以画出如下的形态

二叉树的特性：

满二叉树：除了第一层，其他层的结点都有两个子节点

完全二叉树：除了最后一层外，每层的节点数都达到最大，并且最后一层的节点都集中在左侧。（注：完全二叉树和满二叉树的关系相当于正方形和长方形的关系）

二叉搜索树：一种特定类型的二叉树，对于每个节点，左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。

二叉树的公式

二叉树有几个重要的性质和公式，这是基于二叉树的特性的，有助于理解其结构和行为。以下是一些常见的二叉树相关公式和性质：

1. 节点数量与高度的关系

对于一棵具有 (h) 的高度的完全二叉树，节点的数量 (n) 的范围是：

• 最小节点数：一棵只有根节点的二叉树，n=1
• 最大节点数：完全二叉树的节点数为 n=2^(h+1)−1。那么高度为 (h) 的二叉树的最大节点数为：
• 

2. 完全二叉树的叶子节点与高度

一棵完全二叉树的叶子节点 (L) 的数量与高度 (h) 的关系为：

这适用于从高度为0到高度为(h)的索引。

3. 内部节点数量

对于包含 (n) 个节点的二叉树，内部节点（即有至少一个子节点的节点）数量 (I) 和叶子节点数量 (L) 的关系为：

且总有：

这是因为内部结点仅仅比叶子节点少一个根节点

因此我们可以得出：

4. 节点深度与高度

对于每个节点，其深度（从根节点到该节点的边数） (d) 与树的高度 (h) 的关系是：

5. 完全二叉树的索引

在完全二叉树中，如果父节点为 (i)，则：

• 左子节点为 (2i + 1)
• 右子节点为 (2i + 2)
• 反之，如果一个节点的索引为 j，其父节点的索引为***(j-1)/2***
• 注意，本公式的条件是完全二叉树，但是实际上二叉树都符合这个公式

6.完全二叉树的度

• 

• 度为0的永远比度为2 的多一个，即 N0=N2+1

• 叶子节点的个数——即度为0的个数N0

7.完全二叉树的节点数量

8. 二叉搜索树的性质

在二叉搜索树中：

• 所有左子树的节点值均小于节点值。
• 所有右子树的节点值均大于节点值。

9. 平衡条件

对于一棵 AVL 树（自平衡的二叉搜索树），任何节点的两个子树的高度差至多为 1。这个性质确保了 AVL 树的高度始终保持在 (O(log n))。

二叉树的构建

我们知道，对于树来说，实际上它的子结点本身也是一棵树，那么我们通常就会使用递归的方法来构建树。

递归的介绍

递归，其中函数在其定义的过程中调用自身。

递归通常由两个基本部分组成：

1. 递归基（Base Case）：

   • 这是停止递归调用的条件。当满足某个条件时，函数返回一个结果，而不再进行进一步的递归调用。

2. 递归步骤（Recursive Step）：

   • 这是函数如何将问题分解成更小的子问题的部分。函数调用自身来处理这些子问题，并通常会将结果合并以生成最终结果。

递归的优点

既然我们二叉树可以使用递归，那么递归都有哪些优点呢？

1. 代码简洁性：

   • 递归代码通常比迭代代码更简洁易读，能更直接地表达复杂问题的逻辑。

2. 自然表达：

   • 二叉树的构建和遍历自然适合递归方法，因为递归在某种角度来说与树的结构相辅相成。

递归的缺点

但是使用递归就会有一些缺点浮现。

• 递归可能导致大量函数调用，从而增加系统资源的消耗（如栈空间）。
• 如果没有适当地控制递归深度，可能会导致栈溢出（stack overflow）。

但总的来说，由于树的结构并不是特别复杂，并且往往调用的函数是其本身，其缺点也就微不足道了。

接下来我们就对二叉树的一系列操作进行解析。

二叉树定义

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

1
2
3
4
5
6
7
8

二叉树的创建和存储

二叉树可以使用数组和链表两种形式来进行存储，但是针对二叉树的特点，只有满二叉树或者完全二叉树适合使用数组存储。其他形式的树用数组存储反而会浪费空间，所以我们使用链表存储。

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)  
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

计算树的深度

这里我们使用三位运算符可以更加直观和简短地计算树的深度

int TreeHeight1(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = TreeHeight(root->left);//左子树的高度
	int right = TreeHeight(root->right);//右子树的高度
	return left > right ? left + 1 : right + 1;//当前树的高度=左右子树最大值+1
}

1
2
3
4
5
6
7
8
9
10
11

遍历

对于二叉树的遍历，这其中大有说法。
同时它也是递归思想的经典案例，我们进行仔细分析。

我们知道树的结构，从结点来看，二叉树可以看作父亲结点、左孩子结点、右孩子结点，我们需要获得孩子节点只需要直接指向它的左孩子结点或者右孩子结点即可；而从横面来看，二叉树是具有层数的，每一层的结点数都与2的倍数有关；

那么我们要遍历所有的结点的时候，我们就衍生出了三种不同的遍历方法，它们的不同是根据访问父结点的顺序来决定的：前序遍历（先序遍历）、中序遍历、后序遍历。举个例子，先序遍历就是最先访问父结点，再访问左孩子结点，最后访问右孩子结点。
鉴于递归的特点，当我们访问孩子结点的时候，又可以将其再作为一个父节点，从而再去访问它的孩子结点，一直递归下去，直到遍历完所有的结点。
接下来我们分别编写三种遍历的代码。

先序遍历：父节点->左孩子结点->右孩子结点

//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11

中序遍历：左孩子结点->父节点->右孩子结点

//中序遍历
void MidOrder(BTNode* root)
{
	if (root == NULL) 
	{
		return;
	}
	MidOrder(root->left); 
	printf("%d ", root->data);
	MidOrder(root->right);  
}
1
2
3
4
5
6
7
8
9
10
11

后序遍历：左孩子结点->右孩子结点->父节点

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)  
	{
		return;
	}
	PostOrder(root->left);  
	PostOrder(root->right); 
	printf("%d ", root->data);
}
1
2
3
4
5
6
7
8
9
10
11

通过上述的代码我们其实可以发现，printf("%d ", root->data);这个语句实际上就是父节点的位置，而PostOrder(root->left); 和PostOrder(root->right); 就是左孩子结点和右孩子结点的分别位置。从书面上来看，使用递归的写法使得代码十分简洁易懂，并且具有很强的逻辑性帮助理解二叉树的本质。

你以为遍历就这么完了吗？其实并没有。我们来看一个例子。

现在请你根据这个二叉树写出它中序遍历之后的排列顺序。

你以为的：中序遍历就是按照左->父->右的顺序直接遍历就行了，

H->D->I->B->E->A->F->C->G
1

但是很遗憾，这样写是错的。因为空结点NULL也是结点，我们不能忽视它。

你再以为的：既然空结点也是结点，那只需要将E、F、G的左右孩子结点（即空结点）也表示出来即可。

H->D->I->B->NULL->E->NULL->A->NULL->F->NULL->C->NULL->G->NULL
1

但是很遗憾，这样写也是错的。你忽视掉了H和I。

实际上的：

NULL->H->NULL->D->NULL->I->B->NULL->E->NULL->A->NULL->F->NULL->C->NULL->G->NULL
1

据此我们可以知道的是，遍历的时候我们不能忽视空结点。在实际解决的时候我们需要先访问所有的结点，如果访问完某个结点为空才可以跳过它去访问下一个结点，而不是忽略空结点。

除了以上三种遍历以外，还有一种遍历方法，这种方式是直接一层一层地进行遍历，也叫做层序遍历。

层序遍历：第一层->第二层->第三层->…->第n层

//层序遍历
//思路：首先建一个队列，根节点入队，然后出队，打印队首元素，左右子树入队，直到队列为空
void LevelOrder(BTNode* root)
{
	Queue q;//首先建一个队列
	QInit(&q);//初始化队列
	if (root == NULL)
	{
		return NULL;
	}
	if (root)
	{
		QPush(&q, root);//根节点入队
	}
	while (!QEmpty(&q))//队列不为空
	{
		BTNode* front = QFront(&q);//队首元素
		printf("%d ", front->data);//打印队首元素
		if (front->left) //左子树入队
		{
			QPush(&q, front->left);
		}
		if (front->right) //右子树入队
		{
			QPush(&q, front->right);
		}
	}
	QDestroy(&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

销毁二叉树

//销毁二叉树
void DestroyTree(BTNode* root)
{
	if (root == NULL)
		return;
	DestroyTree(root->left);
	DestroyTree(root->right);
	free(root);
}
1
2
3
4
5
6
7
8
9

以上仅仅是对二叉树典型概念和用法的大致讲解，实际上二叉树涉及到的内容还有很多，例如线索二叉树的构建、树与二叉树之间的转换等等，而这些概念将会在后续的补充中分开进行讲解。