中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）Ch6 树.pdf_大学文库

2014/4/7 1 数据结构 Ch.6 树 1 计算机学院肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj Ch.6 树  树形结构：  二叉树，树，森林等  结点间有分支，具有层次关系  特征：  每个结点最多只有一个直接前驱，但可有多个直间后 2 继．  开始结点 —— 根  终端结点 —— 叶  其余结点 —— 内部结点  应用：家谱、行政架构等，计算机系统中的文件目录等 §６.１树的概念  Def: 树是n (n>=0) 个结点的有限集Ｔ，Ｔ为空时称为空树，否则它满足：  有且仅有一个特定的称为根的结点；  其余结点可分为m (m>=0) 个互不相交的子集Ｔ1 ，Ｔ2，…Ｔm，其中每个子集本身又是一棵树，并称之为根的子树． 3 §６.１树的概念  递归定义：刻画了树的固有特性：非空树由若干棵子树构成，子树由较小子树构成．  表示： 4 §６.１树的概念  术语： ① 结点的度：结点拥有的子树数目（树的度） ② 叶子：终端结点，度为０的结点 ③ 分支结点：非终端结点，度＞０ ④ 内部结点：根之外的分支结点 5 ⑤ 根：开始结点 ⑥ 孩子、双亲：某结点的子树的根称为该结点的孩子，该结点为孩子的双亲直接前驱（双亲）直接后继（孩子） ⑦ 兄弟：同一双亲的孩子互为兄弟 §６.１树的概念  术语： ⑧ 路径：道路（自上而下）若存在一结点序列k1,k2,…，kj ，使得ki 是ki+1的双亲（１<=i<=j-1），则称该序列是从k1到kj 的一条路径或道路，路径长度为边数j-1. 6 ⑨ 祖先和子孙：若k到ks有一路径，则k是ks的祖先，ks 是k的子孙．  结点Ａ的祖先是从根到Ａ的路径上所经过的所有结点．  结点Ａ的子孙是以Ａ为根的子树中的所有结点．  真祖先和真子孙不包含自身 ⑩ 层数从根起算（为１或０），其余结点的层数是其双亲的层数＋１

201447 86.1树的概念 86.1树的概念 ■术语： ■逻辑特征： 11高（深）度：制中结点的量大层数 √父子关系（非线性关系）：任一结点至多有一直接前 12堂兄弟：双亲在同一层的销点互为堂兄弟驱（双亲）结点，但可有多个直接后锤（子女）结 13有序树、无序树：点，若每结疯的各子树香成是从左到贿有次序（不能互换） √开始结点：根的，则称为有序制，否则为无序刺。终结点：叶其余结点为内部结点。 √粗先与子孙关系：是对父子关系的延拓，它定义了制树 ●，●●不可的有序制，一般讨论有序制中结点的纵向关暴。 14森林：m(m>=0)棵互不相交的树的集合横向关系：有序树定义了同一组兄弟间的从左到右的树和森林非常接近：去树根=>森林长幼关系，可将其延拓到结点间的横向次序：k,和k 森林加上一根=>树是兄弟，k,在左，则k,的任一子孙在K的任一于孙的左边。 86.2二叉树 s6.2.1二叉树的定义是一种特殊的树型结构，每个结点至多只有二棵子树，一般树可转换为二叉树，形态计算机用途甚广. 0 O 86.2.1二叉树的定义 (a) ■Def:二叉树是n(n>=0)个结点的有限集，它或者 8花含2变的汉是空集，或由一个根结点及两棵互不相交的，分 ■与度为2的有序树区别：别称作根的左子树和右子树的二叉树组成当某一结点只有当然为长子点只有孩子亦需分出其名一程者试的有树 §6.2.2二叉树的性质 §6.2.2二叉树的性质 1.性质1：二叉树的第层上至多有21个结点 (伦1，根为第1层) 2性质2.深度为h的二叉树至多有2L1个结点(h21). pf:归纳法 ①归纳盖础：1,21-1，第1层上只有根，放成立. P叶深度一定时，仅当每层上结点达到最大时，该 ②归纳假设：设所有的j(1≤jK)命题成立.即：树结点最多。第j层结点数≤2H 利用性质1知，深度为h的二叉树至多有： ①归纳步骤：j=时，第1-1层结点数≤22（由归纳 20+21+.+2t-1=2h.1 假设) 因为，每个结点至多有两个孩子. 所以，第i层上结点数≤2*21-2=2-1. 2

2014/4/7 2 §６.１树的概念  术语： 11 高（深）度：树中结点的最大层数 12 堂兄弟：双亲在同一层的结点互为堂兄弟 13 有序树、无序树：若每结点的各子树看成是从左到右有次序（不能互换） 7 的，则称为有序树，否则为无序树。不同的有序树，一般讨论有序树 14 森林：m (m>=0) 棵互不相交的树的集合树和森林非常接近：删去树根＝＞森林森林加上一根＝＞树 §６.１树的概念  逻辑特征：  父子关系（非线性关系）：任一结点至多有一直接前驱（双亲）结点，但可有多个直接后继（子女）结点．  开始结点：根 }其余结点为内部结点 8  终端结点：叶  祖先与子孙关系：是对父子关系的延拓，它定义了树中结点的纵向关系．  横向关系：有序树定义了同一组兄弟间的从左到右的长幼关系，可将其延拓到结点间的横向次序：k1和k2 是兄弟，k1在左，则k1的任一子孙在k2的任一子孙的左边． }其余结点为内部结点． §６.２二叉树是一种特殊的树型结构，每个结点至多只有二棵子树，一般树可转换为二叉树，计算机用途甚广． §６.２.１二叉树的定义 9  Ｄef: 二叉树是n(n>=0)个结点的有限集，它或者是空集，或由一个根结点及两棵互不相交的，分别称作根的左子树和右子树的二叉树组成 §６.２.1 二叉树的定义  形态 a (b) (c) (d) (e) A A A 10  与度为２的有序树区别： ( ) ( ) ( ) ( ) a b c d e 当某一结点只有一孩子时，有序树中它理所当然为长子，但二叉树中，一个结点只有一个孩子亦需分出其左右． §６.２.2 二叉树的性质 1. 性质１：二叉树的第i层上至多有2i-1个结点（i≥1，根为第1层） pf：归纳法 ① 归纳基础：i=1,2i-1=1,第1层上只有根，故成立． 11 ① 归纳基础：i 1,2 1,第1层上只有根，故成立． ② 归纳假设：设所有的j（1 ≤ j<i）命题成立．即：第j层结点数≤２j-1 ① 归纳步骤：j=i时，第i-1层结点数≤ ２i-2(由归纳假设) 因为，每个结点至多有两个孩子．所以，第i层上结点数≤ ２＊２i-2=2i-1． §６.２.2 二叉树的性质 2. 性质２．深度为h的二叉树至多有２h-1个结点（h≥1). Pf: 深度一定时，仅当每层上结点达到最大时，该 12 深度定时，仅当每层结点达到最大时，该树结点最多．利用性质1知，深度为h的二叉树至多有： 20+21+…+2h-1 = 2h-1

