清华962数据结构 --- Ch6 树和二叉树
一、树
1、定义与基本术语
树是 n ()个结点的有限集,n=0 时称为空树 有且只有一个特定的称为根 (Root)的结点 当 n>1时,其余结点可以分为 m ()个互不相交的有限集合,其中每一个集合本身又是一棵树,称为根的子树
- 结点:包含一个数据元素和指向其子树的分支
- 根结点:只有后继没有前驱,对于非空树,有且只有一个
- 结点的度:结点拥有的子树数
- 叶子结点/终端结点:度为 0 的结点
- 分支结点/非终端结点:度不为 0 的结点
- 树的度:树内部各结点度的最大值
- 孩子:结点的子树的根
- 双亲:孩子结点定义中的结点
- 兄弟:同一个双亲的孩子之间称为兄弟
- 祖先:从根到该结点所经分支上的所有结点
- 子孙:以某结点为根的子树中的所有结点
- 层次:根结点为第一层,根的孩子为第二层
- 堂兄弟:双亲在同一层的结点
- 深度:树中结点的最大层次
- 有序树:树中结点各子树有左右顺序,不能交换
- 无序树:与有序树相反
- 森林:m ()棵互不相交的树的集合
2、树的基本性质
- 树的结点数 = 树的总度数+1
- 度为 m 的树第 i 层至多有 个结点()
- 高为 h 的 m 叉树至少有 h 个结点
- 高为 h,度为 m 的树至少有 个结点
- 具有 n 个结点的 m 叉树的最小高度为
二、二叉树
1、定义
二叉树:n 个 结点的有限集合,其中每个结点最多有两颗子树(二叉树中不存在度大于 2 的结点),同时二叉树子树有左右之分,不能交换。n = 0 时为空二叉树
2、二叉树的形态
(1)五种基本形态
- 空二叉树
- 仅有根结点的二叉树
- 右子树为空的二叉树
- 左子树为空的二叉树
- 左右子树均非空的二叉树
(2)特殊的二叉树
满二叉树 树的每一层结点数都达到了最大值,即一棵深度为 k 且有 个结点的二叉树 特点:
- 只有最后一层有叶子结点
- 不存在度为 1 的结点
- 层序从 1 开始编号,结点 i 的左孩子编号为 ,右孩子的编号为 ,它的父节点为
完全二叉树 深度为 k 的,有 n 个结点的二叉树,当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 在至 n 的结点一一对应时,称为完全二叉树。 一棵完全二叉树是由对应的满二叉树进行删除而来的,且删除的时候必须从右向左,从下到上。 注意:满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树
特点:
- 只有最后两层可能有叶子结点
- 最多只有一个度为 1 的结点
- 如果某个结点只有一个孩子,那么它一定是左孩子
- 层序从 1 开始编号,结点 i 的左孩子编号为 ,右孩子的编号为 ,它的父节点为
- 层序从 1 开始编号,当 时,该结点为分支结点;当 时,该节点为叶子结点
- 二叉排序树
满足以下性质的树称为二叉排序树:
- 左子树上所有结点的关键字值均小于根结点的关键字
- 右子树上所有结点的关键字值均大于根结点的关键字
- 左子树和右子树又各是一颗二叉排序树
用于元素的排序、搜索
- 平衡二叉树 树上任一结点的左右子树高度之差不超过 1
有更高的搜索效率
3、二叉树的基本性质
- 在二叉树的第 i 层上至多有 个结点 利用数学归纳法可以证明本性质
- 深度为 k 的二叉树至多有 个结点
- 对任何一棵二叉树 T,如果其终端结点数为 ,度为 2 的结点数为 ,则
完全二叉树的性质:
- 具有 n 个结点的完全二叉树的高度为 证明:
- 如果对一棵有 n 个结点的完全二叉树(深度为 )的结点按层序编号,则对任一结点 i ,有
- 如果 i=1,则结点 i 是二叉树的根,无双亲;如果 ,则其双亲 PARENT(i)是结点
- 如果 ,则结点 i 为无左孩子(结点 i 为叶子结点);否则其左孩子 LCHILD(i)是结点
- 如果 ,则结点 i 为无右孩子;否则其右孩子 RCHILD(i)是结点
- 对于完全二叉树,可以由结点数 n 推出度为0、1和2的结点个数为 、 和 。因为完全二叉树至多只有一个度为1的结点,即 ,又因为 ,故 一定为奇数,所以
- 若完全二叉树有 (偶数)个结点,则必有
- 若完全二叉树有 (奇数)个结点,则必有
4、二叉树的存储结构
(1)顺序存储
顺序存储只适合存储完全二叉树,因为在最坏的情况下,一棵深度为 k 且只有 k 个结点的单支树(树中不存在度为 2 的结点),需要长度为 的数组
(2)链式存储结构
二叉链表:包含三个指针域(左孩子,data,右孩子) 三叉链表:包含四个指针域(左孩子,data,双亲结点,右孩子)
其中,在含有 n 个结点的二叉链表中有 n+1 个空链域
三、遍历二叉树和线索二叉树
遍历:从根节点开始,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次,且仅被访问一次
共分为三种:
- 先序遍历:根左右(NLR)
- 中序遍历:左根右(LNR)
- 后序遍历:左右根(LRN)
1、先序遍历
第一次遇到这个结点访问,第二次遇到或第三次遇到时跳过该结点直接访问下一个结点
2、中序遍历
第一次遇到结点跳过,第二次再遇到结点访问,第三次遇到跳过
3、后序遍历
前两次遇见结点不访问,最后一次遇见时访问
对于二叉树的遍历而言:
- 对于含有 n 个结点的二叉树,其时间复杂度为
O(n)
- 空间复杂度为遍历过程中栈的最大容量(树的深度)
O(n)
- 每个结点都会被路过 3次
4、层序遍历
基于树的层次特性确定的次序规则 需要借助队列完成。若树为空,则返回空,然后从上至下,从左至右依次访问结点
- 初始化一个辅助队列
- 根结点入队
- 若队列非空,则队头结点出队,访问该结点,然后将其左、右孩子(如果有)插入队尾
- 重复第三步,直至队列为空
5、由遍历序列重建二叉树
(1)前序 + 中序
(2)中序 + 后序
(3)层序 + 中序
6、线索二叉树
我们根据上述的遍历、存储方法,我们只能找到结点的左右孩子信息,而无法知道改树的前驱、后继信息。 即我们只有从根节点出发开始遍历,才能完整的获得树的全部信息,倘若我们跳过了根节点,从其子结点开始遍历则无法获得完整信息
为了充分利用空间和保存特定遍历情况下前后结点的关系,我们用指针指向某个结点的前驱和后继,这样的指针称之为线索,加上线索的二叉链表称之为线索链表,相应的二叉树就称之为线索二叉树
下面是中序线索树的示意图:
(1)线索二叉树的存储
typedef struct BLNode
{
DataType data;
struct BLNode *lchild,*rchild;
int ltag;
int rtag;
}
- ltag=0时指向左孩子;ltag=1时指向前驱
- Rtag=0 时指向右孩子; rtag=1 时指向后继
(2) 二叉树的线索化
线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索,而前驱或后继的信息只有在遍历的时候才能得到,所以线索化的过程就是在遍历的过程中修改空指针的过程。
7、树的存储结构
(1)双亲表示法
- 每个结点中保存指向双亲的“指针”,data,parrent
- 根结点固定存储在0,-1表示没有双亲
可以根据结点的parent指针很容易找到其双亲结点,时间复杂度为O(1)
,且当parent为-1时,就找到了根,但是这种结构不利于寻找孩子且不利于表示结点间关系
(2)孩子表示法
由于树中每个结点都可能有多棵子树,可以考虑使用多重链表,即每个结点有多个指针域,其中每个指针指向一棵子树的根节点,我们将这种表示方法称之为多重链表表示法,此时链表中的结点有两种结点形式
Data-child 1-child 2-...-childd 多重链表中的结点是同构的,但树中的很多结点的度都小于树的度 d,所以在链表中会存在很多空链域,比较浪费空间
Data-degree-child 1-child 2- ...-childd 多重链表中的结点不是同构的,虽然通过这种方式能够节省存储空间,但是操作不方便
为了解决上述两种方法的不便性,我们提出了孩子表示法,将每个结点的孩子结点排列起来,看成是一个线性表,且以单链表作为存储结构。
(3)孩子兄弟表示法
任意一棵树,其结点的第一个孩子如果存在那么就是唯一的,它的右兄弟如果存在也是唯一的。因此,设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟
8、森林与二叉树、树的转换
(1)树转为二叉树
- 加线:在所有兄弟结点之间加一条连线
- 去线:对树中的每一结点,只保留它与第一个孩子结点的连线,删除它与其他孩子之间的连线
- 层次调整:以树的根节点为轴心,将整棵树顺时针旋转一定的角度,使结构层次分明。需要注意的是第一个孩子是二叉树结点的左孩子,兄弟转换过来的孩子是结点的右孩子
(2)森林转化为二叉树
- 每棵树按照上面的方法转化为二叉树
- 第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根节点作为前一棵二叉树的根节点的右孩子,用线连接起来。当所有二叉树连接起来后就森林就转化为了一棵二叉树
(3)二叉树转化为树
- 加线:若某结点的左孩子存在,则将这个左孩子的右孩子结点、右孩子的右孩子结点,也即左孩子的 n 个右孩子结点都作为此结点的孩子。然后该结点与这些孩子结点用线连接起来
- 去线:删除原二叉树中所有结点与其右孩子结点的连线
- 层次调整
(4)二叉树转化为森林
- 从根节点开始,若右孩子存在,则把与右孩子结点的连线删除,再查看分离后的二叉树,若右孩子存在,则连线删除… …,直到所有右孩子连线都删除为止,得到分离的二叉树
- 再把每一颗分离后的二叉树转化为树即可
9、树和森林的遍历
(1)树的先根遍历
- 若树非空,先访问根结点,再依次对每棵子树进行先根遍历
- 树的先根遍历序列与这棵树相应二叉树的先序序列相同
(2)树的后根遍历
- 后根遍历:若树非空,先依次对每棵子树进行后根遍历,最后再访问根结点
- 树的后根遍历序列与这棵树相应二叉树的中序序列相同
- 也被称为深度优先遍历
(3)树的层次遍历
- 用队列实现,又被称为广度优先遍历
步骤:
- 若树非空,则根结点入队
- 若队列非空,队头元素出队并访问,同时将该元素的孩子依次入队
- 重复第二步直到队列为空
(4)森林的先序遍历
若森林为非空,则按如下规则进行遍历:
- 访问森林中第一棵树的根结点
- 先序遍历第一棵树中根结点的子树森林
- 先序遍历除去第一棵树之后剩余的树构成的森林
- 效果等同于依次对各个树进行先根遍历
- 用孩子兄弟表示法转换为二叉树,效果等同于依次对二叉树的先序遍历
(5)森林的中序遍历
若森林为非空,则按如下规则进行遍历:
- 中序遍历森林中第一棵树的根结点的子树森林
- 访问第一棵树的根结点
- 中序遍历除去第一棵树之后剩余的树构成的森林
- 效果等同于依次对各个树进行后根遍历
- 用孩子兄弟表示法转换为二叉树,效果等同于依次对二叉树的中序遍历
四、树与等价问题
尚且存疑,回头看
五、赫夫曼树及其应用
在含有 n 个带权叶结点的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树
- 结点的权:有某种现实含义的数值(如:表示结点的重要性等)
- 结点的带权路径长度:从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积
- 树的带权路径长度:树中所有叶结点的带权路径长度之和(WPL, Weighted Path Length)
1、赫夫曼树的构造
- 将这 n 个结点分别作为 n 棵仅含一个结点的二叉树,构成森林 F
- 构造一个新结点,从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左、右子树上根结点的权值之和
- 从 F 中删除刚才选出的两棵树,同时将新得到的树加入 F中
- 重复步骤2和3,直至F中只剩下一棵树为止
其中:
- 每个初始结点最终都成为叶结点,且权值越小的结点到根结点的路径长度越大
- 哈夫曼树的结点总数为 2n-1
- 哈夫曼树中不存在度为 1 的结点
- 哈夫曼树并不唯一,但 WPL 必然相同且为最优
2、赫夫曼编码
- 固定长度编码:每个字符用相等长度的二进制位表示
- 可变长度编码:允许对不同字符用不等长的二进制位表示
- 若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码,如果没有前缀编码容易出现歧义
- 由哈夫曼树得到哈夫曼编码:字符集中的每个字符作为一个叶子结点,各个字符出现的频度作为结点的权值,根据之前介绍的方法构造哈夫曼树