数据结构 Data Structure 主讲人：王国军，郑瑾 CSU 中南大学信息院计科系 {Csgjwang,zhengjin}@csu.edu.cn http://trust.csu.edu.cn/ 电话：0731-88877711 手机：13508486821 办公室：计算机楼406-B 版权申明：本PPT根据《数据结构》教材所附PPT改编，仅供计科09级/信安09级任课老师和学生使用。

第六章 数和二叉树 6.1 树的定义和基本术语 6.2 二叉树的定义 6.3 二叉树的存储结构 6.4 二叉树的遍历 6.5 线索二叉树 6.6 树和森林的表示方法 6.7 树和森林的遍历 6.8 哈夫曼树与哈夫曼编码

6.1 树的定义和基本术语 一、树的定义(递归定义） 1．树(Tree)是n(n≥0)个结点的有限集T， 如果n = 0，称为空树；否则： 树是一类重要的非线性数据结构，是以分支关系定义的层次结构。 一、树的定义(递归定义） 1．树(Tree)是n(n≥0)个结点的有限集T， 如果n = 0，称为空树；否则： 有且仅有一个称为树的根(root)的结点。 其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。 树型结构是一类重要的非线性结构，正如在课前思考题所看到的，树型结构广泛用于描述家族谱系以及其它社会组织结构。在计算机领域中，如编译程序中的语法结构和数据库中的信息组织也都需要借用树来描述。本章将讨论树和二叉树两种树型结构。 A B C D E F G H I J K L M

2、树的表示形式-—是一棵倒立的树 T1 T2 T3 对于非空树，其特点： 树中至少有一个结点——根 树中各子树是互不相交的集合 只含有根结点的树 T1 T2 T3 含有子树T1、T2和T3的树

树的其它表示方式 嵌套集合 凹入表示法 广义表

树 的 基 本 术 语

二、树的基本术语 它的孩子为第二层…… 结点(node)—表示树中的元素，包括数据项及若干指向其子树的分支 结点的度—结点拥有的（分支）子树个数 叶子—度为0的结点 树的度—树中各结点的度数的最大值 孩子—结点的子树的根称为 该结点的孩子（结点） 双亲（父结点）—孩子结点的上一层结点 称为该结点的~(父结点) 兄弟——同一双亲的孩子互称兄弟（结点） 结点的层次——从根结点算起，根为第一层， 它的孩子为第二层…… A B C D E F G H I J K L M 树的示意图

二、树的基本术语 树的深度（树高）—树中结点的最大层次数。 堂兄弟—其双亲在同一层的结点互称为堂兄弟。 结点的祖先—从根结点到该结点所经分支上的所有结点（不包括该结点本身）。 结点的子孙—以某结点为根的子树中的任一结点都称之为该结点的子孙（不包括该结点）。 有序树和无序树：树中各结点的子树 从左到右有次序（不能互换）， 称该树为有序树，否则为无序树。 （有序树：第一个孩子、第二个孩子…） 森林—m(m0)棵互不相交的树构成的集合。 A B C D E F G H I J K L M 树的示意图

森林： 是m（m≥0）棵互不相交的树的集合 F A B C D E F G H I J K L M root 就逻辑结构而言，可以森林和树相互递归的定义来描述树： 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林

B C D E F G H I J M K L 结点的层次: A (从根结点到结点的)路径： 由从根结点到该结点所经分支和结点构成。 假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1 树的深度： 树中叶子结点所在的最大层次 注意：树的叶子结点不一定都在树的最大层次上

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 对比线性结构和树型结构的结构特点 树型结构（1:n） 线性结构（1:1） A B C D E F G H I J M K L (a1, a2, a3, …an-2, an-1, an) 第一个数据元素 (无前驱) 根结点 (无前驱) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 最后一个数据元素 (无后继) 多个叶子结点 (无后继) 其它数据元素 (一个前驱、 一个后继) 其它数据元素 (一个前驱、 一个或多个后继)

三、树的抽象数据类型定义 } ADT Tree ADT Tree { 数据关系 R： 基本操作…… 数据对象 D： 树的结构定义 + 树的基本操作= 抽象数据类型树的定义 ADT Tree { 数据对象 D： D是具有相同特性的数据元素的集合。 数据关系 R： 若D为空集，则称为空树 。 否则: (1) 在D中存在唯一的称为根的数据元素 root； (2) 当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。 基本操作…… } ADT Tree

查找类： Root(T) // 求树的根结点 Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点 LeftChild(T, cur_e) // 求当前结点的最左孩子 RightSibling(T, cur_e) // 求当前结点的右兄弟 TreeEmpty(T) // 判定树是否为空树 TreeDepth(T) // 求树的深度 TraverseTree( T, Visit() ) // 遍历

插入类： InitTree(&T) // 初始化置空树 CreateTree(&T, definition) // 按定义构造树 Assign(&T, cur_e, value) // 给当前结点赋值 InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树

删除类： ClearTree(&T) // 将树清空 DestroyTree(&T) // 销毁树的结构 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树

6.2 二叉树

或：二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 6.2.1 二叉树的定义 二叉树的递归定义： 其左右子树又都是二叉树。 一、二叉树定义：度不大于2且有左右之分的树型结构 （区别于度为2的树或度不大于2的树）。 或：二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 根结点 右子树 A B E C F G D 左子树 H K

二叉树的基本特征 1、每个结点最多只有两棵子树。 2、子树有左右之分，其次序不能任意颠倒，是一个有序的树型结构。

二、二叉树的五种基本形态（概括性） N N N N L R L R 空树 只含根结点 左右子树 均不为空树 右子树为空树 左子树为空树 二叉树定义：度不大于2 （每个结点最多只有两棵子树）的有序的树型结构 空树 只含根结点 N 左右子树 均不为空树 右子树为空树 左子树为空树 N N N L R L R

三、二叉树的基本操作

查 找 类 LeftChild(T, e); RightChild(T, e); 查 找 类 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit());

插 入 类 Assign(&T, &e, value); CreateBiTree(&T, definition); 插 入 类 InitBiTree(&T); Assign(&T, &e, value); CreateBiTree(&T, definition); InsertChild(&T, p, LR, c);

删 除 类 ClearBiTree(&T); DestroyBiTree(&T); DeleteChild(&T, p, LR);

6.2.2 二叉树的重要特性

性质1： 在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1) 用归纳法证明： 归纳基： i = 1 层时，只有一个根结点： 3 4 5 7 6 用归纳法证明： 归纳基： 归纳假设： 归纳证明： i = 1 层时，只有一个根结点： 2i-1 = 20 = 1； 8 假设对所有的 j，1≤ j  i，命题成立； 即第j层上至多有2j-1 个结点。 因二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2(i-1)-1 2 = 2i-1 。 证明j=i时命题成立 第i-1层的结点数

性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）。 证明： 基于上一条性质，深度为 k 的二叉树上的结点数至多为 思考题：深度为h的 k叉树最多有多少个结点？ =

