【数据结构】从树到二叉树

一. 前言

好久好久没有发文了，这一个月来饱受流感、考试、实践周的折磨，好在终于顺利结束，可以安心学习写文章了（不得不说欠了好多篇qwq）

回顾一下前面几期，我们学习了数据结构中的顺序表、链表、栈和队列，它们有个共同的特点：都是线性的数据结构。而接下来，我们要学习一种非线性的数据结构——》二叉树

想必二叉树这个名字各位或多或少都有听说过，真是久仰大名了。而在学习树之前，我们要先来学习一下树，从对树基本概念的学习逐步过渡到二叉树的学习。

废话少说，上菜！！！

二. 树的概念及结构—-凉拌海带

2.1 什么是树

在上大餐前，我们先来一盘小菜来开开胃—->

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。如下（左图：现实中的树；右图：数据结构中的树）：

一颗树具有以下几个特点：

每颗树有一个唯一的特殊节点，称作根结点，根节点没有前驱结点，上面的A就是根结点。
除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱结点，可以有0个或多个后继结点。
由此可见，树可以看作”根节点”+n个子树组成，而每个子树又可以看作”根节点”+n个子树组成。即树是递归定义的。

2.2 树的基本术语

我们结合下面一张图来理解一些树的常见术语：

**树的常见术语（树+人类亲缘关系描述）**
术语	解释
节点的度	一个节点含有的子树的个数称为节点的度。例如：A有6颗子树，A节点的度为6。
叶子节点/终端节点	度为0的节点称为叶子节点。例如：B、C、H、I…为叶子节点
分支节点/非终端节点	度不为0的节点称为分支节点。例如：D、E、F、G…为分支节点
父节点/双亲结点	如果一个节点含有子节点，则这个节点称为其子节点的父节点。例如：A是B的父节点
子节点/孩子节点	一个节点含有的子树的根节点称为该节点的子节点。例如：B是A的孩子节点
兄弟节点	具有相同父节点的节点互称为兄弟节点。例如：B、C是兄弟节点；H、I不是兄弟节点，它们的父节点不同
树的度	一棵树中，最大的节点的度称为树的度；如上图：树的度为6
节点的层次	从根开始定义起，根为第1层，根的子节点为第2层，以此类推（特别说明：也有地方将根作为第0层）
树的高度/深度	树中节点的最大层次；如上图：树的高度为4（根为第1层）
堂兄弟节点	双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先	从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先、H的祖先有D、A
子孙	以某节点为根的子树中任一节点都称为该节点的子孙；如上图：所有节点都是A的子孙、J的子孙有P、Q
森林	由m（m>0）棵互不相交的树的集合称为森林；

2.3 树的表示

树是一种非线性结构，相对于线性表，树要存储表示起来就比较复杂了。不仅要保存当前结点的值，也要保存结点和结点之间的关系(亲缘关系)。实际中树有很多种表示方式，例如：双亲表示法（结点的指针指向双亲），孩子表示法（结点的指针指向孩子）、孩子双亲表示法（二者混合）以及孩子兄弟表示法（下面介绍）等。我们这里就简单的了解其中最常用的孩子兄弟表示法。以下是孩子兄弟表示法的结构体和图例：

//孩子兄弟表示法
typedef int DataType;
struct Node
{
    struct Node* Child; // 第一个孩子结点
    struct Node* Brother; // 指向其下一个兄弟结点
    DataType _data; // 结点中的数据域
};

其中Child指针域指向第一个孩子结点，Brother指针域指向其下一个兄弟结点。通过这种方式，我们不仅可以有效解决孩子表示法中孩子指针的个数无法合理控制的问题，还能很好地表示出每个结点之间的关系。
1、已知B结点，需要找到F结点：只需通过B结点的Child指针找到D，然后再通过D的Brother指针找到E，最后通过E的Brother指针找到F即可。
2、已知A结点，需要知道G结点的信息：通过A结点的Child指针找到C，然后再通过B的Brother指针找到C，最后通过C的Child指针找到G即可。

2.4 树在实际生活中的应用

我们电脑上的文件目录就是一种树形结构，下面是Linux系统下的目录结构（‘\’表示根目录）：

而Windows系统下有多个盘符（C盘、D盘…），盘符之间相互独立。如果把每个盘符的目录结构看作一颗树，Windows系统下的目录结构就是一片森林：

二. 二叉树的概念及结构—-扬州炒饭

品完小菜，就该端上我们的主食了—->

2.1 什么是二叉树

我们规定二叉树就是一颗度不大于2的树。我们上面说到树是由根结点和多颗子树构成的，二叉树就是由根结点和别名为左子树、右子树的两颗树组成。下面就是一颗二叉树：