2014/47 S6.2.3二叉树的存储结构 s6.2.3二叉树的存储结构缺点 2. 链式存储结构。结点结构对一般的二叉树，须按完全二叉树的编号来存储，浪费空间，最坏情况是右单支树，k个结点需1 child 个结点空间。右孩子 01234567 (国二叉继表中等点 )带双亲的二义战表 M3ABC ·类型定义 typedef struct node 结论 DataType data; struct node"Ichild,"rchild; 藻桨捷钩只适用于存储完全二又树，且横入和 )BinTNode;∥结点类型 typedef BinTNode"BinTree;二叉树类型 86.2.3二叉树的存储结构 S6.3遍历二叉树在二叉树中，所有类型为BinTNode的结点，加上一个指向 1概念根的BinTree型头指针root,就构成了二叉树的链式存储结构，称 ·定义：沿某搜索路线，依次对制中每个结点均做一次且之为二叉雏衰仅做一次访问。量然，二叉链表由根指针root唯一确定，例子重要性：是其它运算的盖础，很多树上绿作均依赖于速历排作，只是访问结点所做的嫌作不同。 ·如何速历？遍历线性结构很容易：从开始结点出发，依次访问当前结点的后继，直至终端特点为止。遍历路线只有一条如单链表，从头指针开始)。 ■特性 (a)二二叉链表空制分root=NULL 但二叉树中每个结点可能有两个后纯，故遭历路线不唯一，须找到适用于每个结点的相同的遍历规则。叶子÷左右指针为空空指针数：n个结点，共有2n个指针罐，但只有n-1个结点是别人的孩子，故空指针数为+1 22 §6.3遍历二叉树 S6.3遍历二叉树 :在二叉树的递归定义中，非空树组成为： 2逾历算法 D,L、R 以中根为例，速历二叉定义为在任一结点上，可按某种次序执行三个操作：计二叉制非空hen( 访问根结点(D),遍历该结点的左子树亿)，遍历该结点的右 (遍历左子制即速历二又铜子树(R) (2)访问根 1将1(2)和(2(3)对视后为先根和后根速历显然有六种执行次 (3)遍历右子制即流历二复制】 }Ⅱ香测为空嫌作（递归结来条件 1从左到右： DLR,LDR,LRD二者对称，只讨论前3种 void Inorder(BinTree T(HT为三叉树的头指针 2.从右到左：DRL,RDL,RLD f(可{ⅡT非空，T为空时为空操作速历规则（从左到右） Inorder(T->Ichild); 归速历左子 printi(""%c”,T->data:∥访间损鳍点，具体问厘，此 DLR,LDR,LRD的差别是访问根的先后次序不同作不同 ①前序（先序，先根）遍历：DLR Inorder(T->rchild); ∥邀归德历右子例 ②中序（中根）遍历：LDR ③后序（后极）遍历：LRD 。时间：O(n

2014/4/7 4 §6.2.3 二叉树的存储结构  缺点对一般的二叉树，须按完全二叉树的编号来存储，浪费空间，最坏情况是右单支树，k个结点需2k-1 个结点空间。 19  结论这种结构只适用于存储完全二叉树，且插入和删除不便。 §6.2.3 二叉树的存储结构 2. 链式存储结构  结点结构 20  类型定义 typedef struct node { DataType data; struct node *lchild, *rchild; } BinTNode; // 结点类型 typedef BinTNode *BinTree; //二叉树类型 §6.2.3 二叉树的存储结构在二叉树中，所有类型为BinTNode的结点，加上一个指向根的BinTree型头指针root，就构成了二叉树的链式存储结构，称之为二叉链表显然，二叉链表由根指针root唯一确定。  例子 21  特性空树  root = NULL 叶子  左右指针为空空指针数：n个结点，共有2n个指针域，但只有n-1个结点是别人的孩子，故空指针数为n+1 §6.3 遍历二叉树 1. 概念  定义：沿某搜索路线，依次对树中每个结点均做一次且仅做一次访问。  重要性：是其它运算的基础，很多树上操作均依赖于遍历操作，只是访问结点所做的操作不同。  如何遍历？ 22 遍历线性结构很容易：从开始结点出发，依次访问当前结点的后继，直至终端结点为止。遍历路线只有一条 (如单链表，从头指针开始)。但二叉树中每个结点可能有两个后继，故遍历路线不唯一，须找到适用于每个结点的相同的遍历规则。 §6.3 遍历二叉树 ∵ 在二叉树的递归定义中，非空树组成为： D、L、R ∴ 在任一结点上，可按某种次序执行三个操作：访问根结点(D)，遍历该结点的左子树(L),遍历该结点的右子树(R) 显然有六种执行次序： lim ( )/ lim(2 3 2 1)/ 2 3 3 2 3 = + + + = →∞ →∞ T n n n n n n n n lim ( )/ lim(2 3 2 1)/ 2 3 3 2 3 = + + + = →∞ →∞ T n n n n n n n n   23 遍历规则(从左到右) DLR,LDR,LRD的差别是访问根的先后次序不同 ① 前序(先序，先根)遍历：DLR ② 中序(中根)遍历：LDR ③ 后序(后根)遍历：LRD 1 DLR LDR LRD 3 DRL RDL RLD       .从左到右：，，二者对称，只讨论前种 2.从右到左：，， §6.3 遍历二叉树 2. 遍历算法以中根为例，遍历二叉树定义为： if 二叉树非空 then { (1) 遍历左子树 // 即遍历二叉树 (2) 访问根 // 将(1)(2)和(2)(3)对调后为先根和后根遍历 (3) 遍历右子树 //即遍历二叉树 } // 否则为空操作 (递归结束条件) 24 void Inorder(BinTree T) { // T为二叉树的头指针 if (T) { // T非空，T为空时为空操作 Inorder(T->lchild); // 递归遍历左子树 printf(“%c”, T->data)；// 访问根结点，具体问题，此 // 操作不同 Inorder(T->rchild); // 递归遍历右子树 } }  时间：O(n)

