🔑数据结构_第五章:树与二叉树
第五章、树与二叉树
(一)树的基本概念
1、基本概念
树是n(n>0)个结点的有限集。
当n=0时,称为空树。在任意一棵空树中应满足:
- 有且仅有一个特定的称为根的结点。
- 当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每个集合本身又是一棵树,并且称为根的子树。
显然,根的定义是递归的,即在树的定义中又用到了其自身,树是一种递归的数据结构。
树作为一种逻辑结构,同时又是一种分层结构,具有以下两个特点:
- 树的根结点没有前驱,其它所有结点有且只有一个前驱。
- 树中所有结点都可以有0个或多个后继。

树有n个结点,那它就有n-1条边。
2、基本术语
结点之间的关系描述
祖先结点:从“你”出发到根结点的路径上所经过的所有结点都称为“祖先结点”。
子孙结点:“你”后面的所有结点都可称为子孙结点。
双亲结点——即父节点——即直接前驱。
孩子结点——直接后继。
兄弟节点——同一层的结点。
唐兄弟节点——双亲在同一层的结点。
结点、树的属性描述
路径:自上而下的某两个节点之间的所有结点构成的序列,同一双亲的两个孩子之间不存在路径。
路径长度:路径上所经过的边的个数。
结点的层次/深度:从上往下数在第几层。
结点的高度:从下往上数。
树的深度/高度:总共多少层。注:深度默认从1开始算,但不排除有些题目指明从0开始!
结点的度:孩子/分支/直接后继的个数,是个数字。非叶子节点的度>0,叶子节点的度=0。
树的度:各结点的度的最大值
MAX{结点A的度,结点B的度,结点C的度,...,结点N的度}
。有序树、无序树
有序树:树中结点的各子树从左到右是有次序的,不能互换。
常见有哈夫曼树(俗称最优二叉树)、族谱(不能交换每一层老大老二老三等的位置)等。
无序树:树中结点的各子树从左到右是无次序的,可以互换。
总之,需要用结点的左右位置关系来反映某些逻辑关系的话就是有序树,否则为无序树。
森林
森林是m(m≥0)棵互不相交的树的集合。
3、树的常考性质
常见考点一:
结点数 = 总度数 + 1
。常见考点二:度为m的树与m叉树的区别。
常见考点三:度为m的树第
i
层至多有**mi-1**个结点(i≥1)。若层数从0开始,则结点数为**mi**个。
常见考点四和五:高度为h的**m叉树**结点个数的上下限问题。
最多:
$$ 最多为:\frac{m^h-1}{m-1} $$ 涉及到的是等比数列求和公式: $$ a+aq+aq^2+...+aq^{n-1} = \frac{a(1-q^n)}{1-q} $$
最少:
有h个结点:
常见考点六:具有n个结点的m叉树的最小高度为:
$$ 前h-1层最多最多结点数 < n \le 前h层最多最多结点数\\ \frac{m^{h-1}-1}{m-1} < n \le \frac{m^h-1}{m-1}\\ m^{h-1}
(二)二叉树的概念
1、基本概念
二叉树是n个结点的有限集合。(n=0时称为空树)
由一个根结点和两个互不相交的被称为跟的左子树和右子树组成,左子树和右子树又分别是一棵二叉树。
特点:
每个结点最多有两棵子树;
左右子树不能颠倒——二叉树是有序树!

二叉树的五种形态:
空树、只有左子树、只有右子树、只有根结点、完整二叉树。
2、几个特殊的二叉树:
(1)满二叉树
高度为h,且含有2h-1个结点的二叉树
特点:
- 只有最后一层有叶子结点。
- 不存在度为1的结点。
- 按层序从
i=1
开始编号,结点i
的左孩子编号为2i
,右孩子为2i+1
;结点i的父结点为[i/2](向下取整)
(如果有的话)。
(2)完全二叉树
定义:当且仅当其每个结点都与高度同样为
h
的满二叉树中编号为1~n
的结点一一对应时,称为完全二叉树。特点:
只有最后两层可能有叶子节点。
最多只有一个度为1的结点。
同上。
总结点数为
n
的完全二叉树中,编号i≤[n/2](向下取整)
的结点为分支节点,i>[n/2](向下取整)
则为叶子节点。换句话说:一半是分支节点另一半是叶子结点,
n
为奇数时多出来的一个一定是叶子结点。

(3)二叉排序树
满足以下特点的树称为二叉排序树:
①左子树上所有结点的数据均小于根结点存储的数据;
②右子树上所有结点的数据均大于根结点存储的数据;
③左子树和右子树又各满足以上条件。

(4)平衡二叉树
定义:树上任一结点的左子树和右子树的深度之差不超过1。
平衡二叉树是为了解决排序二叉树成链状的情况的。

