数据结构——二叉树

前言

        在学习二叉树之前，我们要先学习树的概念。在我们之前学过的顺序表和链表的线性结构中，数据是“一个接一个”排列的，但在现实世界里，很多事物之间的关系并非如此简单。比如，一个家庭的族谱、电脑里的文件系统等，它们都呈现出一种“一对多”的层次关系。为了高效地表示和处理这些数据，树形结构应运而生，而二叉树则是其中最基础、最经典的一种。同时，掌握二叉树不仅是学习后续更复杂数据结构（如红黑树、B树）的基础，也是理解许多算法（如排序、搜索）的关键。

本文将从基础概念出发，深入探讨二叉树的性质、实现方式、遍历算法以及实际应用场景。

一. 树（Tree）

1.1 树的概念与结构

1.1.1 树的概念

树是一种非线性的数据结构，它是由 n（n>=0）个有限节点节点组成的一个具有层次关系的集合。因为它很像一棵倒挂的树，所以称它为树。也就是说它是根朝上，而叶朝下的。

1.1.2 树的结构特点

• 有一个特殊的结点，称为根结点，根结点没有前驱结点。
• 除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每⼀个集合 Ti（1 <= i <= m）是⼀棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有 0 个或多个后继。因此，树是递归定义的。

注：树形结构中，子树不能有交集，否则就不是树形结构

1.2 树的常用术语

• 父节点/双亲节点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点
• 子节点/孩子节点：一个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点
• 节点的度：一个结点有几个孩⼦，他的度就是多少；比如A的度为6，K的度为0 
• 树的度：一棵树中，最⼤的结点的度称为树的度；如上图：树的度为 6 
• 叶子节点/终端节点：度为 0 的结点称为叶结点；如上图： B、C、H、I... 等结点为叶结点
• 分支节点/非终端节点：度不为 0 的结点；如上图： D、E、F、G... 等结点为分支结点
• 兄弟节点：具有相同父结点的结点互称为兄弟结点(亲兄弟)；如上图： B、C 是兄弟结点
• 节点的层次：从根开始定义起，根为第 1 层，根的子结点为第 2 层，以此类推
• 树的高度/深度：树中结点的最大层次；如上图：树的高度为 4 
• 节点的祖先：从根到该结点所经分支上的所有结点；如上图： A 是所有结点的祖先
• 路径：一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列；比如A到Q的路径为： A-E-J-Q；H到Q的路径H-D-A-E-J-Q 
• 子孙：以某结点为根的⼦树中任⼀结点都称为该结点的子孙。如上图：所有结点都是A的⼦孙
• 森林：由 m（m>0） 棵互不相交的树的集合称为森林

1.3 树的表示

树结构相对线性表就比较复杂了，既要保存值域，又要保存节点和节点之间的关系，实际树中有很多表示方式，比如：双亲表示法、孩子表示法、孩子双亲表示法、以及孩子兄弟表示法。这里我们就简单了解一下其中最常用的孩子兄弟表示法

struct TreeNode{
    struct Node* child;  // 左边开始的第⼀个孩⼦结点 
    struct Node* birther;// 指向其右边的下⼀个兄弟结点 
    int data;             // 结点中的数据域 
};

1.4 树型结构的实际运用场景

1.文件系统管理

计算机的文件系统是树结构的典型应用。

• 根目录相当于树的根节点，各级文件夹相当于中间节点，而具体的文件则相当于叶子节点。
• 例如 Windows 系统中，“此电脑” 是根节点的一种体现，其下的 C 盘、D 盘等是子节点，每个磁盘下又有各种文件夹和文件，形成了清晰的树状层级结构，方便用户对文件进行组织、查找和管理。

2.数据库索引

在数据库中，为了提高查询效率，常使用树结构作为索引，其中 B 树和 B + 树是比较常用的。

• B 树的每个节点可以存储多个关键字，并且具有平衡性，能够减少磁盘 I/O 操作，加快数据的查找速度。
• B + 树是 B 树的一种变体，所有的叶子节点通过指针连接在一起，更适合范围查询。在关系型数据库中，很多索引结构都是基于 B + 树实现的，比如 MySQL 的 InnoDB 存储引擎中的主键索引

3.搜索引擎中的倒排索引与树结构