201447 §6.3遍历二叉树 s6.3遍历二叉树 3. 遍历序列 4. 通用的遍历算法包络线是递归遍历路线因为访问钠点的操作依输于具体问厘，故可将它作为一个函敷指针边向下：表示递归调用，更数放于速历算法的◆敷表中，调用时，使其指向具体的访问结点的应用西深一层向上：表示递归结束，返 void Inorder(BinTree T,void ("Visit)(DataType x)){ 回一层前序序列：ABDCEF 每个结点经过3次， Inorder(T->lchild,Visit); 中序序列：DBAECF线性序列 (Visit)(T->data); 第1次经过时访问所得结后序序列：DBEFCA Inorder(T>rchild,Visit); 点序列为前序，第2次经 1个开始结点，1个锋端结点，其余结点均过时访问所得结点序列为有一个童接前驱和一个直接后蛙，为区别中序，第3次经过时访问 3种次序在前窗冠以前序其中Vst是一西数指针，它指向形物void f(DataTyp9x)的函数，故中序所得结点序列为后序。后序【后维可将访问销点的操作写在函仲，通过调用语句： Inorder(root,f); ▲叶子的相对次序相同将的地址传给Vst。 §63遍历二叉树 S6.3遍历二叉树 4通用的遍历算法 5. 建立二叉链表上述算法假定二叉链表已建立例如，可将打印操作为建立二叉树对应的二叉链表方法很多 void print(DataType x){ 先序遍历构造法输入先序序列，加入应结点物入时用空格符“”) print(%c”,x: 以示空指针的位置，例如前述的二叉制，输入为： ABD中中ΦCEΦ中FΦ中调用引Inorder(root,print),即可完成前述算法。 ▲函数名：函数代码的起址。 s6.3遍历二叉树 S6.4线索二叉树 void CreateBinTree(BinTree*T(∥注意T为指针的指针 1. 基本概念 char ch; if(eh=getchar0(=n)return;∥回车结桌输入在一基本数据结构上常常常要扩充，增加辅助信息，其目的是： f(ch=')∥读入空格 ①开发新操作：②加速已有操作。 T=NULL:I将相应的指针置空锐家一利用空指针(+1个存放指肉点在某种速历次序下的 ese{∥峡入的是结点数播前厘和后维指针 *T=(BinTNode*)malloc(sizeof(BinTNode)); 线索链表—加上绒寒的二叉链表 (T->data=ch;∥生成新结点，相当于访向根节点处常二叉树一一相应的二又制称为线家二又制 CreateBinTree(&(T>Ichild;I速历左子侧目的：加速速历操作 CreateBinTree(&(rT->rchild):l施历右子制加速查找任一结点在某种速历次序下的前驱和后镶操作。如何区别结点的指针城孩子常针：指向孩子？建制时调用CreateBinTree(&root),将root(BinTree类型)的镜索指针：指向其莱种速历次序下的前里和后蛙的战索？地址复制给T,故修改T就相当于修改了实◆root本身。时间：O(n 30

2014/4/7 5 §6.3 遍历二叉树前序序列：AB CD EF 3. 遍历序列包络线是递归遍历路线向下：表示递归调用，更深一层向上：表示递归结束，返回一层 25 D EF BA C D EF B CA      前序序列：中序序列: 线性序列：后序序列: 每个结点经过3次，第1次经过时访问所得结点序列为前序，第2次经过时访问所得结点序列为中序，第3次经过时访问所得结点序列为后序。 1个开始结点，1个终端结点，其余结点均有一个直接前驱和一个直接后继，为区别 3种次序在前面冠以         前序前驱中序 + 后继后序 ▲ 叶子的相对次序相同 §6.3 遍历二叉树 4. 通用的遍历算法因为访问结点的操作依赖于具体问题，故可将它作为一个函数指针参数放于遍历算法的参数表中，调用时，使其指向具体的访问结点的应用函数 void Inorder( BinTree T, void (*Visit)(DataType x) ) { if (T) { Inorder(T->lchild Visit); 26 >lchild, Visit); (*Visit)(T->data); Inorder(T->rchild, Visit); } } 其中Visit是一函数指针，它指向形如void f(DataType x)的函数，故可将访问结点的操作写在函数f中，通过调用语句： Inorder(root, f); 将f的地址传给Visit。 §6.3 遍历二叉树 4. 通用的遍历算法例如，可将打印操作为 void print(DataType x) { print(“%c”, x); } 27 调用Inorder(root, print)，即可完成前述算法。 ▲ 函数名：函数代码的起址。 §6.3 遍历二叉树 5. 建立二叉链表上述算法假定二叉链表已建立建立二叉树对应的二叉链表方法很多  先序遍历构造法输入先序序列，加入虚结点(输入时用空格符“ ”) 以示空指针的位置，例如前述的二叉树，输入为： ABDФФФCEФФFФФ 28 ABDФФФCEФФFФФ §6.3 遍历二叉树 void CreateBinTree(BinTree *T) { // 注意T为指针的指针 char ch; if ((ch = getchar()) == ‘\n’) return; // 回车结束输入 if (ch == ‘ ’) // 读入空格 *T = NULL； // 将相应的指针置空 else { // 读入的是结点数据 *T = (BinTNode*) malloc(sizeof(BinTNode)); 29 ( ) ( ( )); (*T)->data = ch; // 生成新结点，相当于访问根节点 CreateBinTree(&(*T)->lchild); // 遍历左子树 CreateBinTree(&(*T)->rchild); // 遍历右子树 } } 建树时调用 CreateBinTree(&root), 将root(BinTree类型)的地址复制给T，故修改*T就相当于修改了实参root本身。时间：O(n) §6.4 线索二叉树 1. 基本概念在一基本数据结构上常常需要扩充，增加辅助信息，其目的是： ①开发新操作；②加速已有操作。  线索 —— 利用空指针域(n+1个)存放指向结点在某种遍历次序下的前驱和后继指针  线索链表 —— 加上线索的二叉链表 30  线索二叉树 —— 相应的二叉树称为线索二叉树  目的：加速遍历操作加速查找任一结点在某种遍历次序下的前驱和后继操作  如何区别结点的指针域孩子指针：指向孩子？线索指针：指向其某种遍历次序下的前驱和后继的线索？

20147 S6.4线索二叉树 §6.4线索二叉树 1. 基本概念 ·结点结构基本概念 lchd lue dats rtag rehild ◆中序线索树中必有两个指针域为空。线索标志左标志ag o:lchild为左指针，指向孩子中序序列开始结点，左线索为NUL】中序为对称序 :Ichild为左线索，指向前墅终端结点，右线煮为NULL (0:rchild为右指针，指向孩子开始结点为最左下的结点] 右标志rtag 中序序列终端结点为最右下的结点 :hd为右线索，指向后继。中序线索树和中序线索链表中序序列：CBDAFHGIE 前序线索树中，有几个指针域为空☒ 前序序列的开始结点为根，故当它的左子树非空时，其指针域指向左指子树，此时前序序列开始结点左指针非空，风" SULL 但是，前序序列的终端结点的右指针必为空。仅当只有1个根结点或根的左子树为空时有两个空指针， (m中序线索二又树 (6)中序线客 §6.4线索二叉树 86.4线索二叉树 1. 基本概念码学霸对时著鹅茅整锦春帮针老为牌。仅当只有1个根时成根 ◆线索树中，如何判定结点是否为叶子？ lag=tag=1(适用于三种线索树) 有时线索树只有左线索或右线索之一 2 线索化将二叉树变为线索树的过程按某种次序遍历，在遍历过程中用线索取代空指针与前序线索树对称 typedef enum (Link,Thread)PointerTag;∥o为Link,1为Thread 带头结点的线索链表 typedef struct node{ 树上6.11图心以.令空指针也指向此消兵 DataType data; PointerTag Itag,rtag; struct node 'Ichild,'rchild: }BinThrNode,'BinThrTree; 设p和pre分别指向遍历过程中当前访问崎点和其前重，即pre和p是 [折向泽漏瑞点〔一餐) 前宽和后的关系，其中p为全局，在速历过程中立缺：以中序为例，pre初始为NULL,因为中序前驱对开翰结点是NULL· s6.4线索二叉树 86.4线索二叉树 void InorderThreading(BinThrTree p){ 3 操作加速 pre为全局量，初德为NULL (找某结点p中序线察树中)中序前驱和后继结点计(p)( InorderThreading(p->Ichild)片左子树棱索化 ①找p的中序后继 ,p->ltag=(p->lchild)?Link:Thread;I左物针非空，量为 i)若p的右子树空，则p->rchild为右线察，直接指向'p的中序后键 ∥Link,否为效康。 i)若p的右子树排空(rtag为0)，则p的中序后蛙必是其右子制中第 p>rtag =(p->rchild)?Link:Thread; 个中序塘历到的销点，其特征是：简t(pre(∥着pe春在从的右孩子开，养在装下，真至找测一个没有左孩许(pre->rtag=Thread)∥当前结点p的前里右标志为能拿子的结点为止，不坊膏其为右子制中“量左下”的结点： pre>rchild=p; ∥令pe的右镜擦指向中序后接p 计(p>tag=Thread)/当前维点的左镜擦已建立 p>lchild =pre; 冷当前书点的左指向中序前这里k多1，R不一定是叶子，其右子树可 pre=p;使pre为p的前，量环不变量为空。可非空。 InorderThreading(p->rchild);右于制线察化 ·算法 ,请自己给出找钟定结点*即的中序后银算法。时间O),快于无械索的二又树。。时间：和速历相同0(. 后序前序线家化类做于此， 6

2014/4/7 6 §6.4 线索二叉树 1. 基本概念  结点结构  线索标志 0 : lchild ltag = 1: lchild 0 : rchild rtag = 1: rchild       为左指针，指向孩子左标志为左线索，指向前驱为右指针，指向孩子右标志为右线索，指向后继 31  中序线索树和中序线索链表中序序列：CBDAFHGIE §6.4 线索二叉树 NULL NULL           开始结点，左线索为中序序列中序为对称序终端结点，右线索为 1. 基本概念  中序线索树中必有两个指针域为空  前序线索树中有几个指针域为空？       开始结点为最左下的结点中序序列终端结点为最右下的结点 32  前序线索树中，有几个指针域为空？前序序列的开始结点为根，故当它的左子树非空时，其指针域指向左指子树，此时前序序列开始结点左指针非空。但是，前序序列的终端结点的右指针必为空。仅当只有1个根结点或根的左子树为空时有两个空指针。 §6.4 线索二叉树 1. 基本概念  后序线索树中，开始结点的左指针必为空，仅当只有1个根时或根的右子树为空时有两个空指针。 33 与前序线索树对称  带头结点的线索链表树上6.11图(b). 令空指针也指向此哨兵    指向终端结点(一般) 线索指向开始结点(更好，有利于遍历操作) §6.4 线索二叉树 1. 基本概念  线索树中，如何判定结点是否为叶子？ ltag = rtag = 1 (适用于三种线索树)  有时线索树只有左线索或右线索之一 2. 线索化将二叉树变为线索树的过程按某种次序遍历，在遍历过程中用线索取代空指针。 34 typedef enum {Link, Thread} PointerTag; // 0为Link，1为Thread typedef struct node { DataType data; PointerTag ltag, rtag; struct node *lchild, *rchild; } BinThrNode, *BinThrTree; 设p和pre分别指向遍历过程中当前访问结点和其前驱，即*pre和*p是前驱和后继的关系，其中pre为全局量，在遍历过程中建立线索。以中序为例，pre初始为NULL，因为中序前驱对开始结点是NULL。 §6.4 线索二叉树 void InorderThreading(BinThrTree p) { // pre为全局量，初值为NULL if (p) { InorderThreading(p->lchild); // 左子树线索化 p->ltag = (p->lchild) ? Link : Thread; // 左指针非空，置为 // Link，否则为线索。 p->rtag = (p->rchild) ? Link : Thread; if (pre) { // 若*pre存在前结点的前右标志为线索     访问 35 if (pre->rtag == Thread) // 当前结点*p的前驱右标志为线索 pre->rchild = p; // 令*pre的右线索指向中序后继*p if (p->ltag == Thread) // 当前结点的左线索已建立 p->lchild = pre; //令当前节点的左线索指向中序前驱 } pre = p; //使*pre为*p的前驱，循环不变量 InorderThreading(p->rchild); // 右子树线索化 } }  时间：和遍历相同O(n). 后序(前序)线索化类似于此。       问根结点 §6.4 线索二叉树 3. 操作(加速) (1) 找某结点*p(中序线索树中)中序前驱和后继结点 ① 找*p的中序后继 i）若*p的右子树空，则p->rchild为右线索，直接指向*p的中序后继 ii）若*p的右子树非空(rtag为0)，则*p的中序后继必是其右子树中第一个中序遍历到的结点，其特征是：从*p的右孩子开始，沿其左链往下找，直至找到一个没有左孩子的结点为止不妨称其为右子树中“最左下”的结点 p 36 子的结点为止，不妨称其为右子树中“最左下”的结点。这里k≥ 1, Rk不一定是叶子，其右子树可为空，可非空。  算法请自己给出找给定结点*p的中序后继算法。时间O(h)，快于无线索的二叉树。 p

201447 §6.4线索二叉树 S6.4线索二叉树。加速作用 (②)找的后序前驱和后序后继《在后序线索树中] 在着通二叉树中，找中序后罐；中找p的后序前驱高对于)同样有效 i)若p的ag=1(左子时为空)，则后序前驱为p->child 对于)就必须从操开始油历。 )若p的归g=0(左子树排空)，则后序前坚为p的左孩子或右孩子有线宗是直禁从线宗找到01。但线宗一般"向上”指向其祖先 :根是在遍历左右子树1L和R之后被访问而二又中无向上的链，只能从开始道历侧到，环情况0。 .p的前驱必是L和R中量后一个遍历到的结点计(p的右孩子春空)then 雪找p的中序前里 return p->rchild;∥后序前驱为p的右孩子 :中序是对称序，其方法与(1)亮全对称 else )若p的tag=1,则中序前驱为lchild return p->Ichild::后序前为p的左孩子少找P的后序后罐建见右图) i)若*p的tag=0,则中序前驱是p的左若p为根，无后幢，返回NULL 子树中“量右下”的结点。 )若p是其双亲右子，则p的后序后她是夏摩的左子树 )若p是其双亲左子，但p无右兄弟，则p的后序后缝亦为双亲 S6.4线家二叉树 S6.4线索二叉树西找p的后序后接综 (4)遍历线京二叉 w)若p是其双亲左子，但p有右兄弟，则p的历某次序的线家二叉树，只要从该次序下的开始结点后序后键是其右兄第子制中1s后序速历到的结点，出发，反复找其后继直至终端结点为止。它是该子制中“章左下的叶特点中销论：找后序前驱司开始坤点（量左下轴点，找当前销点中序后链，真至线填的点 (p->rchild=NULL山)头结点的右指针指向开始点较方找后序后提瑰，因为的序只有p的右子制为空(tag=1)时，p->rchild是线家，可直旅线到：找开始结点（根，找当前销点的前序后罐，直至终端结点 (p->rchild=NULL)头结点的右指针指向，端结点较方便百测，一般须涉及p的限亲，故仅给出p时，须从操速历，找终州结点（根），找当前销点的后序前驱，直至开始结点 (3)找p的前序前呢和前序后维 (p>ehid=NULL,物到的是后序序列的逆序列类似于后序的情况分析头纳点的右指针指向开始地点较方便讨论：找前序前驱难（涉及双亲）时间：仍为0()，但因为非道归，略快于港归的方法对速历面言找前序后罐易前序线拿制中，只需保留右姓素制即可中序效家制中，保留左、右线康之一均可后序线索树中，只需保留左战意即可 86.5树和森林 S6.5树和森林 1. 树、森林与二叉树的转换 1.树、森林与二叉树的转换 ①树>二叉制 ②森林=>二叉树树中每个结点有多个孩子之二叉树只有两个孩子 ·将各树转换为二叉树（根无右兄弟，所以无右子）长子及右邻兄弟>二叉树的左右孩子 ·将各根作为兄弟互连节点X的长子是其左子，X的右兄弟是其右子。每个结点仅保留与长子的连线。所有兄弟结点间连线。6g56000o 98999 g9999 Q (41 7