从上图我们可以看出：
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
对于任意的二叉树都是由以下几种情况复合而成的：

2.2 二叉树两种特殊形式

1.满二叉树

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

2.完全二叉树

完全二叉树是一种效率很高的数据结构。对于深度为K，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。注意：满二叉树是一种特殊的完全二叉树。

2.3 二叉树的性质

1、若规定根结点的层数为1，则一颗非空二叉树上的第i层最多有 $2^{i-1}$ 个结点。
2、若规定根结点的层数为1，则一颗深度为h( $h\geq 1$ )的二叉树最多有 $2^{h}-1$ 个结点（满二叉树）。
3、对于任何一颗二叉树，如果度为0的结点有 $n_{0}$ 个，度为2的结点有 $n_{2}$ 个，则有 $n_{0}= n_{2}+1$ 。
4、若规定根结点的层数为1，则具有n个结点的满二叉树的深度 $h= \log_{2}(n+1)$ 。
5、对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点有：
        1. 若i>0，则i位置节点的双亲序号为 $\left \lfloor (i-1)/2 \right \rfloor$ （表示向下取整）
2. 若i=0，则i为根节点编号，无双亲节点
        3. 若2i+1<n，则左孩子序号为2i+1，否则无左孩子
        4. 若2i+2<n，则右孩子序号为2i+2，否则无右孩子

2.4 二叉树的存储结构

二叉树的存储结构一般分为两种：顺序存储和链式存储。

1. 顺序存储

顺序结构存储就是使用数组来存储，利用下标表示结点之间的关系(性质5)。一般使用数组只适合表示完全二叉树，因为不是完全二叉树则会造成空间浪费。而现实中使用中只有堆(一种完全二叉树)才会使用数组来存储，关于堆我们放到后面的篇章专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。如下：

2. 链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用指针来指示每个结点的逻辑关系。链式结构又分为二叉链和三叉链。二叉链就是除了数据域，链表中还有两个指针域，分别用来指向该结点的左孩子和右孩子的存储地址，目前我们用到的基本都是二叉链。而所谓三叉链就是在二叉链的基础上再增加一个指针域指向该结点的父亲结点的存储地址，一些更复杂的数据结构如红黑树将会用到三叉链。图示如下：

代码表示如下：

typedef int BTDataType;

//二叉链表表示
struct BinaryTreeNode
{
	BTDataType _data; // 当前结点数据域
	struct BinaryTreeNode* _pLeft; // 指向当前结点左孩子
	struct BinaryTreeNode* _pRight; // 指向当前结点右孩子
};

//三叉链表表示
struct BinaryTreeNode
{
	BTDataType _data; // 当前结点数据域
	struct BinaryTreeNode* _pLeft; // 指向当前节点左孩子
	struct BinaryTreeNode* _pRight; // 指向当前结点右孩子
    struct BinaryTreeNode* _pParents; // 指向当前结点双亲
};

三. 链式二叉树基本操作—-红烧猪脚

3.1 温故而知新

在学习二叉树各种各样的操作、品尝大鱼大肉前，我们先来回顾一下二叉树的概念：

二叉树是度不超过2的树，由根结点和左右2个子树组成，每个子树也可以看作一颗二叉树，又可以拆分为根结点和左右两颗子树……

是不是很熟悉，一个大问题可以拆分为两个子问题，每个子问题又可以拆分为更小的子问题，这样层层拆分到不可拆分（遇到空树）的过程，不就是递归吗！因此，我们可以得出：
树是递归定义的，后续树的各种操作正是围绕着这一点进行的。

3.2 二叉树的遍历

我们先从最简单的操作—-遍历学起。所谓二叉树遍历(Traversal)就是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个节点有且只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。二叉树的遍历分为四种：前序遍历、中序遍历、后序遍历和层序遍历。

1.前序遍历

前序遍历（Preorder Traversal）又称先根遍历，即先遍历根结点，再遍历左子树，最后遍历右子树。而对于子树的遍历，也服从上述规则。利用递归，我们可以很快地写出代码：

//前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
    //遇到空树，递归终点
	if (root == NULL)
		return;

    //对根节点进行操作（此处为打印）
	printf("%c ", root->_data);

    //递归遍历左子树
	BinaryTreePrevOrder(root->_left);

    //递归遍历右子树
	BinaryTreePrevOrder(root->_right);
}

为了更好地理解这个过程，我们可以画出递归展开图如下：

2.中序遍历

中序遍历（Inorder Traversal）又称中根遍历，即先遍历左子树，再遍历根结点，最后遍历右子树。同样，子树的遍历规则也是如此。递归代码如下：