搜索引擎在处理用户查询时，会用到多种数据结构，树结构也发挥着重要作用。

• 倒排索引是搜索引擎的核心数据结构之一，它将关键词映射到包含该关键词的文档集合。为了提高关键词的查询效率，通常会对关键词进行排序，并使用二叉搜索树、B 树等结构来存储，以便快速定位到相关的文档。
• 此外，搜索引擎的网页排名算法中，也可能涉及到树结构的应用，如通过树来表示网页之间的链接关系，计算网页的重要性

4.决策树

在机器学习和数据挖掘领域，决策树是一种常用的分类和回归算法。

• 决策树的每个内部节点代表一个特征的判断条件，每个分支代表一个判断结果，叶子节点代表最终的分类或回归结果。
• 例如，在预测客户是否会购买某产品时，可以根据客户的年龄、收入、消费习惯等特征构建决策树，通过对这些特征的逐层判断，最终得出预测结果。决策树具有易于理解和解释的特点，广泛应用于金融、医疗、营销等领域。

5.路由算法中的树结构

在计算机网络中，路由算法用于确定数据包从源节点到目标节点的传输路径，树结构在其中也有应用。

• 例如，生成树协议（STP）用于在局域网中消除环路，它会构建一棵无环的生成树，使数据包能够沿着树的路径进行传输，避免了数据包在环路中无限循环的问题。
• 此外，在一些路由算法中，会根据网络拓扑构建路由树，通过树的层级关系来计算最短路径。

二. 二叉树（Binary Tree）

2.1 二叉树的概念与结构

二叉树是由 n（n>=0） 个节点组成的有限集合，它有以下几种情况：

• 当 n=0 时，它是一棵空二叉树。​
• 当 n>0 时，有且仅有一个特定的称为根的节点，其余节点可分为两棵互不相交的、分别称为根的左子树和右子树的二叉树。
• 二叉树不存在度大于2的节点，并且子树有左右之分，次序不能颠倒，因此二叉树是有序树

二叉树具备以下结构特点：

• 空树也是二叉树
• 二叉树不存在度大于2的节点
• 二叉树的子树有左右之分，次序不能颠倒，即使一个节点只有一棵子树，也要区分是左子树还是右子树，因此二叉树是有序树

对于任意二叉树都是由以下几种情况复合而成的

2.2 特殊结构的二叉树

2.2.1 满二叉树

1）定义

一个二叉树，如果每一层的节点都达到最大值，则这个二叉树是满二叉树。也就是说，如果一个二叉树的层数为 K ，且结点总数是 2^k - 1 ，则它就是满二叉树。

2）性质

• 若规定根节点的层数为1，则满二叉树第 h 层节点个数为 2^(h - 1)
• 若规定根节点的层数为1，则深度为 h 的满二叉树总的节点个数为 2^h - 1
• 若规定根节点的层数为1，具有 n 个节点的满二叉树的深度 h = log2(n + 1)

2.2.2 完全二叉树

1）定义

若设二叉树的深度为h，除第h层外，其它各层（1到h−1）的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，即为完全二叉树。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时，也称之为完全二叉树。

2）性质

• 叶子结点只可能在最大的两层（即最下面的两层）上出现。
• 对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L或L+1。（即除最后一层之外其它层全部被填满，最后一层节点从左到右一次排列，没有空隙）
• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

二叉树的性质（根据满二叉树引申）

• 若规定根节点的层数为1，则二叉树第 h 层节点个数最多为 2^(h - 1)
• 若规定根节点的层数为1，则深度为 h 的二叉树总的节点个数最多为 2^h - 1
• 若规定根节点的层数为1，具有 n 个节点的满二叉树的深度 h = log2(n + 1)（log以2为底，n+1的对数）

2.3 二叉树的存储结构

2.3.1 顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构存储。

2.3.2 链式结构

二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来表示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链。（本篇主要介绍二叉链）

三. 顺序结构二叉树的实现

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，具备二叉树特性的同时，还具备其他特性。

3.1 堆的概念和结构

如果有一个关键码的集合 K = {k0 , k1 , k2 , ...，kn−1 }，把它的所有元素按完全二叉树的顺序存储方式存储，在一个一维数组中，并满足：Ki <= K2∗ i+1（Ki >= K2∗ i+1 且 Ki >= K2∗i+2 ), i = 0、1、2... ，则称为小堆(或大堆)。根结点最小的堆叫做最小堆或小根堆（即子节点大于父节点），将根结点最大的堆叫做最大堆或大根堆（即父节点大于子节点，但左右兄弟节点的大小不确定）。

