＜ 数据结构 ＞ 树与二叉树

目录

1、树的概念及结构

        树的概念

        树的专有名词

        树的表示

        树在实际中的运用

2、二叉树的概念及结构

        概念

        现实中的二叉树

        特殊的二叉树

        二叉树的性质

        二叉树的存储结构

---

1、树的概念及结构

        树的概念

• 现实中的树：

• 数据结构中的树：

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

• 如图：

 特点：

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

注意：

1. 树形结构中，子树之间不能有交集，否则就不是树形结构。
2. 除了根结点外，每个结点有且仅有一个父结点。
3. 一颗N个结点的树由N-1条边。

• 如图：（下面两个都不是树）

        树的专有名词

• 专有名词：

1. 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
2. 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点
3. 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点
4. 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
5. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
6. 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
7. 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
9. 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
10. 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
11. 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
12. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
13. 森林：由m（m>0）棵互不相交的树的集合称为森林；
14. 最近公共祖先：距离某些结点最近的祖先，比如P和Q的最近公共祖先为J，K和F的最近公共祖先为F。结点本身也可以成为自己的祖先

•  拓展：

知晓了上述的专有名词后，接下来可以尝试计算下结点总数和边数的关系：

假设结点总数是n，那么边数就是n-1，如何算出来的呢？很明显，边就是连接各个结点的支架，如上图的黑色线条即是。再假设树的度为 x，由专有名词得知，树的度是最大节点的度的个数，设度为i的节点个数为ni，那么结点总个数就是这些结点的总和，即n=n0+n1+n2+n3+……+n(i-1)+n(i)

综上：

• 边数：n-1
• 结点总数：n=n0+n1+n2+n3+……+n(i-1)+n(i)

例题引入：

• 答案：C
• 解析：

设度为i的节点个数为ni, 该树总共有n个节点,则n=n0+n1+n2+n3。有n个节点的树的总边数为n-1条。根据度的定义,总边数与度之间的关系为n-1=0*n0+1*n1+2*n2+3*n3。根据题意：n3=2，n2=1，n1=2。联立两个方程求解,可以得到n0 = n2 + 2n3 + 1, n0=6，选C。

        树的表示

树结构相对线性表就比较复杂了，因为不知道孩子的数量。但如若知道树的度，那就很好定义了。

//假设指定树的度，可以直接定义
#define N 5
struct TreeNode
{
	int data;
	struct TreeNode* subs[N]; //指针数组，每个结点存5个
};

但是又有一个缺陷，既然树的度为5，但是你这样设定只会导致每个结点的度均为5，可实际上只要保证每个结点的度<=5即可，由此可见，此法开辟造成空间浪费。此外，如果不知道树的度，那么用上述方法定义就比较困难了，可以采用如下方案：

• 孩子兄弟表示法：

既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

//孩子兄弟表示法
typedef int DataType;
struct TreeNode
{
	struct TreeNode* firstChild1; // 第一个孩子结点
	struct TreeNode* pNextBrother; // 指向其下一个兄弟结点
	DataType data; // 结点中的数据域
};

• 画图演示其过程：

假设我们要表示如下的树：

物理结构如下：

也可以这样理解：

解释原理：

由上图代码图画演示及树的样子得知，根结点A是有B和C两个孩子的，永远让A的leftchild指向第一个孩子B，A的其它孩子C让B的兄弟指针去指向，C没有兄弟了，直接指向NULL。同理，B有3个孩子，让leftchild指针指向第一个孩子D，再让D的兄弟指针指向下一个E，以此类推……此法就很好的显示了一个结点有多少个孩子都无所谓，直接让父亲指向第一个孩子，剩下的孩子用孩子的兄弟指针链接起来。

        树在实际中的运用

• （表示文件系统的目录树结构）

2、二叉树的概念及结构

        概念

二叉树：度为2的树，一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空
2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

如图：

 从上图可以看出：

1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

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

        现实中的二叉树

看到这样的树，你说出的第一句话是啥？

是不是在感叹诸如怎么会有这么对称的树，甚至来一句国粹我都觉着还行哈哈……等学习了下文的“特殊二叉树”，你将会有新的认知。

        特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 2^k -1 ，则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

简单来说，满二叉树的每个结点的度均为2，满二叉树是完全二叉树的特殊情况。当深度为K时，完全二叉树就是在【1，k-1】层的区间内均为满二叉树，只有最后一层第K层不满，但是最后一层是从左往右连续的。图示：

 学到这，当再看到上图现实中的二叉树的时候，你是否能够来一句，wc！这不纯纯满二叉树吗。

        二叉树的性质

性质1：若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

性质2：若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h - 1 .

性质3：对任何一棵非空二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 ＝n2 ＋1

性质4：若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log2(N+1) . 

性质5：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

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

注：性质5的相关知识会在下面的存储结构中展开拓展。

例题演示：

• 例题1：

• 答案：B
• 解析：

直接利用性质3，叶节点就是度为0，n0总是比n2度为2的结点多1，所以n0=200，选B。

• 例题2：

• 答案：A
• 解析：

由前文得知，完全二叉树每个结点的度最大是2，最小为0，设度为i的结点个数为ni，其中i属于【0，2】，只需三部曲。

1. 结点总数为2n，则2n=n2+n1+n0，
2. 因为是二叉树，存在n0-1=n2，则式子变为n0-1+n1+n0=2n。
3. 又因完全二叉树，n1只能为0或1，又要确保结果是整数，所以n1为1，综上，n0=n

• 例题3：

• 答案：B
• 解析：

此题其实不复杂，通过完全二叉树以及结点的数量我们可以推出高度的范围，以此锁定答案。

1. 假设高度为h，当结点最多时，此二叉树是满二叉树，那么满足性质2，2^h-1=531，由此得出h为log2(532)，此情况是高度最低值。
2. 当结点最少时，也就是说第1到h-1层均是度为2的结点，只有最后一层第h层只有1个结点。此时列式：2^(h-1)-1+1=531，解得h为log2(531)+1，而此情况是树的高度的最高值
3. 由此，树的取值范围（log2(532)，log2(531)+1）取整，得到h为10，选B

        二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

• 1. 顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

比如我们要表示如下的完全二叉树（逻辑结构）

此时我们尝试用数组去存储（物理结构）

 我们将上述逻辑结构中树的数据存在数组里头，用下标来代表不同的数据，以便于访问。此时，我们就要将这块数组想象成”树“，怎么做呢？见下文：

只需要将数组还原成树的样子即可，如上文。

• 既然图画出来了，现在有个问题。如何理清父亲与孩子的关系呢？

首先，假设父亲的下标为parent，左孩子的下标为leftchild，右孩子的下标为rightchild，则父子间下标关系如下：

1. leftchild = parent*2 + 1
2. rightchild = parent*2 + 2
3. parent = (child - 1) / 2

解析：由图中不难发现，所有左孩子的下标均为奇数，而右孩子下标均为偶数，所以不难得出左右孩子的表达式。相反可以推出父亲的表达式。

• 但是父亲的式子中，只是(child - 1) / 2，并没有区分左右孩子，这是为什么呢？

这里我们假设leftchild和rightchild的下标均为3，算出来的parent下标不难发现均为1，同理左右孩子下标均为4时，父亲的下标算出来都是1，由此规律可得知直接用child下标表示父亲即可，无需区分左右孩子。

• 2. 链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。