【数据结构】第五章：二叉树（下）

第五章：二叉树（下）

---

OVERVIEW

• 第五章：二叉树（下）
• • • 一、树与森林
    • • 1.树存储结构
      • • （1）双亲表示法：
        • （2）孩子链表：
        • （3）二叉链表表示法：
      • 2.树的基本操作
      • • （1）树转换为二叉树：
        • （2）二叉树转换为树：
      • 3.森林的基本操作
      • • （1）森林转为二叉树：
        • （2）二叉树转为森林：
      • 4.树与森林的遍历
      • • （1）树的遍历：
        • （2）森林的遍历：
    • 二、哈夫曼树
    • • 1.基本概念
      • 2.哈夫曼树构造
      • 3.哈夫曼树构造算法
      • • （1）数组初始化：
        • （2）结点的n-1次合并：
      • 4.哈夫曼树应用—哈夫曼编码
      • • （1）问题引入：
        • （2）哈夫曼编码：
      • 5.哈夫曼编码应用—文件的编码与解码
    • 三、二叉树经典问题
    • • 1.数据压缩问题
      • 2.表达式求值问题

一、树与森林

树是n个结点的有限集合，

1. 若n==0，则称为空树

2. 若n > 0，则有：

   有且仅有一个特定的根称为root结点

   其余结点可分为m个互不相交的有限集T1，T2，T3，…Tm

1.树存储结构 （1）双亲表示法：

实现：定义结构数组存放树的结点，每个结点含两个域

• 数据域：存放结点本身信息
• 双亲域：指示本结点的双亲结点在数组中的位置

（2）孩子链表：

将每个结点的孩子结点排列起来，用单链表存储（n个结点则有n个孩子链表）

而n个头指针又组成一个线性表，用顺序表存储（含n个元素的结构数组）

带双亲的孩子链表：

（3）二叉链表表示法：

孩子兄弟表示法、二叉树表示法、二叉链表表示法

实现：用二叉链表表示数的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。

2.树的基本操作

将树转化为二叉树进行处理，利用二叉树的算法来实现对树的操作，

由于树和二叉树都可以用二叉树链表作存储结构，则以二叉链表做媒介可以导出树与二叉树之间的对应关系：

注意：给定一棵树，可以找到唯一的二叉树与之对应

（1）树转换为二叉树：

二叉树转换步骤：

1. 加线：在兄弟之间加一根连线
2. 抹线：对每个结点除了其左孩子外，去除其与其他孩子之间的关系
3. 旋转：以树的根结点为轴心，将整树顺时针旋转45度

总结：兄弟相连留长子

（2）二叉树转换为树：

树转换步骤：

1. 加线：若p为双亲结点的左孩子，则将p的右孩子、右孩子的右孩子…沿分支找到所有的右孩子与双亲连接
2. 抹线：抹掉原二叉树中双亲与右孩子之间的连线
3. 调整：将结点按层次排列，形成树结构

总结：左孩右右连双亲，去掉原来右孩线

3.森林的基本操作 （1）森林转为二叉树：

1. 将各棵树分别转换为二叉树
2. 将每棵树的根结点用线相连
3. 以第一棵树根结点为二叉树的根，再以根结点为轴心顺时针旋转，构成二叉树形结构

总结：树变二叉根相连

（2）二叉树转为森林：

1. 抹线：将二叉树中根节点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉（产生许多孤立的二叉树）
2. 还原：将孤立的二叉树还原为树

4.树与森林的遍历 （1）树的遍历：

遍历方式	说明
先根遍历	若树非空，则先访问根节点，然后依次遍历各树
后根遍历	若树非空，则先依次遍历各树，然后访问根节点
层次遍历	若树非空，则自上而下、自左而右依次访问树中结点

注意：树的遍历没有中根遍历的情况，无法确定根的中序位置

（2）森林的遍历：

先序遍历：

若森林不为空，则

1. 访问森林中第一棵树的根节点
2. 先序遍历森林中第一棵树的子树森林
3. 先序遍历森林中其余树构成的森林

注意：依次从左至右对森林中的每一棵树进行先根遍历

中序遍历：

1. 中序遍历森林中第一棵树的子树森林
2. 访问森林中第一棵树的根结点
3. 中序遍历森林中其余树构成的森林

注意：依次从左至右对森林中的每一棵树进行后根遍历

二、哈夫曼树 1.基本概念

概念	说明
路径	从树中一个结点到另一个结点之间分支构成的路径
结点的路径长度	两个结点之间路径上的分支数
树的路径长度	从树根到每一个结点的路径长度之和TL

注意：结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树

概念	说明
权	将树中结点赋予某种含义的数值，则这个数值称为该结点的权
结点的带权路径长度	从根节点到该结点之间的路径长度与该结点的权的乘积
树的带权路径长度	树中所有叶子结点的带权路径长度之和

哈夫曼树：最优二叉树，带权路径长度（WPL）最短的树

2.哈夫曼树构造

根据哈夫曼树中权越大的叶子离根结点越近的规律，

利用贪心算法的思想：构造哈夫曼树时首先选择权值小的叶子结点

注意：

1. 哈夫曼树结点的度数为0或者2，没有度为1的结点
2. 包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生n-1个新结点
3. 包含n个叶子结点的哈夫曼树中共有2n-1个结点

3.哈夫曼树构造算法

采用顺序存储结构——一维数组实现

（1）数组初始化：

1. 初始化HT[1…2n-1]：lch=rch=parent=0
2. 输入初始化n个叶子结点：置HT[1…n]的weight值

（2）结点的n-1次合并：

对结点进行n-1次合并，依次产生n-1个结点HT[i]，i=n+1, n+2, …2n-1

1. 在HT[1…i-1]中选取两个未被选过（parent==0）且weight最小的结点HT[s1]和HT[s2]

2. 修改HT[s1]和HT[s2]的parent值：HT[s1].parent=i；HT[s2].parent=i；

3. 修改新产生的HT[i]：

   HT[i].weight = HT[s1].weight + HT[s2].weight;
   HT[i].lch = s1;
   HT[i].rch = s2;
   

4.哈夫曼树应用—哈夫曼编码 （1）问题引入：

在远程通讯问题中，需要将待传输字符转换成二进制字符串：

为了解决不定长编码中重码的问题，且使得电文总长最短，

设计一种编码方式使任一字符的编码都不是另一个字符编码的前缀（前缀编码）——哈夫曼编码

1. 统计字符集中每个字符在电文中出现的平均概论（概率越大、要求编码越短）
2. 将每个字符的平均概论作为权值，利用哈夫曼树的特点（权值越大的叶子离根越近）构造哈夫曼树。（概论越大的结点路径越短）
3. 在哈夫曼树的每个结点分支上标记0/1（左分支0，右分支1）
4. 把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符编码

1. 哈夫曼编码是前缀码（没有一片树叶是另一片树叶的祖先）
2. 哈夫曼编码是最优前缀码（哈夫曼树的带权路径长度最短，字符编码总长度一定是最短的）

（2）哈夫曼编码：

5.哈夫曼编码应用—文件的编码与解码

编码过程：

1. 输入各字符及其权值
2. 构造哈夫曼树HT[i]
3. 进行哈夫曼编码HC[i]
4. 查询HC[i]得到各字符的哈夫曼编码

解码过程：

1. 构造哈夫曼树
2. 依次读入二进制码
3. 读入0则走向左孩子，读入1则走向右孩子
4. 一旦到达某个叶子结点，即可译出字符
5. 然后再从根出发继续译码，指导结束

三、二叉树经典问题 1.数据压缩问题

2.表达式求值问题