//中序遍历
void BinaryTreeInOrder(BTNode* root)
{
    //遇到空树，递归终点
	if (root == NULL)
		return;

    //递归遍历左子树
	BinaryTreeInOrder(root->_left);
    
    //对根节点进行操作（此处为打印）
	printf("%c ", root->_data);

    //递归遍历右子树
	BinaryTreeInOrder(root->_right);
}

3.后序遍历

后序遍历（Inorder Traversal）又称后根遍历，即先遍历左子树，再遍历右子树，最后遍历根结点。照葫芦画瓢，递归代码如下：

//后序遍历
void BinaryTreePostOrder(BTNode* root)
{
    //遇到空树，递归终点
	if (root == NULL)
		return;

    //递归遍历左子树
	BinaryTreePostOrder(root->_left);

    //递归遍历右子树
	BinaryTreePostOrder(root->_right);

    //对根节点进行操作（此处为打印）
	printf("%c ", root->_data);
}

4.层序遍历

除了上面的前中后序遍历，还可以对二叉树进行层序遍历。所谓层序遍历就是从所在二叉树的根节点出发，首先访问第1层的根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推。这样自上而下，自左向右逐层访问树的结点的过程就是层序遍历。

与前面三种遍历不同，层序遍历属于广度优先遍历，因此我们可以利用队列先进先出的特性，将每个结点一层一层依次入队，然后依次出队进行操作即可。具体演示及代码如下：

//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
    //先定义一个队列
	Queue que;
	QueueInit(&que);
    //根结点(第一层)入队
	if (root)
    {
		QueueInsert(&que, root);
    }
	while (!QueueEmpty(&que))//队列为空说明遍历完毕
	{
        //遍历队头结点，然后出队
		BTNode* front = QueueFront(&que);
		QueueErase(&que);
		printf("%c ", front->_data);
        //将下一层的非空结点入队
		if (front->_left != NULL)
		{
			QueueInsert(&que, front->_left);
		}
		if (front->_right != NULL)
		{
			QueueInsert(&que, front->_right);
		}
	}
	printf("\n");
	QueueDestroy(&que);
}

四种遍历方式结果如下所示：

3.3 二叉树的结点个数

1.二叉树的总结点数

一颗二叉树的结点数我们可以看作是根结点+左子树结点数+右子树结点数，那左右子树的结点数又是多少呢？按照相同的方法继续拆分，层层递归直到左右子树为空树，返回空树的结点数0即可。递归代码如下：

//二叉树的结点个数
int BinaryTreeSize(BTNode* root)
{
    //递归终点，空树返回0
	if (root == NULL)
	{
		return 0;
	}
    //结点数为1(根结点)+左子树结点数+右子树结点数
	return 1 + BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right);
}

2.二叉树的叶子结点数

左右子树都为空的结点即是叶子结点。这里分为两种情况：左右子树都为空和左右子树不都为空。

1、当左右子树都为空时，则这颗树的叶子结点数为1(根节点)。

2、当左右子树不都为空，即根结点不是叶子结点时，这棵树的叶子结点数就为左子树叶子结点数+右子树叶子结点数（空树没有叶子结点）。

递归代码如下：

//二叉树的叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{
    //空树叶子结点为0，返回
	if (root == NULL)
	{
		return 0;
	}
    
    //左右子树都为空，此树有且只有一个叶子结点(根结点)
	if (root->_left == NULL && root->_right == NULL)
	{
		return 1;
	}
    
    //根为分支结点，返回左右子树的叶子结点数之和
	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}

3.二叉树第k层结点数

类似的，一颗树第k层的结点数我们可以拆分为其左子树第k-1层结点+右子树第k-1层结点。这样层层递归下去，直到k==1求树的第1层结点数时返回1(树的第1层只有根结点)，而如果在递归过程中遇到空树就返回0(空树没有结点)。例如下面一颗树：

递归代码如下：

//求第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
    //为空树，无结点，返回0
	if (root == NULL)
	{
		return 0;
	}
    //第1层只有根结点，返回1
	if (k == 1)
	{
		return 1;
	}
    //k不为1，返回左子树k-1层结点个数+右子树k-1层结点个数
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}

结果如下所示（以上图的二叉树为例）：

3.4 二叉树的高度/深度

树中结点的最大层次称为二叉树的高度。因此，一颗二叉树的高度我们可以看作是

1(根结点)+左右子树高度的较大值。层层递归下去直到遇到空树返回0即可，递归代码如下：