2014/4/7 7 §6.4 线索二叉树 ② 找* 的中序前驱  加速作用在普通二叉树中，找*p中序后继：对于ii）同样有效对于 i）就必须从根开始遍历。 ∵有线索是直接从线索找到O(1)。但线索一般“向上”指向其祖先，而二叉树中无向上的链接，只能从根开始遍历得到，最坏情况O(n)。 37 ② 找*p的中序前驱 ∵ 中序是对称序，其方法与(1)完全对称 i）若*p的ltag = 1，则中序前驱为lchild ii）若*p的ltag = 0，则中序前驱是*p的左子树中 “最右下”的结点。 §6.4 线索二叉树 (2) 找*p的后序前驱和后序后继(在后序线索树中) ① 找*p的后序前驱(易) i）若*p的ltag = 1(左子树为空)，则后序前驱为p->lchild ii）若*p的ltag = 0(左子树非空)，则后序前驱为p的左孩子或右孩子 ∵根是在遍历左右子树L和R之后被访问 ∴*p的前驱必是L和R中最后一个遍历到的结点 if (p的右孩子非空) then return p->rchild; // 后序前驱为p的右孩子 38 return p->rchild; // 后序前驱为p的右孩子 else return p->lchild; //后序前驱为p的左孩子 ② 找*p的后序后继(难)(见右图) i）若*p为根，无后继，返回NULL ii）若*p是其双亲右子，则*p的后序后继是双亲 iii）若*p是其双亲左子，但*p无右兄弟，则*p的后序后继亦为双亲 §6.4 线索二叉树 ② 找*p的后序后继(续) iv）若*p是其双亲左子，但*p有右兄弟，则*p的后序后继是其右兄弟子树中1st后序遍历到的结点，它是该子树中“最左下的叶结点” 结论：找后序前驱易找后序后继难，因为：只有*p的右子树为空(rtag = 1)时，p->rchild是线索，可直接找到； 39 否则，一般须涉及*p的双亲，故仅给出*p时，须从根遍历。 (3) 找*p的前序前驱和前序后继类似于后序的情况分析讨论：找前序前驱难(涉及双亲) 找前序后继易 §6.4 线索二叉树 (4) 遍历线索二叉树遍历某次序的线索二叉树，只要从该次序下的开始结点出发，反复找其后继直至终端结点为止。  中序找开始结点(最左下结点)，找当前结点中序后继，直至终端结点 (p->rchild = NULL) 头结点的右指针指向开始结点较方便  前序找开始结点(根)，找当前结点的前序后继，直至终端结点 (p >rchild = NULL) 头结点的右指针指向终端结点较方便 40 ->rchild = NULL) 头结点的右指针指向终端结点较方便  后序找终端结点(根)，找当前结点的后序前驱，直至开始结点 (p->lchild = NULL)，得到的是后序序列的逆序列头结点的右指针指向开始结点较方便  时间：仍为O(n)，但因为非递归，略快于递归的方法  对遍历而言前序线索树中，只需保留右线索树即可中序线索树中，保留左、右线索之一均可后序线索树中，只需保留左线索即可 §6.5 树和森林 1. 树、森林与二叉树的转换 ① 树 => 二叉树树中每个结点有多个孩子 => 二叉树只有两个孩子长子及右邻兄弟 => 二叉树的左右孩子节点X的长子是其左子，X的右兄弟是其右子  每个结点仅保留与长子的连线  所有兄弟结点间连线 41 §6.5 树和森林 1. 树、森林与二叉树的转换 ② 森林 => 二叉树  将各树转换为二叉树(根无右兄弟，所以无右子)  将各根作为兄弟互连 42