堆结构具有以下结构特性：

• 堆中某个节点总是不大于（大堆）或不小于（小堆）其父节点的值
• 堆是一棵完全二叉树（除最后一层之外其它层全部被填满，最后一层节点从左到右一次排列，没有空隙）

用堆实现完全二叉树的性质：

• 对于 n 个节点的完全二叉树，如果按照从上至下、从左指右的数组顺序堆所有节点从0开始编号对于序号为 i 的节点：

1. 若 i >0，i 位置节点的双亲序列号：(i - 1) / 2 ；若 i = 0，i 为节点编号，无双亲节点
2. 若 2i + 1 < n ，左孩子序号：2i + 1 ，2i + 1 >= n ，否则无左孩子
3. 若 2i + 1 > n ，右孩子序号：2i + 2 ，2i + 2 >= n ，否则无左孩子

3.2 堆的实现

3.2.1 堆结构的定义，初始化，销毁和堆中数据的打印

//定义堆的结构（底层为数组）
typedef int HPDataType;
typedef struct Heap {
	HPDataType* arr;
	int size;
	int capacity;
}HP;

//初始化
void HPInit(HP* php)
{
	php->arr = NULL;
	php->size = php->capacity = 0;
}
//销毁
void HPDestory(HP* php)
{
    //申请了哪些空间，销毁时就要释放
	if (php->arr)
		free(php->arr);
	php->arr = NULL;
	php->size = php->capacity = 0;
}
//打印
void HPPrint(HP* php)
{
	assert(php);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->arr[i]);
	}
	printf("\n");
}

3.2.2 向上调整算法

• 先将元素插入到堆的末尾,即最后一个孩子之后
•  插入之后如果堆的性质遭到破坏，将新插入结点顺着其双双亲往上调整到合适位置即可

//向上调整算法 O(n*logn)
//知道子节点，求父节点
//parent = (child - 1) / 2;
void AdjustUp(HPDataType* arr, int child)
{
	assert(arr);
	int parent = (child - 1) / 2;
	//建小堆
	while (child > 0)
	{
		//建小堆 <
		//建大堆 >
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

3.2.3 向下调整算法

• 将堆顶元素与堆中最后一个元素进行交换 
• 删除堆中最后一个元素
• 将堆顶元素向下调整到满足堆特性为止

//向下调整算法 O(n)
//知道父节点，求子节点
//左孩子：child = 2 * parent + 1 
//右孩子：child = 2 * parent + 2
void AdjustDown(HPDataType* arr, int parent, int n)
{
	assert(arr);
	int child = 2 * parent + 1;
	while (child <= n)
	{
		//建小堆：<
		//建大堆：>
		if (child + 1 <= n && arr[child + 1] < arr[child])
		{
			child = child + 1;
		}
		//建小堆：>
		//建大堆：<
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else {
			break;
		}
	}
}

3.2.4 入堆，交换

• 入堆前要判断空间是否足够
• 向堆的末尾插入数据后，堆的结构可能遭到破坏，因此要用向上调整算法将其至于合适的位置

//交换
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//入堆
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//空间不够
	if (php->size == php->capacity)
	{
		//扩容
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr,sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newcapacity;
	}
	//空间足够
	php->arr[php->size] = x;
	//向上调整
	AdjustUp(php->arr, php->size);
	//先调整，后++
	php->size++;
}

3.2.5 出堆，判空，交换

• 出堆前要判断堆是否为空，若为空，则无法出堆
• 出堆时要从堆顶出（先将堆顶与堆的最后一个元素交换，然后size--），然后用向下调整算法将新的堆顶元素与子节点比较，交换位置，直到重新满足堆序性。

为什么要从堆顶删除元素呢？

1. 堆顶元素一定是当前堆中的极值，快速获取或删除“当前极值”能满足许多场景的需求
2. 从堆顶删除后，可利用向下调整算法高效维护堆的结构
3. 符合堆的设计目标：高效处理极值操作

//判空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

//交换
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//出堆
void HPPop(HP* php)
{
    //堆中有数据才能出队，因此要先判空
	assert(!HPEmpty(php));
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->arr[php->size--];
	//向下调整
	AdjustDown(php->arr, 0, php->size - 1);
}

3.2.6 取堆顶，堆中有效数据个数

//取堆顶
HPDataType HPTop(HP* php)
{
	assert(!HPEmpty(php));
	return php->arr[0];
}

//堆有效数据个数
int HPSize(HP* php)
{
	assert(php);
	return php->size;
}

3.3 堆的应用——堆排序

堆排序——借助数据结构“堆”（注：这不是真正意义上的堆排序）

//堆排序——借助数据结构-堆（这不是真正意义上的堆排序）
void HeapSort01(int* arr, int n)
{
	HP hp;
	HPInit(&hp);
	for (int i = 0; i < n; i++)
	{
		HPPush(&hp, arr[i]);
	}
	int i = 0;
	//循环出堆顶
	while (!HPEmpty(&hp))
	{
		int top = HPTop(&hp);
		arr[i++] = top;
		HPPop(&hp);
	}
	HPDestory(&hp);
}

堆排序——使用堆结构的思想（真正意义上的堆排序）

//堆排序——使用的堆排序的思想
//乱序数组建堆可以用向上调整算法，也可以用向下调整算法
//交换之后必须用向下调整算法
void HeapSort(int* arr, int n)
{

    //排升序建大堆，排降序建小堆  

  //（1）用向下调整算法将乱序数组建堆
  //先从最小的一棵子树开始调整（从下到上，从右到左）（即最后一个节点的父节点）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n - 1);
	}
  //（2）用向上调整算法将乱序数组建堆
  //先从最大的一棵子树开始调整（从上到下，从左到右）（即根节点的左子树）
  //for (int i = 1; i < n; i++)
  //{
  //  	AdjustUp(arr, i);
  //}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end - 1);
		end--;
	}
}