3、二叉树常考性质
常见考点1
设非空二叉树中度为0、1、2的结点的个数分别为n0、n1、n2,则有:
$$
n_0 = n_2 + 1
$$
即——叶子节点总比二分之结点多一个。

常见考点2
二叉树第i层至多有**2i-1**个结点(i≧1)。
m叉树第m层至多有**mi-1**个结点(i≧1)。

常见考点3
高度为h的二叉树至多有2h-1个结点(满二叉树)。
高度为h的m叉树至多有mh-1/m-1个结点。

完全二叉树的常见考点
常见考点1:
完全二叉树的结点数为n(n>0),那么高度h为[log2(n+1)](向上取整)或[log2n]+1(向下取整)。
![]()
![]()
常见考点2:
对于完全二叉树,可以由总结点数n推出度为0、1、2的结点个数n0、n1、n2。
![]()
4、二叉树的存储结构
(1)顺序存储
只适合存储完全二叉树!
用数组存储,每个数组元素就是一个结点:
1 |
|

几个重要常考的基本操作:
- 判断是否有并找出指定结点
i
的左孩子、右孩子、父结点、i
所在层次。
(2)链式存储
对于非完全二叉树采用链式存储——也称为“二叉链表”。
1 | //二叉树链式存储 |

在该类二叉链表中,由某一结点开始寻找子节点很容易,但是寻找父结点就只能循环遍历了。
当然我们还可以给每个结点多附加一个指向父结点的指针使其成为“三叉链表”,不过考研考的是不带父指针的情况。。。(该遍历害得遍历)
对于有n个结点的二叉树,共有2n个指针域,除去根结点外每个结点头上都有一个指针指向它,所以共有n-1个非空指针,那么空指针就有2n-(n-1)=n-1个。
这些空指针域我们可以用来构造线索二叉树。
(三)二叉树的遍历与线索二叉树
1、根据二叉树的递归特性制定遍历规则
二叉树的递归特性:
- 要么是个空二叉树;
- 要么就是由“根结点+左子树+右子树”组成的二叉树。
对于非空二叉树有三种遍历方式:
先序遍历:根左右NLR
1
2
3
4
5
6
7void PreOrder(BiTree){
if(T != NULL){
visit(T); //根
PreOrder(T->lchild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}中序遍历:左根右LNR
1
2
3
4
5
6
7void InOrder(BiTree){
if(T != NULL){
InOrder(T->lchild); //递归遍历左子树
visit(T); //根
InOrder(T->child); //递归遍历右子树
}
}后序遍历:左右根LRN
1
2
3
4
5
6
7void PostOrder(BiTree){
if(T != NULL){
PostOrder(lchild); //递归遍历左子树
PostOrder(rchild); //递归遍历右子树
visit(T); //根
}
}
eg:



这种递归调用的时间复杂度为:O(h)(h为树的高度)。
求树的深度
1
2
3
4
5
6
7
8
9
10
11int treeDepth(BiTree T){
if(T == NULL){
return 0;
}
else{
int l = treeDepth(T->lchild);
int r = treeDepth(T->rchild);
//树的深度 = MAX(左子树深度, 右子树深度) + 1;
return l>r ? l+1 : r+1;
}
}
2、二叉树的层序遍历
层序遍历,即按层级从上到下、从左到右依次遍历。
代码实现过程中还需借助一个辅助队列。


1 | //定义二叉树结点 |
3、由遍历序列构造二叉树
不同二叉树可能得出同一个遍历结果(前、后、中、层序遍历都是如此),而由一个遍历序列可以产生不同的二叉树:

因此我们说,不能仅通过前、中、后、层序遍历系列中的某个序列确定一个二叉树。
但如果给出中序遍历加其他任意一个序列的话,我们可以凭这两个序列确定一个唯一的二叉树:
PS:必须有有中序遍历序列!

eg:


总结:

考试考法:给出中序遍历序列和其他一种序列,让我们求二叉树。
4、线索二叉树
(1)概念及原理
我们把那些左右指针为空的结点加以改造利用起来,使其原本为空的指针域指向它遍历顺序的前、后结点,这样子该二叉树要比原来访问起来(找前驱后继)方便很多。
下图为中序遍历方式生成的线索二叉树:


代码层面:
1 | //原来的结点结构 |
先序线索二叉树同样如此:

后序线索二叉树同样如此:

总结:

(2)代码实现——二叉树的线索化
①中序线索化


②先序线索化


③后续线索化


(3)在线索二叉树中寻找前驱和后继
中序线索二叉树:
在中序二叉树中找某个结点*p
的中序后继next
:
①若p->rtag == 1
,则next = p->rchild
;
②若p->rtag == 0
,则遍历寻找后继结点。

同理,找前驱也是如此:
①若p->ltag == 1
,则pre = p->lchild
;
②若p->ltag == 0
,则遍历寻找前驱结点。

先序线索二叉树:

在先序线索二叉树中无法用该方法实现找某个节点的先序前驱!除非能找到其父结点并且:

后序线索二叉树:

同样,在后序线索二叉树中无法用传统方法找某个节点的后序后驱!除非能找到其父结点并且:

(四)树、森林
回顾:树的逻辑结构

1、双亲表示法(顺序存储)
用顺序存储的方式存储每个数据元素,每个结点都有数据域和一个存储父结点位置的”指针“:
1 | //定义节点 |

- 增删改查:
- 增:直接在表的末尾增加结点即可。
- 删:叶子结点随便删,但是非叶子结点就不好删了!
- 改:找到结点即可。
- 查:查某个元素的父结点很容易,但要查子节点就只能遍历了。
2、孩子表示法(顺序+链式)

*讲师没有过多赘述,,,。
3、孩子兄弟表示法(链式)——二叉树与树的转化
最常用!最常考!!!
本质上是二叉链表,不同的是,每个结点的两个指针,一个指向兄弟结点,另一个指向其第一个孩子节点,如下图:

这样存储的结果便是将一棵任意的树转化成了二叉树,实现了二者的转化!
1 | typedef struct CSNode{ |
4、森林和二叉树之间的转换
同理,森林不过是多个树而已,而多个树的根结点我们又可以看作是同一层的兄弟结点,这样子就可以把整片森林存储为一个二叉树!
森林转化为二叉树:
二叉树转化为森林:
其实本质上还是用二叉链表存储森林。
(五)树、森林的遍历
- 树的遍历有:
- 先根遍历
- 后根遍历
- 层序遍历
- 森林的遍历有:
- 先序遍历
- 中序遍历
1、树的先根、后根、层序遍历
树的先根、后根、层序遍历在逻辑上与二叉树的遍历一毛一样!

树的先根遍历的结果序列,与把它转化为二叉树的先序遍历序列结果,是一样的,后根遍历序列又对应中序遍历序列,即:
先根——先序,树后根——二叉树中序,二者属于深度优先遍历。
而层次遍历属于广度优先遍历:

2、森林的遍历
(1)先序遍历
挨个树进行先根遍历,最后依次连起来:
- 访问森林中第一棵树的根结点;
- 先序遍历第一棵树中根节点的子树森林;
- 先序遍历除去第一棵树后剩余的树构成的森林。

或者转化为二叉树进行先序遍历,序列结果一样。
(2)中序遍历
挨个树进行中序遍历,最后依次连起来:
- 中序遍历森林中第一棵树的根结点的子树森林。
- 访问第一棵树的根结点。
- 中序遍历除去第一棵树之后剩余的树构成的森林。

或者转化为二叉树进行中序遍历,序列结果一样。
(六)哈夫曼树
1、哈夫曼树的定义
我们给结点赋予一个新的属性——权值,节点的权是具有某种现实含义的数值(如表示结点的重要性等)。
结点的带权路径长度:从树的根结点到该结点的路径长度(经过的边数)与该结点权值的乘积。
树的带权路径长度:树中所有叶子结点的带权路径长度之和(WPL,Weighted Path Length)。

定义:在含有n个带权结点的二叉树中,其中带权路径长度最小的二叉树称为哈夫曼树,也称最优二叉树、赫夫曼树。
2、哈夫曼树的构造
给定n个不同权值的结点,构造哈夫曼树:
将这些单独的结点看作只有根节点的二叉树,它们构成森林F;
从F中选择两个权值最小的树,作为新的根结点的孩子,构成一个具有新的权值的二叉树;
从F中删除刚才选出的两棵树,同时将新得到的树加入到F中。
重复上述步骤,直到F中只剩一棵树为止。

- 每个初始给定的结点最终都成为构造的哈夫曼树的叶子结点,且权值越小的结点到根结点的路径长度越大;
- 哈夫曼树的结点总数为
2n - 1
; - 哈夫曼树中不存在度为1的结点;
- 哈夫曼树并不唯一,但WPL必然相同且为最优。
3、哈夫曼编码
- 固定长度编码:每个字符都采用相同长度的二进制位表示。
- 可变长度编码:允许对不同字符采用不等长的二进制位表示。
- 在一套可变长度编码中,若任意字符的编码都不是其它任意字符编码的前缀,那么我们称这一套编码为前缀编码。
- 哈夫曼编码:由哈夫曼树得到——字符集中的每个字符作为一个叶子结点,各个字符出现的频度作为叶子结点的权值,由此构造出哈夫曼树。
