第6章树和二叉树(09).ppt

《第6章树和二叉树(09).ppt》由会员分享，可在线阅读，更多相关《第6章树和二叉树(09).ppt（66页珍藏版）》请在三一办公上搜索。

1、1,数据结构课程的内容,2,第1章 绪论第2章 线性表第3章 栈和队列 第4章 串第5章 数组和广义表第6章 树和二叉树 第7章 图第9章 查找第10章 排序,目 录,3,第6章 树和二叉树（Tree&Binary Tree）,6.1 树的基本概念6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.5 赫夫曼树及其应用,特点：非线性结构，一个直接前驱，但可能有多个直接后继。,（一对多或1:n）,二叉树的定义、性质和存储结构,二叉树的运算,4,6.1 树的基本概念,6.1.1 树的定义6.1.2 若干术语6.1.3 逻辑结构6.1.4 存储结构6.1.5 树的运算,5,6.1.1 树

2、的定义,注：树的定义具有递归性，即“树中还有树”。,由一个或多个(n0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n1时，其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树。,6,6.1.2 若干术语,即上层的那个结点(直接前驱)即下层结点的子树的根(直接后继)同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点,根 叶子 森林有序树无序树,即根结点(没有前驱)即终端结点(没有后继)指m棵不相交的树的集合(例如删除A后的子树个数),双亲孩

3、子兄弟堂兄弟祖先子孙,结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。,7,即树的数据元素结点挂接的子树数,结点结点的度结点的层次终端结点分支结点,树的度树的深度(或高度),从根到该结点的层数（根结点算第一层）即度为0的结点，即叶子即度不为0的结点（也称为内部结点）,所有结点度中的最大值（Max各结点的度）指所有结点中最大的层数（Max各结点的层次）,问：右上图中的结点数；树的度；树的深度,13,3,4,（有几个直接后继就是几度，亦称“次数”）,8,自学：树的抽象数据类型定义,（见教材P118-119）,ADT Tree数据对象D:数据关系R:基本操作 P：ADT Tree,

4、D是具有相同特性的数据元素的集合。若D为空集，则称为空树；/允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：root 唯一/关于根的说明 DjDk=/关于子树不相交的说明/关于数据元素的说明/至少有15个，如求树深，求某结点的双亲,9,6.1.3树的逻辑结构,一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。,6.1.4树的存储结构,讨论1：树是非线性结构，该怎样存储？,特点：,仍然有顺序存储、链式存储等方式。,10,讨论3：树的链式存储方案应该怎样制定？,复原困难,可用多重链表：一个前趋指针，n个后继指针。细节问题：树中

5、结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型）。,可规定为：,从上至下、从左至右将树的结点依次存入内存。,重大缺陷：,不能唯一复原就没有实用价值！,讨论2：树的顺序存储方案应该怎样制定？,11,树结点的结构：,困惑：构造树的结点时应当开多少个链域?,先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。,解决思路：,最简单的树二叉树,12,6.1.5树的运算,要明确：1.普通树（即多叉树）若不转化为二叉树，则运算很难实现。2.二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些

6、操作必须建立在对树结点能够“遍历”的基础上！,本章重点：二叉树的表示和实现,遍历指每个结点都被访问且仅访问一次，不遗漏不重复,13,6.2 二叉树,为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。,6.2.1 二叉树的定义6.2.2 二叉树的性质6.2.3 二叉树的存储结构,注：二叉树的运算见6.3节遍历,14,6.2.1二叉树的定义,定义：是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1:2）基本特征:每个结点最多只有两棵子树（不存在度大于2

7、的结点）；左子树和右子树次序不能颠倒。,问：具有3个结点的二叉树可能有几种不同形态？,有5种,基本形态：,15,二叉树的抽象数据类型定义（见教材P121-122）,ADT BinaryTree数据对象D:数据关系R:基本操作 P：ADT BinaryTree,D是具有相同特性的数据元素的集合。若D=，则R=；若D，则R=H；存在二元关系：root 唯一/关于根的说明 DjDk=/关于子树不相交的说明/关于数据元素的说明/关于左子树和右子树的说明/至少有20个，如返回某结点的左孩子，或中序遍历，等等,16,6.2.2二叉树的性质(3+2),讨论1：第i层的结点数最多是多少？,性质1:在二叉树的第

8、i层上至多有2i-1个结点（i0）。,性质2:深度为k的二叉树至多有2k-1个结点（k0）。,再提问：第i层上至少有 个结点？,1,讨论2：深度为k的二叉树，最多有多少个结点？,2i-1个,2k-1个,17,性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n21（即n0=n2+1）,证明：二叉树中全部结点数nn0+n1+n2(叶子数1度结点数2度结点数)又二叉树中全部结点数nB+1(总分支数根结点)（除根结点外，每个结点必有一个直接前趋，即一个分支）而 总分支数B=n1+2n2(1度结点必有1个直接后继，2度结点必有2个)三式联立可得：n0+n1+n2=n1+2n2+

9、1,即n0=n2+1,物理意义：叶子数2度结点数1,讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？,18,性质4:具有n个结点的完全二叉树的深度必为log2n1,性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i1；其双亲的编号必为i/2（i1 时为根,除外）。,证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即 2k-1-1n2k-1 或2k-1n2k三边同时取对数，于是有：k-1log2nk 因为k是整数，所以k=

10、log2n+1,可根据归纳法证明。,对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：,19,完全二叉树：深度为k 的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。,为何要研究这两种特殊形式？,因为它们在顺序存储方式下可以复原！,满二叉树：一棵深度为k 且有2k-1个结点的二叉树。（特点：每层都“充满”了结点）,满二叉树和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。,20,21,6.2.3 二叉树的存储结

11、构,一、顺序存储结构 按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。,ABCDEFGHI,问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i1（即性质5）例如，对应2的两个孩子必为4和5,即B的左孩子必是D,右孩子必为E。,T0一般不用,22,讨论：不是完全二叉树怎么办？,答：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。,ABCDE,缺点：浪费空间；插入、删除不便,23,二、链式存储结构用二叉链表即可方便表示。,二叉树结点数

12、据类型定义：typedef struct node*tree_pointer;typedef struct node int data;tree_pointer left_child,right_child;node;,一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始）注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。,24,二叉树链式存储举例：,优点：不浪费空间；插入、删除方便,25,6.3 遍历二叉树和线索二叉树,6.3.1 遍历二叉树,遍历定义遍历用途遍历方法,指按某条搜索路线遍访每个结点且不重复（又称周游）。,它是树结构插入、删除、

13、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。,对每个结点的查看通常都是“先左后右”。,Traversing Binary Tree,26,遍历规则,二叉树由根、左子树、右子树构成，定义为D、L、R,以根结点为参照系,注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。,D、L、R的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLD 若限定先左后右，则有三种实现方案：,DLR LDR LRD先序遍历 中序遍历 后序遍历,27,例1：,先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：,D B E A CD E B C A,口诀：DL

14、R先序遍历，即先根再左再右LDR中序遍历，即先左再根再右LRD后序遍历，即先左再右再根,A,B,D,E,C,28,先序遍历结果+*/A B C D E前缀表示法中序遍历结果A/B*C*D+E中缀表示法后序遍历结果A B/C*D*E+后缀表示法层次遍历结果+*E*D/C A B,例2：用二叉树表示算术表达式,29,中序遍历算法LDR(node*root)if(root!=NULL)LDR(root-lchild);printf(“%d”,root-data);LDR(root-rchild);return(0);,后序遍历算法LRD(node*root)if(root!=NULL)LRD(roo

15、t-lchild);LRD(root-rchild);printf(“%d”,root-data);return(0);,结点数据类型自定义typedef struct nodeint data;struct node*lchild,*rchild；node;node*root;,先序遍历算法DLR(node*root)if(root!=NULL)/非空二叉树 printf(“%d”,root-data);/访问DDLR(root-lchild);/递归遍历左子树DLR(root-rchild);/递归遍历右子树 return(0);,30,对遍历的分析：,1.从前面的三种遍历算法可以知道：如

16、果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。,从虚线的出发点到终点的路径上，每个结点经过3次。,第1次经过时访问，是先序遍历第2次经过时访问，是中序遍历第3次经过时访问，是后序遍历,2.二叉树遍历的时间效率和空间效率时间效率:O(n)/每个结点只访问一次空间效率:O(n)/栈占用的最大辅助空间,精确值：树深为k的递归遍历需要k+1个辅助单元,31,用空格字符表示无孩子或指针为空,如何把二叉树存入电脑内？,怎样建树？见教材P131例,例：将下面的二叉树以二叉链表形式存入计算机内。,考虑1：输入结点时怎样表示“无孩

17、子”？考虑2：以何种遍历方式来输入和建树？,将二叉树按先序遍历次序输入：A B C D E G F(/n),以先序遍历最为合适，让每个结点都能及时被连接到位。,字符串输完后应当再加一特殊的结束符号(如$)，因为 无法惟一表示结束。,32,建树算法：Status CreateBiTree(BiTree/CreateBiTree,输入序列：A B C D E G F,33,例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。分析：由后序遍历特征，根结点必在后序序列尾部（即A）；由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即BD

18、CE），其右部必全部是右子树的子孙（即FHG）；继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。,34,已知中序遍历：B D C E A F H G已知后序遍历：D E C B H G F A,（B D C E）,（F H G）,A,（D C E）,A,B,B,A,C,C,D C E,35,算法6.2 中序遍历算法的非递归描述 递归算法是通过栈来实现的，因此可仿照算法执行过程中工作栈的状态变化状况写出相应的非递归算法。以中序遍历为例，算法如下：,36,Status InOrderTraverse(BiTree T,Status(*visit)(

19、TelemType e)InitStack(S)；p=T；while(p|!StackEmpty(S)if(p)Push(S,p)p=p-lchild;else Pop(S,p)；printf(“/n”,p-data);p=p-rchild；/else/while return OK；/InOrderTraverse,37,6.3.2 线索二叉树,Threaded Binary Tree,讨论：用二叉链表法（l_child,r_child）存储包含n个结点的二叉树，结点的指针区域中会有多少个空指针？,有n+1个！,思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？我们可以用

20、它来存放当前结点的直接前驱和后继等线索，以加快查找速度。,这就是线索二叉树（Threaded Binary Tree）,38,二叉树中容易找到结点的左右孩子信息，但该结点的直接前驱和直接后继只能在某种遍历过程中动态获得。先依遍历规则把每个结点对应的前驱和后继线索预存起来，这叫做“线索化”。意义：从任一结点出发都能快速找到其前驱和后继，且不必借助堆栈。,对二叉树进行某种遍历之后，将得到一个线性有序的序列。例如对某二叉树的中序遍历结果是B D C E A F H G，意味着已将该树转为线性排列，显然其中结点具有唯一前驱和唯一后继。在此前提下，那n+1个空链域才能装入（也装得下）“线索”。,讨论2.

21、如何获得这种“直接前驱”或“直接后继”？有何意义？,讨论1：二叉树是1:2的非线性结构，如何定义其直接后继？,39,与原有的左右孩子指针域“复用”，充分利用那n+1个空链域。,规 定：,1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱(即线索)；,2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继(即线索)。,问题：计算机如何判断是孩子指针还是线索指针？,如何区别？,40,约定:,当Tag域为0时,表示正常情况;,当Tag域为1时,表示线索情况.,前驱(后继),左(右)孩子,为区别两种不同情况，特增加两个标志域：,问：增加了前驱和后

22、继等线索有什么好处？,能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整个树。,41,1.有关线索二叉树的几个术语：,线索链表：线 索：线索二叉树：线 索 化：,用含Tag的结点样式所构成的二叉链表指向结点前驱和后继的指针加上线索的二叉树对二叉树以某种次序遍历使其变为线索二叉树的过程,线索化过程就是在遍历过程中修改空指针的过程：将空的lchild改为结点的直接前驱；将空的rchild改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为“正常情况”）,42,A,G,E,I,D,J,H,C,F,B,例：带了两个标志的某先序遍历结果如下表所示，请画出对应的二叉树。,A,Tag=1表示线索:

23、Ltag=1表示前驱Rtag=1表示后继,43,悬空？NIL,悬空？NIL,解：对该二叉树中序遍历的结果为:H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行：,为避免悬空态，应增设一个头结点,例1：画出以下二叉树对应的中序线索二叉树。,2.线索二叉树的生成线索化,线索化过程就是在遍历过程中修改空指针的过程,44,注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G,对应的中序线索二叉树存储结构如图所示：,45,例2：给定如图所示二叉树T，请画出与其对应的中序线索二叉树。,解:因为中序遍历序列是：55 40 25 60 28 08 33 54对应线索树应当按此规律连线，即在

24、原二叉树中添加虚线。,46,线索二叉树的生成算法（递归算法见教材P134-135）,目的：在遍历二叉树的过程中修改空指针，添加前驱或后继的线索，使之成为线索二叉树。,为了记下遍历过程中访问结点的先后次序，需要设置两个指针：p指针当前结点之指针；pre指针当前结点的前趋结点指针。,设计技巧：依某种顺序遍历二叉树，对每个结点p，判断其左指针是否为空，以及其前驱结点的右指针是否为空。,每次只修改前驱结点的右指针（后继）和本结点的左指针（前驱），参见算法6.6。,若p-lchildNULL,则p-Ltag=1;p-lchildpre;/p的前驱线索应存p结点的左边若pre-rchildNULL,则pr

25、e-Rtag1;pre-rchild=p;/pre的后继线索应存pre结点的右边,47,3.线索二叉树的遍历（无需堆栈）,对于线索二叉树的遍历，只要找到序列中的第一个结点，然后依次访问结点的后继直到后继为空为止。（因为建立线索时已遍历一次，相当于线性化了！）,难点：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继。,以中序线索二叉树为例：当RTag=1时，直接后继指针就在其rchild域内；当RTag=0时，直接后继是当前结点右子树最左下方的结点；,请注意中序遍历规则是LDR，先左再根再右,48,5）当RTag=0时（表示有右孩子），此时应

26、当从该结点的右孩子开始(p=p-rchild）查找左下角的子孙结点；即重复2）,附：中序线索二叉树遍历步骤（算法6.5）：,1）设置一个搜索指针p；,2）先寻找中序遍历之首结点（即最左下角结点），方法是：当LTag=0时（表示有左孩子），p=p-lchild;直到LTag=1（无左孩子，已到最左下角）；首先访问p-data；,3）接着进入该结点的右子树，检查RTag 和p-rchild；,4）若该结点的RTag=1(表示有后继线索)，则 p=p-rchild；访问p-data;并重复4），直到后继结点的RTag=0；,有后继找后继，无后继找右子树的最左子孙,49,50,6.5 Huffman树

27、及其应用,一、Huffman树二、Huffman编码,最优二叉树,Huffman树,Huffman编码,带权路径长度最短的树,不等长编码,是通信中最经典的压缩编码,51,一、Huffman树（最优二叉树）,路 径：路径长度：树的路径长度：带权路径长度：树的带权路径长度：Huffman树：,由一结点到另一结点间的分支所构成。,路径上的分支数目。,从树根到每一结点的路径长度之和。,结点到根的路径长度与结点上权的乘积（WPL）,若干术语：,即树中所有叶子结点的带权路径长度之和,带权路径长度最小的树。,例如：ae的路径长度,树长度,2,10,Huffman常译为赫夫曼、霍夫曼、哈夫曼等,Weighte

28、d Path Length,52,树的带权路径长度如何计算？,经典之例：,WPL=,WPL=,WPL=,Huffman树是WPL 最小的树,树中所有叶子结点的带权路径长度之和,36,46,35,53,1.构造Huffman树的基本思想：,例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4，怎样编码才能使它们组成的报文在网络中传得最快？,法1：等长编码（如二进制编码）令d=00，i=01，a=10，n=11，则：WPL12bit(7524）36法2：不等长编码（如Huffman编码）令d=0;i=10,a=110,n=111，则：,明确：要实现Huffman编码，就要先构造Huffm

29、an树,讨论：Huffman树有什么用？,权值大的结点用短路径，权值小的结点用长路径。,WPL最小的树,频度高的信息用短码，反之用长码，传输效率肯定高！,WPL2=1bit72bit5+3bit(2+4)=35,最小冗余编码、信息高效传输,54,2.构造Huffman树的步骤（即Huffman算法）：,(1)由给定的 n 个权值 w1,w2,wn 构成n棵二叉树的集合F=T1,T2,Tn（即森林），其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。(2)在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之

30、和。(3)在F 中删去这两棵树，同时将新得到的二叉树加入 F中。(4)重复(2)和(3),直到 F 只含一棵树为止。这棵树便是Huffman树。,怎样证明它就是WPL最小的最优二叉树？参考信源编码,Huffman树的特点：没有度为1的结点。,55,step1：对权值进行合并、删除与替换在权值集合7,5,2,4中，总是合并当前值最小的两个权,具体操作步骤：,a.初始,方框表示外结点（叶子，字符）,圆框表示内结点（合并后的权值）,b.合并2 4,c.合并5 6,d.合并7 11,56,step2：按左“0”右“1”对Huffman树的所有分支编号,Huffman编码结果：d=0,i=10,a=11

31、0,n=111WPL=1bit72bit5+3bit(2+4)=35（小于等长码的WPL=36）,特征：每一码不会是另一码的前缀，译码时可惟一复原,Huffman编码也称为前缀码,将 Huffman树 与 Huffman编码 挂钩,57,二、Huffman编码,（1）由于Huffman树的WPL最小，说明编码所需要的比特数最少。,（4）Huffman编码时是从叶子走到根；而译码时又要从根走到叶子，因此每个结点需要增开双亲指针分量（连同结点权值共要开5个分量）（5）用计算机实现时，顺序和链式两种存储结构都要用到。,分析Huffman树和编码的特点：,霍夫曼编码的基本思想是出现概率大的信息用短码，

32、概率小的用长码,最小冗余,这种编码已广泛应用于网络通信中。,（2）Huffman树肯定没有度为1的结点；（3）一棵有n 0个叶子结点的Huffman树，共有2n0-1个结点；（因为n=n0+n1+n2=2n0-1),58,如何编程实现Huffman编码？,建议1：Huffman树中结点的结构可设计成5分量形式：,将整个Huffman树的结点存储在一个数组HT1.n.m中;各叶子结点的编码存储在另一“复合”数组HC1.n中。请参见教材P149图6.27的（a)和（c),建议2：Huffman树的存储结构可采用顺序存储结构：,(1)教材P147149内容；(2)严蔚敏“数据结构”演示程序；,可参考

33、：,59,typedef structunsigned int weight；/权值分量（可放大取整）unsigned int parent，lchild，rchild；/双亲和孩子分量HTNode，*HuffmanTree；/用动态数组存储Huffman树typedef char*HuffmanCode；/动态数组存储Huffman编码表,Huffman树和Huffman树编码的存储表示：,双亲,*HuffmanTree或 HT向量,HT3.parent=9,指针型指针,60,如何编程实现Huffman编码？,参见教材P147,先构造Huffman树HT，再求出N个字符的Huffman编码H

34、C。,Void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,int n),if(n=1)return;m=2*n-1;/n 0个叶子的HuffmanTree共有2n0-1个结点；HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0单元未用,*w存放n个字符的权值,for(p=HT,i=1;i=n;+i,+p,+w)*p=*w,0,0,0;/给前n0个单元初始化for(；i=m;+i,+p)*p=0,0,0,0;/对叶子之后的存储单元清零for(i=n+1;i=m;+i)/建Huffman树(从叶子后开

35、始存内结点)Select(HT,i-1,s1,s2);/在HT1i-1选择parent为0且weight最小的两个结点，其序号分别为S1和s2（教材未给出此函数源码）HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;,61,(续前)再求出n个字符的Huffman编码HC,HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配n个字符编码的头指针向量（一维数组）cd=(char*)malloc(n*sizeof(char);/分配

36、求编码的工作空间(n)cdn-1=“0”;/编码结束符（从cd0cdn-1为合法空间）For(i=1;i=n;+i)/逐个字符求Huffman编码 start=n-1;/编码结束符位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码if(HT f.lchild=c)cd-start=“0”;else cd-start=“1”;HCi=(char*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间strcpy(HCi,/释放工作空间/HuffmanCoding,62,Huffman编码举例,解：先将

37、概率放大100倍，以方便构造哈夫曼树。放大后的权值集合 w=7,19,2,6,32,3,21,10，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。,例1【严题集6.26】：假设用于通信的电文仅由8个字母 a,b,c,d,e,f,g,h 构成，它们在电文中出现的概率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，试为这8个字母设计哈夫曼编码。如果用07的二进制编码方案又如何？【类同P148例2】,63,w=7,19,2,6,32,3,21,10 在机内存储形式为:,b,c,a,d,e,g,f,h,请注意：哈夫曼树样式不惟一！,5,11,17,28

38、,40,60,100,双亲,左右孩子,64,对应的哈夫曼编码：,Huffman码的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61,3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3,二进制等长码的WPL,按左0右1标注,65,小结：哈夫曼树及其应用,1.Huffman算法的思路：权值大的结点用短路径，权值小的结点用长路径。,2.构造Huffman树的步骤：对权值的合并、删除与替换。,3.Huffman编码规则：左“0”右“1”又称为前缀码、最小冗余编码、紧致码等等，它是数据压缩学的基础。,66,本 章 小 结,1、定义和性质,2、存储结构,3、遍历,4、线索化,1:2，性质有3+2条,孩子兄弟,线索树,第6章结束,