对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式： 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式： n0 = n2+1。 1 2 3 4 5 6 证明： 设 二叉树上结点总数 n = n0 + n1 + n2 …① 又 设二叉树上分支总数为 b，则： 从前驱 (入支）角度： b= n-1 … ② 从后继（出支）角度： b=n1 + 2n2 …③ 从而有： n0 + n1 + n2 – 1= n1 + 2n2 由此， n0 = n2 + 1 。

利用结点总数与分支总数求解问题 思考题： 有n个结点的树，仅有度为0的叶子结点和 度为k的结点,问该树含有多少叶子结点？ 结点总数 n=n0+nk …① 分支总数： 从入支角度：有b= n-1 … ② 从出支角度：有b=nk*k …③ 叶子数目 =（n(k-1)+1）/k

两类特殊的二叉树： 满二叉树：指的是深度为k且含有2k – 1 个结点的二叉树。 特点：每一层上的结点数都是最大结点数 二叉树性质1：第 i 层上至多有2i-1 个结点。 二叉树性质2：深度为k的二叉树至多有2k - 1 个结点。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

若一棵二叉树中所含的 n 个结点与满二叉树中编号为 1 至 n 的结点一一对应(编号和位置一一对应)。 完全二叉树： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 若一棵二叉树中所含的 n 个结点与满二叉树中编号为 1 至 n 的结点一一对应(编号和位置一一对应)。 特点： 1. 叶子结点只可能在层次最大的两层上出现. 2. 对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1. 1 2 3 4 5 6 7 8 9 10 11 12

如何判别 完全二叉树？ 定义 法一：若二叉树中最多只有最下两层有度小于2的结点,且最下层的结点都依次排列在最左边,则称此二叉树为完全二叉树。 如何判别 完全二叉树？ 定义 法一：若二叉树中最多只有最下两层有度小于2的结点,且最下层的结点都依次排列在最左边,则称此二叉树为完全二叉树。 法二：深度为k的二叉树,若第1到第k-1层为深度为k-1的满二叉树,第k层的结点都依次排列在最左边,则称此二叉树为完全二叉树。 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 1 2 3 4 5 6 7 从完全二叉树定义可知，结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下，表示本层结点数达到最大后，才能放入下一层。从左到右，表示同一层结点必须按从左到右依次排列，若左边空一个位置时不能将结点放入右边。 1 2 3 11 4 5 8 9 12 6 7 10 1 2 3 4 5 6

1 2 3 4 5 6 7 8 9 10 11 12 性质4 如将一棵有n个结点的完全二叉树自 顶向下，同一层自左向右连续给结点编号 • 如果i = 1，则结点i无双亲； • 如果i > 1，则结点i的双亲为i/2。　 • 如果2i < n，则结点i的左孩子为2i，若2i+1 < n，则结点i的右孩子为2i+1。 1 2 3 4 5 6 7 8 9 10 11 12 2

证明： 性质 5 ： 具有 n 个结点的完全二叉树的深度为  log2n +1 。 特点 2k - 1 个结点（k≥1）。 3 11 4 5 8 9 12 6 7 10 特点 深度为 k 的二叉树上至多含 2k - 1 个结点（k≥1）。 证明： 设完全二叉树的深度为 k 则： 2k-1 -1 < n ≤ 2k -1 或 2k-1 ≤ n < 2k 两边取对数得： k-1 ≤ log2 n < k k ≤ log2 n +1 < k +1 因为 k 只能是整数，因此， k =log2n + 1 (注意ëxû表示取不大于x的最大整数，也叫做对x下取整，éxù表示取不小于x的最小整数，也叫做对x上取整。) 证明：设该完全二叉树高度为k，则该二叉树的前面k-1层为满二叉树，共有2k-1-1个结点，而该二叉具有k层，第k层至少至有1个结点，最多有2k-1个结点。因此有下面的不等式成立：（2k-1 –1）+1 ≤n ≤（2k-1-1）+2k-1，即有 2k-1≤n≤2k-1。由式子后半部分可知, n≤2k-1…① 由式子前半部分可知 2k-1≤n…② 由①有 n+1≤2k ，同时取对数得： log2(n+1)≤k 故 k≥log2(n+1),即 k=élog2(n+1)ù。即得到第二个结论。 由②有2k-1≤n,同时取对数得：k≤log2n+1即 k=ëlog2 nû+1,即第一个结论成立,证毕。 知识点：变换 具有2000个结点的二叉树，其高度至少为（ ）。 A．9 B．10 C．11 D．l2 分析：在什么情况下 ，具有N个结点的二叉树的高度最低？ 当二叉树中各个结点按编号由1到N与具有N个结点的完全二叉树的编号一一对应时（即二叉树中各个结点顺序紧邻排列），对应二叉树的高度最低。

6.2.3 二叉树的存储结构 顺序存储结构 链表存储结构

二叉树的顺序存储 ---完全二叉树 二叉树的顺序存储表示是：用一组连续存储空间（一维数组）依次从上到下、从左到右存储完全二叉树中的所有结点，亦即完全二叉树编号为 i 的结点存到一维数组的下标为 i(0号单元不存储节点） 的位置中。 若该二叉树为非完全二叉树，则必须将相应位置空出来或用0补充，使存放的结果符合完全二叉树形状。为方便存储，需要把二叉树中补充成完全二叉树形状，如 下图 所示。

完全二叉树 顺序表示 （最简单、最省存储） 1 **对完全二叉树的所有 2 3 结点按照层次次序自 顶向下，得到一个结 点的线性序列，按该 序列将二叉树放在一 维向量中。 4 8 9 5 10 6 7 1 2 3 4 5 6 7 8 9 10 完全二叉树 顺序表示 （最简单、最省存储） **利用完全二叉树的 性 质 4，从一个结点的编 号推算出其双亲、子 女、兄弟等结点的编 号，找到这些结点。 52

1 2 3 4 6 7 8 9 12 14 一般二叉树 顺序表示 1 **对二叉树结点进行编 它放到一维数组中。 **在编号时，若遇到空 号，然后按其编号将 它放到一维数组中。 **在编号时，若遇到空 子树，应在编号时假 2 3 5 6 9 10 11 12 13 14 4 7 8 定有此子树进行编号， 1 2 3 4 6 7 8 9 12 14 一般二叉树 顺序表示 而在顺序存储时留出 相应位置，由此找到 其双亲、子女、兄弟 结点的位置，但可能 消耗大量空间。 53

极端情形：只有右单支的二叉树 由于一般二叉树必须 1 仿照完全二叉树那样 存储，可能会浪费很 多存储空间，单支树 就是一个极端情况。 3 7 15 1 3 7 15 31 31 **要求一个可存储 31个结点的一维数组，但只在其中 几个位置放有结点数据，其它大多数结点空间都未 利用，又不能压缩到一起，造成很大空间浪费。 （K个结点，需要2k-1个结点空间）

A B C D 例如:深度为4，且仅有4个结点的右单分支 1 1 2 3 4 5 6 …… 15 A 0 B 0 0 0 C … D 1 2 3 4 5 6 …… 15 改进措施：存储节点数据，同时存储节点编号 （对应满二叉树的编号）

二叉树的顺序存储表示 #define MAX_TREE_SIZE 100 // 二叉树的最大结点数 #define TElemType char //二叉树的数据元素类型：char typedef TElemType SqBiTree[MAX_TREE_SIZE]; //二叉树顺序存储的数据类型定义，char一维数组 //0号单元存储根结点 SqBiTree bt; // 定义一个二叉树顺序存储的数据类型变量bt

二叉树的链表表示 • 链表方式 – 便于插入、删除和修改； 数据不需移动； 只需修改指针； 可提高效率。 55

二叉树的链式存储 1. 二叉链表 2．三叉链表 3．双亲链表 *4．线索链表

二叉树的链式存贮结构---二叉链表 考虑： 二叉链表： 二叉树的数据元素之间的关系 任一个结点，最多有两个孩子（直接后继元素） 二叉链表： 将一个结点分成三部分,一部分存放结点本身信息,另外两部分为指针,分别存放左、右孩子的地址。 A B C data LChild RChild LChild data RChild 结点结构 特点：找孩子容易，但不利于找双亲

思考:在n个结点的二叉链表中,有多少个空指针域? 链式存储结构--二叉链表存储示意图 LChild data RChild 结点结构 A B C D E F G ^ root A B C D E F G 逆向思维：司马光砸缸：“让水离人”，而非“救人离水”， 要求空指针，转化为求实指针 ： n个结点共有2n个指针，除了根结点没有指向他的指针外，其余的结点都有且仅有一个指向它的指针，n-1个结点应共有n-1个指针指向，所以空指针为2n-（n-1）=n+1 思考:在n个结点的二叉链表中,有多少个空指针域? n+1

二叉链表的C 语言类型描述如下: 结点结构: lchild data rchild #define TElemType char //二叉树的数据元素类型：char typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; 特点：找孩子容易，但不利于找父亲

root  2．三叉链表 A E B C F D 结点结构: parent lchild data rchild 特点：找孩子容易，找双亲也很容易

三叉链表C 语言的类型描述如下: parent lchild data rchild 结点结构: typedef struct TriTNode { // 结点结构 TElemType data; struct TriTNode *lchild, *rchild; // 左右孩子指针 struct TriTNode *parent; //指向父亲结点 } TriTNode, *TriTree;

A A  A  B B B C D D D E F 二叉树 二叉链表 三叉链表 二叉树链表表示的示例 58  C   C  root A root A  root A  B B B  C   C  C D D D E F  E   F   E   F  二叉树 二叉链表 三叉链表 二叉树链表表示的示例 58

BPTNode nodes[MAX_TREE_SIZE]; 3．双亲链表（静态链表） typedef struct BPTNode { // 结点结构 TElemType data; int *parent; // 指向双亲的指针 char LRTag; //该结点是双亲的左、右孩子标志域 } BPTNode typedef struct BPTree{ // 树结构 BPTNode nodes[MAX_TREE_SIZE]; int num_node; // 结点数目 int root; // 根结点的位置 } BPTree

data parent LRTag 双亲链表示意图—在 L R 1 2 3 4 5 6 A B C D E F 结点结构: 1 2 3 4 5 6 A B C D E F 应用场景：找双亲容易，找孩子不容易，适用于如判断一个元素在哪个集合中，集合的合并等操作。

6.3 二叉树的遍历

二叉树的遍历 一、问题的提出—何谓二叉树的遍历 二、先左后右的遍历算法 三、算法的递归描述 四、中序遍历算法的非递归描述 五、遍历算法的应用举例

一、问题的提出 二叉树的遍历：按一定规律（顺着某一条搜索路径）访问二叉树中的所有结点，使得每个结点均被访问而且仅被访问一次。 注意：“访问”的含义可以很广，如：输出（获取）或修改结点的信息等。 比较“遍地”是黄金。遍地是指整个地上或满地。 遍历：走遍或全部经过 二叉树的遍历,实际上，也就是要把一个非线性结构的二叉树转化为一个线性结构。

“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继，只需从前到后，依次进行即可)，故不需要另加讨论。 但是，二叉树是非线性结构，每个结点有两个后继，则存在按什么样的搜索路径遍历的问题。

分析：二叉树的递归定义： D R L 二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。 可见二叉树有三部分组成： 根结点D，左子树L和右子树R 由此，遍历二叉树的方案有6种： 先左后右： DLR, LDR, LRD 先右后左： DRL, RDL, RLD

先序（先根）的遍历算法：DLR D R L （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 - + a * b c d 若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 若左子树为空树，则空操作；否则， （1）访问左子树的根结点； （2）先序遍历左子树的左子树； （3）先序遍历左子树的右子树。 - + a * b c d e f / 如图所示是用二叉树表示下述表达式： a+b*(c-d)-e/f D R L 先根遍历结果为： -+a*b-cd/ef （波兰式）

中序（中根）的遍历算法：LDR D R L - + a * b c d e f / 若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 若左子树为空树，则空操作；否则， （1）中序遍历左子树的左子树； （2）访问左子树的根结点； （3）中序遍历左子树的右子树。 - + a * b c d e f / D R L 中根遍历结果为： a+b*(c-d)-e/f

“仅知二叉树的先序序列“ abcdefg” 不能唯一确定一棵二叉树，如果同时已知二叉树的中序序列“ cbdaegf”，则会如何？ 由二叉树的先序和中序序列建树 “仅知二叉树的先序序列“ abcdefg” 不能唯一确定一棵二叉树，如果同时已知二叉树的中序序列“ cbdaegf”，则会如何？ 二叉树的先序序列 根 左子树 右子树 二叉树的中序序列 左子树 根 右子树 确定原则： ★由先序序列确定二叉树的根结点， ★有中序序列确定二叉树的左右子树序列。

a a a b c d e f g b c d e f g c c b d a e g f b d e g f 例如: ^ ^ ^ ^ ^ ★由二叉树的后序和中序序列如何确定二叉树？ a a b c d e f g b c d e f g 先序序列中序序列 c c b d a e g f b d a e g f a b e ^ c d f ^ ^ ^ ^ ^ g ^ ^

后序（后根）的遍历算法：LRD D R L - + a * b c d e f / 若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 - + a * b c d e f / D R L 后根遍历结果为： abcd-*+ef/- （逆波兰式）

三、算法的递归描述 lchild data rchild 二叉链表C 语言的类型描述如下: 结点结构: #define TElemType char //二叉树的数据元素类型：char typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;

先序(根）遍历算法的递归描述 若二叉树为空树，则空操作；否则， （1）访问根结点； Visit(T->data); （2）先序遍历左子树； （3）先序遍历右子树。 void Preorder (BiTree T, void(*Visit)(TElemType &e)) { // 先序遍历二叉树 if (T) { Visit(T->data); // 访问结点.可以是输出cout<< T->data Preorder(T->lchild, Visit); // 先序遍历左子树 Preorder(T->rchild, Visit);// 先序遍历右子树 }

{ printf("%d\t", bt->data); Pre(bt->lchild); Pre(bt->rchild); printf(A); pre(T L); A pre(T R); void Pre(BiTree *bt) { if(bt!=NULL) { printf("%d\t", bt->data); Pre(bt->lchild); Pre(bt->rchild); } T B printf(B); pre(T L); T C printf(C); pre(T L); B C T > 左是空返回 pre(T R); T > 左是空返回 T > 右是空返回 T D printf(D); pre(T L); D 返回 T > 左是空返回 T > 右是空返回 主程序 pre( T ) 返回 pre(T R); 返回 返回 先序序列：A B D C pre(T R); 返回

中序遍历算法的递归描述 若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 void Inorder (BiTree T, void( *Visit)(TElemType &e)) { // 中序遍历二叉树 if (T) { Inorder(T->lchild, Visit); // 中序遍历左子树 Visit(T->data); // 访问根结点 Inorder(T->rchild, Visit);// 中序遍历右子树 }

二叉树的遍历过程（先根，中根，后根）

算法分析 3种遍历算法不同之处仅在于访问根结点、遍历左子树、遍历右子树的先后关系。若不考虑Visit()语句，则三种遍历方法完全相同（访问路径是相同的，只是访问结点的时机不同） 。 从虚线的出发点到终点的路径上，每个结点经过3次。 第1次经过时访问＝先序遍历 第2次经过时访问＝中序遍历 第3次经过时访问＝后序遍历 三种遍历算法均是递归算法： 二叉树的定义本身就是递归的； 递归和栈密切联系：递归过程实际就是对栈的操作过程 可以直接通过对栈的操作，来把递归算法写为非递归算法

四、中序遍历算法的非递归过程 –分析（1） A B C D E F G p i p->A (1) A B C D E F G p i p->B (2) A B C D E F G p i p->A p->B p->C (3) p=NULL A B C D E F G i p->A p->B 访问：C (4) 弹出栈顶C 弹出栈顶B

p A B C D E F G i p->A 访问：C B (5) A B C D E F G i p->A p->D (6) E入栈 D入栈 A B C D E F G i p->A p->D p->E 访问：C B p (7) A B C D E F G i p->A p->D 访问：C B E p (8) G入栈 弹出栈顶E

A B C D E F G i p->A p->D p->G 访问：C B E P=NULL (9) A B C D E F G i p->A p->D 访问：C B E G p (10) A B C D E F G i p->A p->F 访问：C B E G D p (12) A B C D E F G i p->A 访问：C B E G D p (11)

A B C D E F G i 访问：C B E G D F A p (14) A B C D E F G i p->A 访问：C B E G D F p=NULL (13) A B C D E F G i 访问：C B E G D F A p=NULL (15)

中序遍历的非递归算法思路： 设待遍历的二叉树的根结点指针为T（算法开始时，令p=T），则可能出现两种情况： 1、若p不空，则先按中序次序遍历T（p）的左子树，然后打印p->data,再按中序次序遍历p的右子树。 为此，在遍历p的左子树前要保留根结点指针p,以便返回后再打印p->data，接着遍历其右子树。 2、若p为空，则表明以p为根的二叉树遍历完毕，应该返回（同时也表明对某子树 T’ 的左子树p遍历完毕，下面应该访问 T’的根结点，并对其右子树遍历，如上图⑺）。此时，若栈不空，则栈顶元素一定为T’，取出栈顶的指针并赋予p，在访问完p之后，继续遍历其右子树；若栈为空，则整个二叉树遍历完毕。

中序遍历的非递归算法描述 开始 初始化栈S p=NULL 初始化指针p=T p入栈 p=p->LChild 栈顶元出栈：→p 打印p->data p=p->RChild 结束 N Y P和栈均空吗？ Status InOrderTraverse( BiTree T, status (*Visit)(TElemType e )) { InitStack( S ); p = T; while( p || !StackEmpty( S )) { if( p )// 根指针进栈，遍历左子树 { Push( S, p ); p = p->LChild;} else // 根指针出栈，访问根结点,遍历右子树 { Pop( S, p ); Visit( p->data); p = p->RChild; // 右子树 }// else }// while return OK; }// InOrderTraverse

五、遍历算法的应用举例 1、统计二叉树中结点的个数(先序遍历) 2、求二叉树的深度(后序遍历) 3、复制二叉树(后序遍历) 说明: 二叉树的所有算法都是建立在遍历的基础上的，故二叉树的应用也是以遍历为基础，或者说以遍历为主框架。在应用遍历算法时，不同的问题需要对其中的“访问结点”操作做适当的修改。 1、统计二叉树中结点的个数(先序遍历) 2、求二叉树的深度(后序遍历) 3、复制二叉树(后序遍历) 4、建立二叉树的存储结构

1、统计二叉树中结点的个数 算法基本思想: 先序(或中序或后序)遍历二叉树，在遍历过程中查找结点，并计数。需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是该结点非空，则计数器增1。 void Preorder (BiTree T, void( *Visit)(TElemType &e)) { if (T) { Visit(T->data); // 访问结点 Preorder(T->lchild, Visit); // 先序遍历左子树 Preorder(T->rchild, Visit);//先序 遍历右子树 }

统计二叉树中结点的个数 void CountNode (BiTree T, int& node) if ( T ) { node ++; CountNode( T->lchild, node); CountNode( T->rchild, node); } // if } // CountNode

统计二叉树中叶子结点的个数 算法基本思想: 先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。 void Preorder (BiTree T, void( *Visit)(TElemType& e)) { if (T) { Visit(T->data); // 访问结点 Preorder(T->lchild, Visit); // 先序遍历左子树 Preorder(T->rchild, Visit);//先序 遍历右子树 }

void CountLeaf (BiTree T, int& count) {//在实际使用时，count作为全局变量，其初始值为0 if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; // 对叶子结点计数 CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); } // if } // CountLeaf 重写算法：要么叶子数为0，要么为左右子树叶子数之和。

首先分析二叉树的深度和它的左、右子树深度之间的关系。 2、求二叉树的深度(后序遍历) 算法基本思想: 首先分析二叉树的深度和它的左、右子树深度之间的关系。 从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。因此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。

求二叉树的深度的算法(后序遍历) int Depth (BiTree T ){ // 返回二叉树的深度 if (T ) { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight); } else depthval = 0; return depthval;

构造二叉树的存储结构 int CreateBiTree(BiTree &T) { scanf(&ch); / /cin>>ch; if (ch==' ') T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = ch; // 生成根结点 CreateBiTree(T->lchild); // 构造左子树 CreateBiTree(T->rchild); // 构造右子树 } return OK; } // CreateBiTree

何谓线索二叉树 6.3.2线索二叉树 线索链表的遍历算法 如何建立线索链表 （注：此部份内容了解即可，一般用的不是很多，工作面试，研究生考试一般都不涉及）

例如: A B C D E F G H K 一、何谓线索二叉树？ 先序序列: A B C D E F G H K 中序序列: 说明：通过遍历二叉树，可把二叉树的非线性结构转化为线性结构，求得结点的一个线性序列。 问题：在以二叉链表表示二叉树时，各种线性序列中结点间的前驱和后继关系 只能在遍历时才能得到。 例如: A B C D E F G H K 先序序列: A B C D E F G H K 通过遍历二叉树，可求得结点的一个线性序列。在任一序列中，除了第一个和最后一个结点外，其余结点又且仅有一个直接前驱和直接后继。但是在以二叉链表表示二叉树时，这些不同遍历序列的直接前驱和直接后继信息只能在遍历过程中才能得到。为此我们可以在二叉链表的结点结构中增设两个指向前驱和后继的指针域，但考虑到二叉链表中的2n个指针域中，有n+1个空指针域，为充分利用空间，可以考虑用这些空指针域来保存前驱和后继指针信息。 中序序列: B D C A H G K F E 后序序列: D C B H K G F E A

A B C D E F G H K 包含 “线索” 的存储结构，称作 “线索链表” E ^ ^ B C ^ ^ D ^ 指向该线性序列中的“前驱”和 “后继” 的指针，称作“线索”（以区别于二叉链表中的孩子指针，利用二叉链表中空指针做线索） 包含 “线索” 的存储结构，称作 “线索链表” A B C D E F G H K ^ B E ^ C ^ ^ D ^

在二叉链表的结点中增加两个标志域，并作如下规定： 对线索链表中结点的约定： 在二叉链表的结点中增加两个标志域，并作如下规定： lchild LTag data RTag rchild 若该结点的左子树不空，则lchild域的指针指向其左子树， 且左标志域LTag的值为“指针 Link”； 否则，lchild域的指针指向其“前驱”，且左标志域LTag的值为“线索 Thread” 。 以这种结构构成的二叉链表作为二叉树的 存储结构,叫做线索链表,其中指向结点前驱与 后继的指针叫做线索，加上线索的二叉树称为 线索二叉树。 若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域RTag的值为 “指针 Link”；否则，rchild域的指针指向其“后继”，且右标志RTag的值为“线索Thread”。 0 lchild域指示结点的左孩子，表示lchild为左孩子指针 LTag= 1 lchild域指示结点的前驱，表示lchild为线索 0 rchild域指示结点的右孩子，表示rchild为右孩子指针 RTag= 1 rchild域指示结点的后驱，表示rchild为线索

先序线索二叉树举例 A B D C E T 先序序列：ABCDE 先序线索二叉树 1 ^ A B C D E

中序线索二叉树举例 A B D C E T 中序序列：BCAED 中序线索二叉树 A B C D E ^ 1 1 ^ 1 1 1 1

后序线索二叉树举例 A B D C E T 后序序列：CBEDA 后序线索二叉树 A B C D E 1 1 ^ 1 1 1 1

中序序列：BCAED 中序线索二叉树 头结点： LTag=0, lchild 指向根结点 RTag=1, rchild指向遍历序列中 1 ^ 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 0 1 头结点： LTag=0, lchild 指向根结点 RTag=1, rchild指向遍历序列中 最后一个结点 遍历序列中第一个结点的lchild和最后一个结点的rchild域都指向头结点

typedef enum { Link, Thread } PointerThr; 线索链表的类型描述： typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索 typedef struct BiThrNod { TElemType data; struct BiThrNode *lchild, *rchild; // 左右指针 PointerThr LTag, RTag; // 左右标志 } BiThrNode, *BiThrTree;

for ( p = firstNode(T); p; p = Succ(p) ) 二、线索链表的遍历算法 由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。 某种遍历序列中的第一个结点 求该结点的后继 for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);

例如: 对中序线索化链表的遍历算法 ※ 中序遍历的第一个结点？ 左子树上处于“最左下” （没有左子树）的结点。 A B C D E 左子树上处于“最左下” （没有左子树）的结点。 ※求中序线索化链表中某结点的后继？ 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 0 1 若无右子树，则为后继线索所指结点； 否则为对其右子树进行中序遍历时访问的第一个结点。

{ //T指向头结点,头结点的lchild左链指向根结点，中序遍历二叉线索树的非递归算法, void InOrderTraverse_Thr (BiThrTree T, void (*Visit)(TElemType e)) { //T指向头结点,头结点的lchild左链指向根结点，中序遍历二叉线索树的非递归算法, //对每个数据元素调用函数Visit p = T->lchild; // p指向根结点 while (p != T) // 空树或遍历结束时，p==T { while (p->LTag==Link) p = p->lchild; //找第一个结点 if(!Visit(p –>data)) return error; //访问该结点 while (p->RTag==Thread && p->rchild!=T) { p = p->rchild; Visit(p->data); } // 访问后继结点 p = p->rchild; // p进至其右子树根 }// 若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。 } // InOrderTraverse_Thr p->RTag==Thread 如 113页的C结点

三、如何建立线索链表？ 在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre, 并始终保持指针pre指向当前访问的指针p所指结点的前驱。

void InThreading(BiThrTree p) { if (p) { //中序遍历 对以p为根的非空二叉树进行线索化 InThreading(p->lchild); // 左子树线索化 if (!p->lchild) // 建前驱线索，pre是p的前驱 { p->LTag = Thread; p->lchild = pre; } if (!pre->rchild) // 建后继线索，即p是pre的后继 { pre->RTag = Thread; pre->rchild = p; } pre = p; //右子树线索化前pre = p;保持pre指向p的前驱 InThreading(p->rchild); // 右子树线索化 } // if } // InThreading A B D C E T 中序序列：BCAED 中序线索二叉树 1 ^ pre p

Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) { //中序遍历二叉树T，并将其线索化 构建中序线索链表，Thrt指向头结点 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode)))) exit (OVERFLOW); Thrt->LTag = Link; Thrt->RTag =Thread; Thrt->rchild = Thrt; // 添加头结点 } // InOrderThreading Thrt 0 1 if (!T) Thrt->lchild = Thrt; // 树空时，回指 else { Thrt->lchild = T; pre = Thrt; // Thrt->lchild 指向树根 T InThreading(T); pre->rchild = Thrt; // 处理最后一个结点，（图示） pre->RTag = Thread; Thrt->rchild = pre; } return OK;

头结点： LTag=0, lchild 指向根结点 RTag=1, rchild 指向遍历序列中 最后一个结点 A B D C E T 中序序列：BCAED 中序线索二叉树 1 ^ A B C D E 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 0 1 头结点： LTag=0, lchild 指向根结点 RTag=1, rchild 指向遍历序列中 最后一个结点 遍历序列中第一个结点的lchild和最后一个结点的rchild都指向头结点

6.4 树和森林

树的三种存储结构 一、双亲表示法 二、孩子链表表示法 三、树的二叉链表(孩子-兄弟） 存储表示法

一、双亲表示法 实现：定义结构数组存放树的结点，每个结点含两个域： 数据域（data）：存放结点本身信息 双亲域（parent）：指示本结点的双亲结点在数组中位置 data parent typedef struct node { char data; int parent; } PT; PT tree[M]; 简单实现： 特点：找双亲容易，找孩子难

一、双亲表示法示意图 0号单元不用或 用于存结点个数 如何找某结点的 孩子结点？ 该结点在数组中的位序与某个结点的parent相等。 a b c d e f h g i 6 1 2 3 4 5 7 8 9 data parent 9 a c d e f g h i b 1 1 2 2 3 5 如何找某结点的 孩子结点？ 5 5 该结点在数组中的位序与某个结点的parent相等。

data parent C语言的类型描述: 结点结构: #define MAX_TREE_SIZE 100 typedef struct PTNode { //结点结构 Elem data; int parent; // 双亲位置域 } PTNode; typedef struct { //树结构 PTNode nodes[MAX_TREE_SIZE]; int r, n; // 根结点的位置和结点个数 } PTree;

多重链表 结点同构：结点的指针个数相等，为树的度D 结点不同构：结点指针个数不等，为该结点的度d 多重链表： 每个结点设有多个指针域，分别指向其子树的根。 结点同构：结点的指针个数相等，为树的度D (浪费存储单元，很多结点的孩子少于D，指针域为空。) 结点不同构：结点指针个数不等，为该结点的度d (按需分配指针域，但操作不便 data child1 child2 …… childD data degree child1 child2 …… childd

typedef struct { child next data FirstChild 二、孩子链表表示法--顺序存储与链式存储相结合 typedef struct CTNode { int child; //孩子结点在数组中的位置 struct CTNode *next; } *ChildPtr; 孩子结点结构: child next typedef struct { Elem data; ChildPtr firstchild; // 孩子链表的头指针 } CTBox; CTBox tree[M]; //结点采用顺序存储 双亲结点结构 data FirstChild

二、孩子链表表示法示意图 a b c d e f h g i data child next 6 1 2 3 4 5 7 8 9 a c d First Child child next 6 1 2 3 4 5 7 8 9 a c d e f g h i b 2 3 ^ 4 5 ^ 6 ^ ^ 9 7 8 ^ ^ ^ ^ ^

带双亲的孩子链表 6 1 2 3 4 5 7 8 9 a c d e f g h i b data firstchild ^ parent parent a b c d e f h g i

三、孩子兄弟表示法（二叉链表表示法） 特点：操作容易，(但破坏了树的层次) 实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点 data nextsibling firstchild 特点：操作容易，(但破坏了树的层次) 根结点没有兄弟（无右指针） a b c d e f g h i ^ a b c d e f h g i ^ ^ ^ ^ ^ ^ ^ ^ ^

firstchild data nextsibling 结点结构: firstchild data nextsibling typedef struct CSNode{ Elem data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree;

树与二叉树（孩子兄弟二叉树）的转换 对应 A B C D E 二叉树 A C B E D 树 A ^ ^ B C ^ D ^ ^ E ^ 存储 解释 A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^

将树转换成二叉树 加线：在兄弟之间加一连线 旋转：以树的根结点为轴心，将整树顺时针转45° 抹线：对每个结点，除了其左孩子外，除去其与其余孩子之间的连线 旋转：以树的根结点为轴心，将整树顺时针转45° A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I 树转换成的二叉树时其右子树一定为空

将二叉树转换成树 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来 抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构 A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I p p A B C D E F G H I

由森林转换成二叉树的转换规则为: 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构 A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J

由二叉树转换为森林的转换规则为： 将二叉树转换成树 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树（二叉树→树） 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，…，沿分支找到的所有右孩子,都与p的双亲用线连起来 抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构 将二叉树转换成树 A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J

6.4.3 树的遍历

若树不空，则先依次后根遍历各棵子树，然后访问根结点。 树的遍历可有三条搜索路径: 先根(序)遍历: 若树不空，则先访问根结点，然后依次先根遍历各棵子树。 后根(序)遍历: 若树不空，则先依次后根遍历各棵子树，然后访问根结点。 按层次遍历: 若树不空，则自上而下自左至右访问树中每个结点。 注：对于树而言，无中序遍历

A B C D E F G H I J K 先根遍历时结点的访问次序： A B E F C D G H I J K 后根遍历时结点的访问次序： E F B C I J K H G D A 层次遍历时结点的访问次序： A B C D E F G H I J K

6.5 哈夫曼树与哈夫曼编码 最优树的定义 如何构造最优树 前缀编码

有关术语 路径：从树中一个结点到另一个结点之间的结点与分支（边）构成这两个结点之间的路径。 路径长度：路径上的分支（边）数 树的路径长度：从树根到每一个叶子结点的路径长度之和 树的带权路径长度：树中所有叶子结点的带权路径（Weighted Path Length ） 长度之和。 r d c a b 2 4 7 5 第k个叶子结点到根的路径长度 — 个叶子结点的权值 第 叶子结点的个数 其中： 记作： k WPL 1 n l w lk wk - = å 在实际的应用中，人们常常给树的每个结点赋予一个具有某种实际意义的实数，我们称该实数为这个结点的权。 例如：

例 有4个结点a,b,c,d，其权值分别为7，5，2，4， 构造有4个叶子结点的二叉树 WPL=7*2+5*2+2*2+4*2=36 a b c d 7 5 2 4 WPL=7*3+5*3+2*1+4*2=46 WPL=7*1+5*2+2*3+4*3=35

哈夫曼树（Huffman树）—— 又称最优二叉树，它是n个带权叶子结点构成的所有二叉树中，带权路径长度（WPL）最小的二叉树。 教材定义：设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则WPL最小的二叉树叫哈夫曼树或最优二叉树。

构造哈夫曼树 Huffman给出构造最优二叉树的算法，具体构造哈夫曼算法的步骤如下：  ⑴ 根据给定的 n 个权值{w1, w2, …, wn}构成 n 棵二叉树的集合 F ={T1, T2, …, Tn} ，其中每棵二叉树 Ti (1≤i≤n) 中只有一个带权为wi的根结点，其左右子树均空； ⑵ 在 F 中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 　⑶ 在F中删除这两棵树，同时将新得到的二叉树加入 F 中。 　重复(2)和(3)，直到 F 只含一棵树为止。这棵树便是所求的哈夫曼树。

例如，对5个权值 {5,6,2,9,7} 构造最优二叉树的过程如动画所示

例如: 已知权值 W={ 5, 6, 2, 9, 7 } 5 6 2 9 7 6 9 7 7 5 2 9 7 13 5 2 6 7

9 7 13 5 2 6 7 29 1 13 16 1 1 6 7 9 7 1 00 01 10 5 2 110 111

Huffman树的应用：寻求最佳判断过程 根据出现的频率决定比较的次数 Huffman树的应用：寻求最佳判断过程 例：编制一个将百分制转换成五级分制的程序 0～59 ———————————————————— bad 60～69 ———————————————————— pass 70～79 ———————————————————— general 80～89 ———————————————————— good 90～100 ———————————————————— excellent ………………………5% ………………………15% ………………………40% ………………………30% ………………………10% a<60 Y N if (a<60) b=“bad”; else if (a<70) b=“pass”; else if (a<80) b＝“general”; else if (a<90) b=“good”; else b=“excellent”; 不及格 a<70 Y N 判定树 及格 a<80 Y N 中等 a<90 Y N 良好 优秀

出现的频率： 5 15 40 30 10 100 70≤a<80 Y N 40 60 中等 80≤a<90 Y N 30 30 70～79 30 30 良好 60≤a<70 N Y 80～89 a<60 15 15 及格 Y N 60～69 0～59 不及格 优秀 5 10 90～100

改造成每个判定框只有一次比较的判定树： a<80 Y N a<70 a<90 Y N N Y a<60 中等 良好 优秀 Y N 不及格 及格 实践证明：按照此棵判定树，输入10000个输入数据，原判定树需 进行31500次比较，此判定树需进行22000次比较

6.6.2 哈夫曼编码 在电报通讯中，电文是以二进制的0，1序列传送的。 编码： 在发送端，发送的电文 二进制序列 译码： 6.6.2 哈夫曼编码        在电报通讯中，电文是以二进制的0，1序列传送的。 编码： 在发送端，发送的电文 二进制序列 译码： 在接收端，接到的二进制序列 电文

（1） 如何使电报编码变短，非前缀编码会出现二义性； （2） 用二叉树可以构造前缀编码； （3） 由哈夫曼树得到最优编码 哈夫曼编码提出的背景： （1） 如何使电报编码变短，非前缀编码会出现二义性； （2） 用二叉树可以构造前缀编码； （3） 由哈夫曼树得到最优编码 哈夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。 它的基本原理是：频繁使用的信息用较短的代码代替，较少使用的信息用较长的代码代替，每个信息的代码各不相同。这些代码都是二进制码，且码的长度是可变的。

1）等长编码 例：假设传送的电文为英文序列‘ABACCDA’ A B C D 00 01 10 11 则电文编码为“00010010101100”，总长14， 译码时：两位一分

2）不等长编码 使用频率： 3 1 2 1 A B C D 0 00 1 10 电文编码“000011010”，总长9 一般，在英文字母a—z中，e的使用频率比q,z要大得多，使用频率高的用短码，使用频率低的用长码。编码不等长，但大部分情况下电文总长度会减少 使用频率： 3 1 2 1 A B C D 0 00 1 10 电文编码“000011010”，总长9 译码：AAAA 或 BB 或 ABA，译码不唯一，无法正确译码！ 原因：A(0)为B(00)的前缀

3）前缀编码（有的教材又称无前缀编码） 设计不等长编码时，任一字符的编码不是另一字符编码的前缀，这种编码称为前缀编码（只有前缀编码才能被正确译码）。 如何得到使电文长度最短的二进制前缀编码？ 假设电文中每种字符出现的次数为Wi, 其编码长度为li ,电文中有n种字符，则电文总长为： 使它最小，对应到二叉树上，置 Wi为叶子的权 li为根到叶子的路径长度 则设计电文总长最短的问题变成设计哈夫曼树的问题

则： A ：0 C ：10 B ：110 D ：111 由此可见该编码是前缀编码 待传电文ABACCDA 的编码：‘0110010101110’， 总长13 例：A: 3 B:1 C:2 D: 1 0 1 0 1 0 1 哈夫曼编码： 约定: 树中的左分支表示字符‘0’ 树中的右分支表示字符‘1’ 编码：从根到叶子的路径上分支字符组成的字符串 作为该叶子结点字符的编码。 注：利用二叉树的编码是前缀编码，利用最优二叉树得到哈夫曼编码 A C B D

Huffman编码的特点 Huffman编码是一种前缀编码。解码时,不会混淆。 即任一字符的编码不会是另一字符的编码前缀。 同样的元素集合，产生的haffman树及编码都可能是不一样的。但编码方和译码方的哈夫曼树必须一致， 否则不能正确译码。

Huffman编码应用 主要用途是实现数据压缩： 设给出一段报文： CAST CAST SAT AT A TASA 的频率(次数)是W＝{ 2, 7, 4, 5 }。 若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11 则平均总编码长度为( 2+7+4+5 ) * 2 = 36。

若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符出现概率为{ 2/18, 7/18, 4/18, 5/18 },化整为{ 2, 7, 4, 5 }。以它们为各叶结点上的权值, 建立Huffman树。左分支赋0，右分支赋1，得Huffman编码(变长编码)。

A : 0 T : 10 C : 110 S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3=35，比等长编码的情形要短。 总编码长度正好等于Huffman树的带权路径长度WPL。 Huffman编码是一种无前缀编码，解码时不会 混淆。 √CAST: 110011110 请给出11001010111对应的字符串： 利用哈夫曼树进行解码。

译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走；一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。 C B D 1 例 电文编码：‘0110010101110’ 译文只能是“ABACCDA” 注意：编码方和译码方的哈夫曼树必须一致， 否则不能正确译码

由n个叶子结点构成的哈夫曼树共有多少个结点？有多少度为2的结点？ 哈夫曼编码算法的实现 首先要清楚 2 个问题： 由n个叶子结点构成的哈夫曼树共有多少个结点？有多少度为2的结点？ n个结点经过n-1次合并，得到一棵哈夫曼树，每次和并得到一个新结点。 共计 : n + n-1 =2n -1 度为2的结点个数：n-1 哈夫曼树有没有度为1的结点？ 没有，仅有度为2的结点和叶子结点 n个结点经过n-1次合并，最后得到一棵哈夫曼树，每次和并得到一个新结点。中没有度为1的结点

int weight ; /* 用来存放各个结点的权值*/ 哈夫曼编码算法的实现 一棵有n个叶子的哈夫曼树共有 2n-1 个结点，可以用一个大小为 2n-1 的一维数组存放哈夫曼树的各个结点。 由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。静态三叉链表描述如下： typedef struct { int weight ; /* 用来存放各个结点的权值*/ int parent, LChild, RChild ; /*指向双亲、 孩子结点的指针*/ } HTNode; typedef char **HuffmanCode ; /*动态分配数组存储哈夫曼编码*/ n个结点经过n-1次合并，最后得到一棵哈夫曼树，每次和并得到一个新结点。中没有度为1的结点 typedef HTNode HuffmanTree[m];

一、构造Huffman树 二、 输出Huffman编码 对Huffman编码器程序的解释： HT[s1].parent=? 一、构造Huffman树 注1：算法开始时，把每个子树的双亲都设为空（0）。 注2：各个子树 权值序列并没有重新排序，而是顺序存放。挑选两个最小权值是用逐次比较法，用s1和s2记录对应位置； 注3：合并后生成的新树依次顺序存放，它的两个子树并不删除，而是修改这两个子树的双亲指针（i）；下一轮找最小权值时，凡是双亲指针不空（0）的就跳过去（不再考虑）。 二、 输出Huffman编码 注：从叶子开始按“左0右1”将每个叶子的哈夫曼码存入对应数组（为每个叶子设立一个向量，从“个位”开始存放）。

创建哈夫曼树并求哈夫曼编码的算法如下（自学）： HuffmanTree CrtHuffmanTree(HuffmanTree *ht , HuffmanCode *hcode, int * w, int n) { /*w存放n个权值, 构造哈夫曼树ht, 并求出哈夫曼编码hc */ HuffmanTree ht;  m=2*n-1;  ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1; i<=n; i++) ht[i] ={w[i], 0, 0, 0}; /*叶子结点初始化，数组前n个*/ for(i=n+1; i<=m; i++) ht[i]={0, 0, 0, 0}; /*非叶子结点初始化，数组后n-1个*/  

ht［s1］.parent=i; ht［s2］.parent=i;  for(i=n+1; i<=m; i++) /*创建非叶子结点, 建哈夫曼树*/ { /*在ht［1］~ht［i-1］的范围内选择两个parent为0且weight最小的结点， 其序号分别赋值给s1、 s2返回*/ select(ht, i-1, s1, s2);  ht［s1］.parent=i; 　ht［s2］.parent=i;  ht［i］.LChild=s1; 　ht［i］.RChild=s2;  ht［i］.weight=ht［s1］.weight+ht［s2］.weight; } /*哈夫曼树建立完毕*/ /*从叶子结点到根， 逆向求每个叶子结点对应的哈夫曼编码*/ hcode=(HuffmanCode)malloc((n+1)*sizeof(char *)); /*分配n个编码的头指针*/ cd=(char * )malloc(n * sizeof(char )); /*分配求当前编码的工作空间*/ cd［n-1］＝′\0′； /*从右向左逐位存放编码， 首先存放编码结束符*/

for(c=i, p=ht［i］.parent; p! =0; c=p, p=ht［p］.parent) /*从叶子到根结点求编码*/ for(i=1; i<=n; i++) /*求n个叶子结点对应的哈夫曼编码*/ { start=n-1; /*初始化编码起始指针*/ for(c=i, p=ht［i］.parent; p! =0; c=p, p=ht［p］.parent) /*从叶子到根结点求编码*/ if(ht［p］.LChild==c) cd［--start］=′0′; /*左分支标0*/  else cd［--start］=′1′; /*右分支标1*/ hcode［i］=(char *)malloc((n-start)*sizeof(char)); /*为第i个编码分配空间*/ strcpy(hcode［i］, &cd［start］);  } free(cd); }

weight parent leftChild rightChild 建立Huffman树的过程如图所示： weight parent leftChild rightChild 1 2 3 4 5 6 7 5 2 4 -1 -1 -1 7 5 2 4 来源于复旦大学课件：这里使用了0号单元，故都初始化为-1 70

weight parent leftChild rightChild 7 -1 -1 -1 5 2 4 6 -1 4 -1 -1 2 -1 -1 3 -1 1 2 3 4 p1 p2 i 7 5 6 5 6 -1 -1 -1 2 4 71

weight parent leftChild rightChild 7 11 7 -1 -1 -1 p1 p2 i 5 2 4 6 11 5 -1 4 -1 -1 2 1 -1 -1 3 4 -1 1 2 3 4 5 5 6 2 4 -1 -1 -1 6 72

weight parent leftChild rightChild 7 6 -1 -1 -1 18 1 2 3 4 5 2 4 6 5 4 -1 2 -1 3 7 11 2 5 6 4 p2 i 5 6 11 18 6 -1 -1 1 0 -1 4 5 -1 73

Huffman Code Construction 80 76 93 125 D L R S N I H 40 41 61 65 71 73 55 C U 31 27

Huffman Code Construction 80 76 93 125 D L R S N I H 40 41 61 65 71 73 58 55 C U 31 27

Huffman Code Construction 80 76 81 93 125 D L R S N I H 40 41 61 65 71 73 58 55 C U 31 27

Huffman Code Construction 80 76 81 93 125 113 D L R S N I H 40 41 61 65 71 73 58 55 C U 31 27

Huffman Code Construction 80 76 81 93 126 125 113 D L R S N I H 40 41 61 65 71 73 58 55 C U 31 27

Huffman Code Construction 80 76 81 93 126 144 125 113 D L R S N I H 40 41 61 65 71 73 58 55 C U 31 27

Huffman Code Construction 156 A O T E 80 76 81 93 126 144 125 113 D L R S N I H 40 41 61 65 71 73 58 55 C U 31 27

Huffman Code Construction 156 174 A O T E 80 76 81 93 126 144 125 113 D L R S N I H 40 41 61 65 71 73 58 55 C U 31 27

Huffman Code Construction 156 174 238 A O T E 81 126 144 113 D L R S N I H 58 C U

Huffman Code Construction 156 174 270 238 A O T E 80 76 81 93 126 144 125 113 D L R S N I H 40 41 61 65 71 73 58 55 C U 31 27

Huffman Code Construction 330 156 174 27.0 238 A O T E 80 76 81 93 126 144 125 113 D L R S N I H 40 41 61 65 71 73 58 55 C U 31 27

Huffman Code Construction 330 508 156 174 270 238 A O T E 80 76 81 93 126 144 125 113 D L R S N I H 40 41 61 65 71 73 58 55 C U 31 27

Huffman Code Construction 838 330 508 156 174 270 238 A O T E 80 76 81 93 126 144 125 113 D L R S N I H 40 41 61 65 71 73 58 55 C U 31 27

Huffman Code Construction 125 Freq 93 80 76 73 71 61 55 41 40 E Char T A O I N R H L D 31 27 C U 65 S 0000 Fixed 0001 0010 0011 0100 0101 0111 1000 1001 1010 1011 1100 0110 110 Huff 000 011 001 1111 11100 11101 838 Total 4.00 3.62

应用实例1 集合的表示（了解） Two operations considered here S1={0, 6, 7, 8}, S2={1, 4, 9}, S3={2, 3, 5} Two operations considered here Disjoint set union S1  S2={0,6,7,8,1,4,9} Find(i): Find the set containing the element i. 3  S3, 8  S1 1 2 8 4 9 3 5 6 7 Si  Sj = 

Make one of trees a subtree of the other Disjoint Set Union（不相交集合的并操作） Make one of trees a subtree of the other 1 4 9 1 6 7 8 9 6 7 8 4 Possible representation for S1 union S2

*Data Representation of S1S2and S3 6 7 8 4 1 9 2 3 5

Array Representation for Set int find1(int i) { for (; parent[i]>=0; i=parent[i]); return i; } void union1(int i, int j) parent[i]= j;

*Trees obtained using the weighting rule weighting rule for union(i,j): if # of nodes in i < # in j then j the parent of i

Trees achieving worst case bound  log28+1

查找并做路径压缩 1 1 6 7 2 4 2 4 3 6 3 5 5 7

本章小结 • 知识点 – 树、二叉树、二叉树的基本性质 – 二叉树上的操作 – 线索二叉树 – 树和森林的基本操作 – Huffman树 • 知识点 – 树、二叉树、二叉树的基本性质 – 二叉树上的操作 – 存储、遍历 – 线索二叉树 – 建立线索、遍历 – 树和森林的基本操作 – 存储、与二叉树的转换 – Huffman树 – 建立、应用 85

本章小结 存储结构 遍历 1、定义和性质 树 2、存储结构 森林 3、遍历 4、线索化：线索树 哈夫曼树 先序遍历 后序遍历 顺序结构 双亲表示 孩子表示 孩子兄弟 存储结构 遍历 1、定义和性质 树 二叉树 森林 顺序结构 链式结构 2、存储结构 二叉链表 线索链表 中序遍历 后序遍历 先序遍历 3、遍历 遍历 哈夫曼树 先序线索树 中序线索树 后序线索树 先 序 遍 历 后 序 遍 历 4、线索化：线索树 哈夫曼编码

1. 熟练掌握二叉树的结构特性，了解相应的证明方法。 本章需要掌握的内容 　1. 熟练掌握二叉树的结构特性，了解相应的证明方法。 　 2. 熟悉二叉树的各种存储结构的特点及适用范围。 　 3. 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。

　　4. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。

　　5. 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握 1 至 2 种建立二叉树和树的存储结构的方法。 　　6. 学会编写实现树的各种操作的算法。 　　7. 了解最优二叉树的特性，掌握建立最优二叉树和哈夫曼编码的方法。

作 业 习题集六