20147 §6.5树和森林 §6.5树和森林 1. 树、森林与二叉树的转换 2. 树的存储结构 ③二叉树=>树或森林 ①双亲链表表示法设x是y的左孩子，则将x的右孩子，右孩子的右孩子。每结点双亲唯一故存储结点时，增加一个都与y相连 parent城指向双亲，用向量表示较方便使去掉所有双亲到右孩子的连线 0 123456 7890 d A B C D E F G H 1J Fi6. met-1000112333 特点：向上链接，根的parent为-1 求指定结点双亲(O(1)及祖先(O(h)方便求指定结点孩子及后代须遍历数组O( 类型说明略) §6.5树和森林 §6.5树和森林 2树的存储结构 2树的存储结构少孩子链表表示法孩子链表表示法（续）若k叉树用k叉链表表示，会导致浪费空间特点：易实现找结点的孩子及子州向下查找易】 :树边n-1条难实现找结点的双亲及祖先（向上查找难）空指针kn-n-1)=n(k-1)+1 双亲孩子链衰囊示法设度数域，结点不等长、运算不便在孩子链表中，增加parent位域热新表膏被鑫警轩佳表。持结点及相应玻子此方法结合了双亲链表和孩子链表的优点，向上向下查找均方仅 rot0厚置四类型说明：略 ③孩子兄弟链表表示法品吧四制=之二叉树时，结点关系由：量左孩子、右邻兄弟表 SF A Leftmootchid data rightsibling 相当干二又链表 §65树和森林 s6.6 Huffman?树及其应用 3. 树和森林的遍历 86.6.1最优二叉树 ①先序速历树 1. 概念先访问树的根；然后依次先序速历根的每棵子树结点路径长度：根到该结点所经过的边数后序速历制先依次后序遍历根的每棵子树：然后访问树的根：树的路径长度：所有结点的路径长度之和雪先序撞历森林 (结点数相同时，完全二叉树的路径长度最短) 先访问森林中第一棵树的根；然后先序遍历第一操树中 ●结点的带权路径长度：点的各子成的森林：最后先序遍历除第一棵外其它树构成的森林结点的权值W,X结点的路径长度 ④后序速历森林 ●树的带权路径长度（实际上是加权外部路径长度后序速历森林中第一操树的根结点的各子树所抱成的森所有叶子的加权路径长度之和林，然后访问第一操制的根：景后后序遍历除幕一棵外其它树构成的林 P一∑以形：第个叶子的权（实数 1:第í个叶子的路径长度

2014/4/7 8 §6.5 树和森林 1. 树、森林与二叉树的转换 ③ 二叉树 => 树或森林 • 设x是y的左孩子，则将x的右孩子，右孩子的右孩子，都与y相连 • 去掉所有双亲到右孩子的连线 43 §6.5 树和森林 2. 树的存储结构 ① 双亲链表表示法 ∵每结点双亲唯一，故存储结点时，增加一个 parent域指向双亲，用向量表示较方便 44 • 特点：向上链接，根的parent为-1 求指定结点双亲(O(1))及祖先(O(h))方便求指定结点孩子及后代须遍历数组O(n) • 类型说明(略) §6.5 树和森林 2. 树的存储结构 ② 孩子链表表示法 • 若k叉树用k叉链表表示，会导致浪费空间 ∵ 树边n-1条 ∴ 空指针kn-(n-1)=n(k-1)+1 • 设度数域，结点不等长、运算不便 45 • 孩子链表：每结点设一孩子链表，将结点及相应孩子链表的头指针放在一向量中。 §6.5 树和森林 2. 树的存储结构 ② 孩子链表表示法（续） • 特点：易实现找结点的孩子及子孙(向下查找易) 难实现找结点的双亲及祖先(向上查找难) • 双亲孩子链表表示法在孩子链表中，增加parent域 46 此方法结合了双亲链表和孩子链表的优点，向上向下查找均方便 • 类型说明：略 ③ 孩子兄弟链表表示法树 => 二叉树时，结点关系由：最左孩子、右邻兄弟表示 §6.5 树和森林 3. 树和森林的遍历 ① 先序遍历树先访问树的根；然后依次先序遍历根的每棵子树 ② 后序遍历树先依次后序遍历根的每棵子树；然后访问树的根； ③ 先序遍历森林先访问森林中第棵树的根然后先序遍历第棵树中 47 先访问森林中第一棵树的根；然后先序遍历第一棵树中根结点的各子树所构成的森林；最后先序遍历除第一棵外其它树构成的森林 ④ 后序遍历森林后序遍历森林中第一棵树的根结点的各子树所构成的森林；然后访问第一棵树的根；最后后序遍历除第一棵外其它树构成的森林先序遍历恰好等价于先序遍历对应的二叉树，后序遍历恰好等价于中序遍历对应的二叉树。 §6.6 Huffman树及其应用 §6.6.1 最优二叉树 1. 概念  结点路径长度：根到该结点所经过的边数  树的路径长度：所有结点的路径长度之和 (结点数相同时，完全二叉树的路径长度最短)  结点的带权路径长度 48 ：结点的权值Wi × 结点的路径长度li  树的带权路径长度(实际上是加权外部路径长度) 所有叶子的加权路径长度之和 1 : i : i n ii i i i WPL wl w l = =  第个叶子的权(实数) 第个叶子的路径长度

2014/47 §6.6 Huffman树及其应用 s6.6 Huffman树及其应用 s6.6.1最优二叉树 s6.6.1最优二叉树。最忧二叉树(Huffman树) 2。构造最优二叉树在权为ww2 ,w的叶子所构成的所有的二叉树显然，权越大应离根越近，Huffman首先提出了构造方法： WPL意小的称为二叉树例n=4,a:7,b:5,c:2,d:41 ”魏整权”笑中兴淡除为叶子结点，其权为w: 2)食并：在F中选两操根的权囊小的三叉树（考不止两，则任选作为左、有右孩子，将其合并为一棵新制，新根权值为这两个结点的权值之和： e:合并后F中少了1棵树若叶子权值相同，完全二叉树一定是量优二叉树，否则不 3)对新森林F重复2，直至只利下一棵树为止。 s6.6 Huffman树及其应用 s6.6 Huffman树及其应用 s6.6.1最优二叉树 86.6.1最优二叉树 2构造最优二叉树 2构造最优二叉树 ·算法特点 ·存储结构 ①初始有n棵树，每树仅有一个立结点 #define n 100 叶子合并：每合并一次，少一操制，故只需合并-1次每合并一次产生结点，且新点度为2，故最终的 define m2n-1∥结点总量 Huffman制有2n-1个结点： typedef struct{ float weight; 1权，不妨设20 2”-个结点/个肝子 int Ichild,rchild,parent;/ 一1个度为2的结点}无1度结点严格的2又树】 }HTNode; 实际上任何严格二叉树中，叶子数为时，总结点数为 typedef HTNode HuffmanTree[m]; 2n-1. parent罐作用：找双亲结点为1时衰示根，区分根与非根 ·构造算法 s6.6 Huffman树及其应用 §6.6.2 Huffman编码 void CreateHuffmanTree(Huffman Tree T)(∥构道量优树，根为Tm-) int i,p1,p2; 绿念 InitHuffmanTree(T:∥初输化将2n-1个结点的3个指针夏空-1，权里为0 ● 数据压缩 InputWeight(T); ∥轴入n个叶子根)的权存于T0.n-们中，初可将数据文件压缩20%~90%，压缩效率取决于文件特征始化意林杆0中的根权编解码 fori=四：i<m:+K山对中的树合并-1次，新根依次放入T可中，囊钱编鸭压缩，根为可m-1】文科中的字将字符集中字狗一程四架西二进制位用 SelectMin(Ti-1,&p1,8p2外；∥在当前凛琳T0灯的所有结点中，选权量小和次小的两个根维点Tp1]和Tp习作为合并时像，0sp1P2-1 Tp】parent=Tp以.parent=i:∥合并产生的新根为T) 编码方案（对字符集编码） T[i].lchild p1; 例C={a,b,c,d,e,,设数据文件有10万字符，1C=6 T[i].rchild p2; e 填码总长 T[i].weight=T[p1]-weight+T[p2].weight 频度万4.51.31.21.00.90.5 定长00000101001110010130万变长01011001111101110022.4万算法中用到的三个函数略，实例（教材）节约25%空间 9