//二叉树的高度
int BinaryTreeHeight(BTNode* root)
{
    //空树返回0
	if (root == NULL)
	{
		return 0;
	}
    //求左右子树的高度
	int LeftHeight = BinaryTreeHeight(root->_left);
	int RightHeight = BinaryTreeHeight(root->_right);
    //二者较大值+1即为当前树的高度
	return max(LeftHeight, RightHeight) + 1;
}

3.5 二叉树的查找

二叉树的查找本质上就是一种遍历，只不过是将之前的打印操作换为查找操作而已。我们可以使用前序遍历来进行查找，先比较根结点是否为我们要查找的结点，如果是，之间返回；如果不是，遍历左子树和右子树，返回其查找的结果；如果都找不到，返回空指针。代码如下：

//二叉树的查找
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    //为空树，找不到，返回空指针
	if (root == NULL)
	{
		return NULL;
	}
    //根为要找的结点，返回根结点地址
	if (root->_data == x)
	{
		return root;
	}
    //查找左子树
	BTNode* ret1 = BinaryTreeFind(root->_left, x);
	if (ret1)
	{
        //找到了，返回结点地址
		return ret1;
	}
    //左子树找不到，查找右子树
	BTNode* ret2 = BinaryTreeFind(root->_right, x);
	if (ret2)
	{
		return ret2;
	}
    //都找不到，返回空指针
	return NULL;
}

3.6 二叉树的创建和销毁

最后，我们再来看看如何来创建和销毁一颗二叉树。我们前面说过：二叉树是递归定义的。有了前面的基础，二叉树的创建和销毁也就不是什么难事了。

1.二叉树的创建

需求：给定一个字符串“ABD###CE##F##”代表二叉树的前序遍历序列，其中#代表空，其余字符代表每个结点的值。要求根据此序列创建一颗二叉树。

方案：既然是前序遍历的序列，那么我们就采用前序遍历来创建树，遍历执行的操作就是创建结点。先创建根结点，然后创建左子树，最后创建右子树。此外，我们还需要一个变量来标识当前需要创建的结点的值，这个变量必须是指针，因为如果是简单的传递整形变量，由于形参的改变并不会影响实参，上一次递归调用对变量的修改并不会影响下一次递归的结果。具体代码如下：

//创建一个值为x的结点
BTNode* BuyTreeNode(BTDataType x)
{
	BTNode* ret = (BTNode*)malloc(sizeof(BTNode));
	ret->_data = x;
	ret->_left = NULL;
	ret->_right = NULL;
	return ret;
}

//根据前序序列递归建树
//a：前序序列  n：字符串的长度  pi：指向 当前需要创建的字符下标 的指针
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
    //所有结点创建完毕，返回NULL
	if (*pi == n)
	{
		return NULL;
	}
    //当前要创建的结点不为空
	if (a[*pi] != '#')
	{
        //创建根结点
		BTNode* newnode = BuyTreeNode(a[*pi]);
		(*pi)++;//指向下一位置
        //创建左子树
		newnode->_left = BinaryTreeCreate(a, n, pi);
        //创建右子树
		newnode->_right = BinaryTreeCreate(a, n, pi);
        //树创建完毕，返回根结点指针
		return newnode;
	}
	else //要创建的结点为空
	{
        //指向下一位置并直接返回NULL指针即可
		(*pi)++;
		return NULL;
	}
}

注意事项：
1、给出的遍历序列必须是对空结点进行补全的序列，否则仅凭一种序列无法确定唯一的二叉树。
2、使用#号补全的前序遍历可以确定唯一的二叉树。
3、仅仅使用中序遍历无法确定唯一的二叉树，因此在不带附加条件的情况下不能仅凭中序遍历创建二叉树
4、如果给出的是后序遍历，2则不能利用上述前序递归的思想来创建二叉树，原因是父结点都没有被创建怎么创建左右子树？

2.二叉树的销毁

对于二叉树的销毁，我们一般采用后序遍历的方式进行销毁，即先销毁左子树，再销毁右子树，最后销毁根结点。因为如果采用前序或者中序遍历，销毁根结点后就找不到左右子树了，还需事先保存左右孩子的地址，比较麻烦。在此情景下，遍历结点进行的操作就是销毁操作。具体代码如下：

//二叉树的销毁
void BinaryTreeDestory(BTNode** root)
{
	assert(root);
	//空结点，直接返回
	if (*root == NULL)
	{
		return;
	}
    //销毁左子树
	BinaryTreeDestory(&((*root)->_left));
    //销毁右子树
	BinaryTreeDestory(&((*root)->_right));
    //销毁根结点
	free(*root);
    //置空，避免野指针
	*root = NULL;
}

以上，就是本期的全部内容啦🌸

制作不易，能否点个赞再走呢🙏

文章出处登录后可见！

已经登录？立即刷新