四. 链式结构二叉树的实现（注：结合注释理解）

用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址， 其结构如下：

//定义链式结构二叉树
typedef char BTDataType;
typedef struct BinaryTreeNode {
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

4.1 二叉树的遍历

4.1.1 深度优先遍历

/前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

4.1.2 广度优先遍历

//层序遍历
//将根节点保存在队列中，是队列不为空
//循环判断队列是否为空，不为空取头，将不为空的孩子节点入队列
void LevelOrder(BTNode* root)
{
	Queue q;
	QInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，打印队头
		BTNode* front = QueueFront(&q);
		printf("%c ", front->data);
		QueuePop(&q);
		//队头节点不为空的孩子节点入队列
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}

	QueueDestory(&q);
}

4.2 节点个数及高度等

（注：部分方法用到了栈和队列的相关知识，如有不清楚可看我前面的文章）

4.2.1 二叉树节点个数

//⼆叉树结点个数 
//节点总数 == 1 + 左子树节点个数 + 右子树节点个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

4.2.2 二叉树叶子节点个数

//⼆叉树叶子结点个数
//没有左右孩子节点（即度为0）
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);
}

4.2.3 二叉树第 k 层节点个数

// ⼆叉树第k层结点个数 
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

4.2.4 二叉树的深度/高度

// 二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);
	//根节点+max（左子树高度，右子树高度）
	return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

4.2.5 二叉树查找值为 x 的节点

// 二叉树查找值为x的结点 
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}

4.2.6 二叉树销毁

// 二叉树销毁
//传地址形参的改变才能影响实参
void BinaryTreeDestory(BTNode** root)
{
	//后续遍历，一个一个销毁
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

4.3 判断是否为完全二叉树

//判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QInit(&q);
	//头节点入队列
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			//top取到空就直接出队列
			break;
		}
		//将队头节点的左右孩子入队列
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}
	//队列不为空，继续取队列中的队头
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			//不是完全二叉树
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}

总结

本文系统介绍了树和二叉树的基本概念、存储结构及实现方法，二叉树作为树形结构的基础，其思想可延伸至 B 树、红黑树等复杂结构，掌握本文内容对后续数据结构学习至关重要。

如有不足或改进之处，欢迎大家在评论区积极讨论，后续我也会持续更新数据结构相关的知识。文章制作不易，如果文章对你有帮助，就点赞收藏关注支持一下作者吧，让我们一起努力，共同进步！