2014/4/7 9 §6.6 Huffman树及其应用 §6.6.1 最优二叉树  最优二叉树（Huffman树）在权为w1,w2,…,wn的叶子所构成的所有的二叉树， WPL最小的二叉树称为最优二叉树例 n=4，{a:7, b:5, c:2, d:4} 49  若叶子权值相同，完全二叉树一定是最优二叉树，否则不一定 §6.6 Huffman树及其应用 §6.6.1 最优二叉树 2. 构造最优二叉树显然，权越大应离根越近，Huffman首先提出了构造方法： 1）初始森林：根据给定的n个权{w1,w2,…,wn}构成一个包含 n棵二叉树的森林F={T1,T2,…,Tn}. 其中Ti 只有一个根(亦为叶子)结点，其权为wi ; 2）合并：在F中选两棵根的权最小的二叉树(若不止两棵，则任选)作为左右孩子将其合并为棵新树新根权值 50 任选)作为左、右孩子，将其合并为一棵新树，新根权值为这两个结点的权值之和； 3）对新森林F重复2)，直至只剩下一棵树为止。 §6.6 Huffman树及其应用 §6.6.1 最优二叉树 2. 构造最优二叉树  算法特点 ① 初始有n棵树，每棵树仅有一个孤立结点 ② 合并：每合并一次，少一棵树，故只需合并n-1次每合并一次产生1新结点，且新结点度为2，故最终的 Huffman树有2n-1个结点： 51 实际上任何严格二叉树中，叶子数为n时，总结点数为 2n-1。 21 ( ) n   −     n 1 2 n1 2 个叶子个结点无度结点严格的叉树 - 个度为的结点 §6.6 Huffman树及其应用 §6.6.1 最优二叉树 2. 构造最优二叉树  存储结构 #define n 100 // 叶子数 #define m 2*n-1 // 结点总数 typedef struct { float weight; // 权不妨设≥0 52 float weight; // 权，不妨设≥0 int lchild, rchild, parent; // 指针 } HTNode; typedef HTNode HuffmanTree[m]; parent域作用：找双亲结点为-1时表示根，区分根与非根  构造算法 §6.6 Huffman树及其应用 void CreateHuffmanTree (HuffmanTree T) { // 构造最优树，根为T[m-1] int i, p1, p2; InitHuffmanTree(T); // 初始化, 将2n-1个结点的3个指针置空(-1),权置为0 InputWeight(T); // 输入n个叶子(根)的权存于T[0..n-1]中，初 //始化森林F0中的根权 for (i = n; i < m; i++){ // 对F中的树合并n-1次，新根依次放入T[i]中，最终 //根为T[m-1] SelectMin(T i-1 &p1 &p2); // 在当前森林T[0 i-1]的所有结点中选权 53 SelectMin(T, i-1, &p1, &p2); // 在当前森林T[0..i-1]的所有结点中，选权 //最小和次小的两个根结点T[p1]和T[p2]作为合并对象，0≤p1,p2≤i-1 T[p1].parent = T[p2].parent = i; // 合并产生的新根为T[i] T[i].lchild = p1; T[i].rchild = p2; T[i].weight = T[p1].weight + T[p2].weight } } 算法中用到的三个函数略，实例（教材） §6.6.2 Huffman编码 1. 概念  数据压缩可将数据文件压缩20%～90%,压缩效率取决于文件特征  编解码 54  编码方案(对字符集编码) 例 C = {a, b, c, d, e, f}, 设数据文件有10万字符，|C|=6 节约25%空间 a bcde f 编码总长频度(万) 4.5 1.3 1.2 1.0 0.9 0.5 定长 000 001 010 011 100 101 30万变长 0 101 100 111 1101 1100 22.4万

