2014/47 Ch.6树 数据结构 ■树形结构： ◆二叉树，树，森林等 Ch.6树 ◆结点间有分支，具有层次关系 ■特征： ·每个结点最多只有一个直接前驱，但可有多个直间后 计算机学院 继。 肖明军 。开始结点一根 ◆终端结点一叶 Email:xiaomj@ustc.edu.cn ◆其余结点一内部结点 http://staff.ustc.edu.cn/~xiaomj 应用：家谱、行政架构等，计算机系统中的文件 目录等 s6.1树的概念 S6.1树的概念 递归定义：刻画了树的固有特性：非空树由若干 ■Def:制是n(n>=O)个结点的有限集T,T为空时称为空树， 棵子树构成，子树由较小子树构成。 否测则它满足： 表示 ◆有且仅有一个特定的称为损的结点： 种解.TT 第一层 分支结点 8 子 (。树形表示法 ()数套集合表云选 (口入表表示法 (A(B(E.F(I.J)).C.D(G.HJ)) (D广义表表示法 86.1树的概念 S6.1树的概念 术语： ■术语： ①结点的度：结点拥有的子树数目（树的度） ⑧路径：道路（自上而下） ②叶子：终端结点，度为O的结点 若存在一结点序列k,k2,k,使得k是k的双亲 ③分支结点：非终端结点，度>O (1<=K=小1)，则称该序列是从k,到k的一条路径或 道路，路径长度为边数-1. ③内部结点：根之外的分支结点 ②粗先和子孙：若k到k有一路径，则k是k的粗先，k ⑤根：开始结点 是k的子孙， ⑥孩子、双亲：某结点的子树的根称为该 轴点A的祖先是从根到A的路径上所经过的所有结点 结点的孩子，该结点为孩子的双亲 结点A的于孙是以A为根的子树中的所有结点. 直接前驱（双亲）直接后继（孩子） 真祖先和真子孙不包含自身 ⑦兄弟：同一双亲的孩子互为兄弟 鲁层数从根起算（为1或0），其余结点的层数是其双 亲的层敷+1
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 §6.2.2二叉树的性质 §6.2.2二叉树的性质 3. 性质3，在任一二叉树T中，设叶子数为ng,度为 4. 满二叉树：深度为h的具有2n,1个结点的二叉 2的结点数为n2:则nn2t1 树称为满二叉树。 Pt设n,为度为1的结点总数，则结点总数n等于0度， 5完全二叉树：若一二叉树至多只有最下两层上 1度和2度结点数之和 结点的度数可小于2，且最下一层上的结点都 n=ng*n+nz∥二叉制 (6.1) 集中在该层最左边的若干位置，则称为完全二 另一方面，除根外，其余结点均是其双亲的孩子，树中： 叉树。 孩子结点总数=n1+2n2中n-1=n,+2n2 某结点无左孩子，则它必为叶子 n年n,+2n2+1 (6.2) 满二叉树是完全二叉树，但反之未必成立： 由6.1和6.2：nn2+1 86.2.2二叉树的性质 S6.2.3二叉树的存储结构 1. 顺序存储结构 6. 性质4.具有n个结点的完全二叉树高为lg小+1或 如何将结点线性化，使得在线性序列中的相互位置能 g(n+1) 反映出结点间的辑关系？ pt:树高为h,则前h-1层是高为h-1的满二叉树，结点总数 若对完全二叉制自上而下，每层自左到右给所有个结 =2h1.1. 点编号，就能到一个足以反映整个二叉树结构的线性序 .∴，2h-1.11，则k,的双亲是妇 映结点间的逻辑关系 (2)若2i≤n,则k,的左孩子为k2i:否则k,无左孩子，即它必 :.可将n个结点存储在向量 为叶子。//因此，完全二叉制中编号i》Lw对的结点必为叶子： bt[0.n可中，其中： (3)若2i+1≤n,则k,的右孩子为k2,否则k,无右孩子： bt0]一不用，或存储n (④若i为奇数且大于1，则k,的左兄弟为k,否则k无左兄 bt1n)一存储编号为1至n的结点 弟： 1 14151617 (5)若i为数且小于n,则k1的右兄弟为k,否则k,无右兄 正明从略。 3
2014/4/7 3 §６.２.2 二叉树的性质 3. 性质３．在任一二叉树Ｔ中，设叶子数为n0，度为 ２的结点数为n2．则n0=n2+1. Pf: 设n1为度为１的结点总数，则结点总数n等于０度， １度和２度结点数之和 13 n = n0+n1+n2 // 二叉树 （６.１） 另一方面，除根外，其余结点均是其双亲的孩子，树中： 孩子结点总数 = n1+2n2 n-1 = n1+2n2 n = n1+2n2+1 （６.２） 由６.１和６.２：n0=n2+1 §６.２.2 二叉树的性质 4. 满二叉树：深度为h的具有２h-1个结点的二叉 树称为满二叉树． 5. 完全二叉树：若一二叉树至多只有最下两层上 结点的度数可小于２ 且最下一层上的结点都 14 结点的度数可小于２，且最下 层上的结点都 集中在该层最左边的若干位置，则称为完全二 叉树． 某结点无左孩子，则它必为叶子 满二叉树是完全二叉树，但反之未必成立． §６.２.2 二叉树的性质 6. 性质４．具有n个结点的完全二叉树高为 或 pf: ∵树高为h，则前h-1层是高为h-1的满二叉树，结点总数 = 2h-1-1. lg 1 n + lg( 1) n + 15 ∴ 2h-1-1 1，则ki的双亲是 (2) 若2i≤n,则ki的左孩子为k2i；否则ki无左孩子，即它必 为叶子。//因此，完全二叉树中编号i> 的结点必为叶子; ( ) 若 ≤ 则 的右孩子为 否则 无右孩子 17 (3) 若2i+1≤n,则ki的右孩子为k2i+1 ,否则ki无右孩子; (4) 若i为奇数且大于1，则ki的左兄弟为ki-1，否则ki无左兄 弟; (5) 若i为偶数且小于n，则ki的右兄弟为ki+1，否则ki无右兄 弟。 证明从略。 §6.2.3 二叉树的存储结构 i / 2 ∵ 上述关系中，编号足以反 映结点间的逻辑关系 ∴ 可将n个结点存储在向量 bt[0..n]中，其中： bt[0] —— 不用 或存储n 18 bt[0] —— 不用，或存储n bt[1..n] —— 存储编号为1至n的结点
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位串，不是字符串，即写入 压缩文件中的是“位