20147 §6.6.2 Huffman编码 §6.6.2 Huffman编码 ◆定长编两：网长g 公静态墙网 ◆变长增调：问题是解码可能有二义性无需海次压结前均统计C的频度，而是对定义在相同字符靠如：设E,T,W编码为00,01,0001 上的大量文件进行计，测出每个字符C,出现的率，此两，则平均网长为：解码时对0001串有两种方式：E工，W 问题的原因一E的墙码是W的填码的前氯 Σ了一平均码长最短的前氯码为最优前领码前源增钢：是求字符集中，任一字符的纳码肯不是其他字符填网的前氯。显然，定长纳网是前量墙网 2鲜克学轻008…086平构奶长为量优的前细网（付uffman编码）：压镇效果量佳的前氯网特点所有文件使用同一纳码，省时 ①功态格调编码算法对不同的文件，效果不尽相同对错定文件，先统计字符集C=C1,c2,c】中各字符出现 2. 的频率，据此设计墙码，设c的网长为，则墙吗文件总长度： ·算法思想之—使文件编码总长最短的前领码是最优前银网件物态智表示的不同文件，塘码方素不同，即文利用Huffman制求量优前氯码 step1:用字符c作为叶子，p,(或切徽c的权，构造uffman制特点：费时，效果最佳 s19p2将制的左右分支分别标记0和1，将根到那叶子的路径上的振号依次相连，作为该叶子字符的编网。 s6.6.2 Huffman编码 s6.6.2 Huffman编码 ·例子 ·上述编码是量优的前领吗？ 678910 T45n13c512bm16eu09,05,a142503,5510 电量优 :叶子的码长=叶子的路径长度 ,∑P以疑是平均网长，又是=叉树的WPL 55 下标ch bits 即Huffman制是WPL量最小的二又树=>平均网长量小 ②前绿码 72 :制中在一叶子不可能是其它叶子的祖先 1D0 每叶子纳码不可能是其它叶子纳码的前爆 2=0.110国16 3I风 3 111 0 3算法实现（对字符集编码，即叶子集编码） 5 50 typedef struct 100 710 char ch; ∥放字符 ()哈夫曼编码树 ()哈夫曼编码表 char bits[n+们：∥放位率0结桌，码长不会超过n }CodeNode; ∥存放Huffman纳码的结点按算法建立的Huffman树幢 typedef CodeNode HuffmanCode[n]: S6.62 Huffman编码 s6.6.2 Huffman编码 void HuffmanCoding (HuffmanTree T,HuffmanCode H){ ∥根据哈夫曼树求哈夫曼绮网瘦H 4应用（数据文件的压缩与解压） int c,p,i; ∥c和p分别指示树打中孩子和父亲的位量 ①压缩徽据文件对文件编冯 char cd[n+小：B编时存放编码 for(依次从H中读入字将c)( int start; ∥指示编网在cd中的起始位量在Huffman网表H中，找H0.ch=c cdn=n0:B从后往前放编周将c转换为H门.bits写入压输文件2中： fort=0:i=0){∥到授为止 for(依次读入f2中的位率(1直至文件结来许(Tp].lchild=c)cd-star=0':∥暂Tc是p)的左于刺生成代码0 从Huffman树根Tm-]出发 else cd[-start]='1'; ∥否测生成代码1 若当前读入0，走向左孩子，否别走向右孩子： c=p; ∥链蝶上别若到达叶子T四，便泽出字符H门.ch写入还原文件中，然后量新从根出发译码 strcpy(H0.bits,&cd[start]∥复制编爵位率 }∥endfor Note:实际压缩与解压时，编网的01位率，不是字符串，即写入 ∥时间：on.h 压文件中的是“位” 10

2014/4/7 10 §6.6.2 Huffman编码   lg C    定长编码：码长  变长编码：问题是解码可能有二义性例如：设E,T,W编码为00, 01, 0001 解码时对0001串有两种方式：ET, W 问题的原因 —— E的编码是W的编码的前缀  前缀编码：要求字符集中，任一字符的编码皆不是其他字符编码的前缀。显然，定长编码是前缀编码  最优的前缀码 (H ff 编码) 压缩效果最佳的前缀码 55  最优的前缀码 (Huffman编码)：压缩效果最佳的前缀码 ① 动态编码对给定文件，先统计字符集C = {c1,c2,…,cn} 中各字符出现的频率fi , 据此设计编码，设ci 的码长为li ，则编码文件总长度： —— 使文件编码总长最短的前缀码是最优前缀码对同一字符集表示的不同文件，编码方案不同，即根据文件特征动态编码。特点：费时，效果最佳 1 n i i i f l =  §6.6.2 Huffman编码 1 n i i i p l =  ② 静态编码无需每次压缩前均统计Ci 的频度，而是对定义在相同字符集上的大量文件进行统计，得出每个字符Ci 出现的概率pi ，据此编码，则平均码长为： —— 平均码长最短的前缀码为最优前缀码例：上例中a～f 出现的概率为：0.45, 0.13, …, 0.05, 平均码长为 2.24，优于定长编码 (平均码长为3)。 56 特点 2. 编码算法  算法思想利用Huffman树求最优前缀码 step1：用字符ci 作为叶子，pi (或fi )做ci 的权，构造Huffman树 step2：将树的左右分支分别标记0和1，将根到叶子的路径上的标号依次相连，作为该叶子(字符)的编码。    所有文件使用同一编码，省时对不同的文件，效果不尽相同 §6.6.2 Huffman编码  例子 57 按算法建立的Huffman树唯一 §6.6.2 Huffman编码  上述编码是最优的前缀吗？ ② 最优 ∵ 叶子的码长 = 叶子的路径长度li ∴ 既是平均码长，又是二叉树的WPL 即 Huffman树是WPL最小的二叉树 => 平均码长最小 ② 前缀码 ∵ 树中任叶子不可能是其它叶子的祖先 1 n i i i p l =  58 ∵ 树中任一叶子不可能是其它叶子的祖先 ∴ 每叶子编码不可能是其它叶子编码的前缀 3. 算法实现 (对字符集编码，即叶子集编码) typedef struct { char ch; // 放字符 char bits[n+1]; // 放位串‘\0’结束，码长不会超过n } CodeNode; // 存放Huffman编码的结点 typedef CodeNode HuffmanCode[n]; §6.6.2 Huffman编码 void HuffmanCoding (HuffmanTree T, HuffmanCode H) { // 根据哈夫曼树T求哈夫曼编码表H int c, p, i; // c和p分别指示树T中孩子和父亲的位置 char cd[n+1]; // 临时存放编码 int start; // 指示编码在cd中的起始位置 cd[n] = ‘\0’; // 从后往前放编码 for (i = 0; i = 0) { // 到根为止 if (T[p].lchild == c) cd[--start] = ‘0’; // 若T[c]是T[p]的左子树生成代码0 else cd[--start] = ‘1’; // 否则生成代码1 c = p; // 继续上溯 } strcpy(H[i].bits, &cd[start]); // 复制编码位串 } // endfor } // 时间: O(n.h) §6.6.2 Huffman编码 4. 应用 (数据文件的压缩与解压) ① 压缩数据文件 (对文件编码) for (依次从f1中读入字符c) { 在Huffman编码表H中，找H[i].ch = c 将c转换为H[i].bits写入压缩文件f2中； // 按bits0，1串写入“位”，设f2是二进制文件 } 60 ② 加压译码 (对压缩文件解码) for (依次读入f2中的位串) { // 直至文件结束从Huffman树根T[m-1]出发若当前读入0，走向左孩子，否则走向右孩子；若到达叶子T[i]，便译出字符H[i].ch写入还原文件中，然后重新从根出发译码 } Note: 实际压缩与解压时，编码的0/1位串，不是字符串，即写入压缩文件中的是“位