第六章树和二叉树.ppt

《第六章树和二叉树.ppt》由会员分享，可在线阅读，更多相关《第六章树和二叉树.ppt（84页珍藏版）》请在三一文库上搜索。

1、主讲：薛春艳,树和二叉树,主 要 内 容,1. 树的定义与基本术语,2. 二叉树,3. 二叉树的遍历与线索化,4. 树、森林和二叉树的关系,5. 哈夫曼树及其应用,引 言,【树的原型】 社会生活中：家族的族谱，政府自上至下摄制的机构体系，学校的管理体系，公司的管理体系等等。,【树的抽象】 树是对具有层次关系的数据元素集合的抽象。,【树的应用】 操作系统中：文件系统的组织； 编译系统中：复合语句的句法； 表达式表示中：表达式树； 编码与解码中：Huffman树。,树的概念,【树】n(n0)个结点的有限集合T。 当n=0时，称为空树； 当n0时，该集合满足如下条件：,1、其中必有一个称为根（T）的

2、特定结点，它没有直接前驱，但有零个或多个直接后继。,2、其余n-1个结点可以划分成m（m0）个互不相交的有限集T1，T2，T3，Tm，其中Ti又是一棵树，称为根T的子树。每棵子树的根结点有且仅有一个直接前驱，可有零个或多个直接后继。,1. 有且仅有一个结点没有前驱结点,该结点为树的根结点。,2. 除了根结点外,每个结点有且仅有一个直接前驱结点。,3. 包括根结点在内，每个结点可以有多个后继结点。,树的逻辑特点,子树,根,1. 倒置树结构（树型表示法）,2. 广义表形式（嵌套括号表示法）,(A ( B ( E ( K , L ) , F ) , C ( G ) , D ( H ( M ) , I

3、 , J ) ) ),树的图解表示法,结 点：包含数据元素及若干指向其子树的分支信息。 结点的度：一个结点的子树个数称为此结点的度。 叶子结点：度为0的结点，即无后继的结点，也为终端结点。 分支结点：度不为0的结点，也称为非终端结点。 结点的层次：从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。 结点的层序编号：将树中的结点按从上层到下层、同层从左到右的次序排成一个线性序列，依次给它们编以连续的自然数。 树 的 度：树中所有结点的度的最大值。 树的高度（深度）：树中所有结点的层次的最大值。,树的相关术语,结 点 结点的度 叶子结点 分支结点 结点的层次 结点的层序编号 树

4、 的 度 树的高度（深度）,树的相关术语,有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。,森 林： m(m0)棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。,同 构：对两棵树，通过对结点适当地重命名，就可以使两棵树完全相等（结点对应相等，对应结点的相关关系也相等），则称这两棵树同构。,树的相关术语,双亲结点：一个结点的直接前驱称为该结点的双亲结点。上图中A是B、C的双亲。,兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。上图中的结点H、I、J互为兄弟结点。,祖先结点：一个结点的祖先结点是指从根结点到该

5、结点的路径上的所有结点。结点K的祖先结点是A、B、E。,子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点。如结点D的子孙是H、I、J、M。,孩子结点：一个结点的直接后继称为该结点的孩子结点。如上图的B、C是A的孩子。,堂 兄 弟：父亲是兄弟关系或堂兄关系的结点称为堂兄弟结点。在图6.1中，结点E、G、H互为堂兄弟。,树的相关术语,【定义】我们把满足以下两个条件的树型结构叫做二叉树（Binary Tree）： （1）每个结点的度都不大于2； （2）每个结点的孩子结点次序不能任意颠倒。,下面给出二叉树的五种基本形态：,二叉树的定义与基本操作,Root(T); Value(T, e); P

6、arent(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();,二叉树的基本操作查找类:,CreateBiTree(,二叉树的基本操作插入类:,二叉树的基本操作删除类:,ClearBiTre

7、e(,性质1：在二叉树的第i层上至多有2i-1个结点(i1)。,1、当i=1时，二叉树只有一个根结点，此时 2i-1=20=1，结论成立。,【证明】,2、假设i=k时结论成立，即第k层上结点总数最多为2k-1个。,3、现证明当i=k+1时，结论成立：,因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即 22k-1=2(k+1)-1 故结论成立。,二叉树的性质（一）,性质2：深度为k的二叉树至多有2k-1个结点（k1）。,因为深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树的结点总数至多为：,故结论成立。,二叉树的

8、性质（二）,【证明】,性质3：对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0= n2+1 。,设二叉树中结点总数为n，n1为二叉树中度为1的结点总数。因为二叉树中所有结点的度小于等于2，所以有n= n0+ n1+n2 设二叉树中分支数目为B，因为除根结点外，每个结点均对应一个进入它的分支，所以有：n=B+1。 又因为二叉树中的分支都是由度为1和度为2的结点发出，所以分支数目为： B=n1+2n2 整理上述两式可得到：n=B+1=n1+2n2+1 将n= n0+ n1+n2代入上式得出n0+ n1+n2=n1+2n2+1，整理后得n0= n2+1，故结论成立。,二叉树

9、的性质（三）,【证明】,满二叉树：深度为k且有2k-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。,满二叉树,两种特殊的二叉树,关系：满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。,完全二叉树：深度为k，结点数为n的二叉树，如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号一一对应，则为完全二叉树 。,两种特殊的二叉树,性质4：具有n个结点的完全二叉树深度为 log2n +1。,设n个结点的完全二叉树的深度为k，根据性质2可知，k-1层满二叉树的结点总数为： 2k-1-1 k 层满二叉树的结点总数为： 2k-1 显然有： 2k-1 - 1 n 2

10、k- 1 2k- 1 n 2k 取对数有：k -1 log2n k 因为k是整数，所以k -1 = log2n ， k= log2n+1 结论成立。,二叉树的性质（四）,【证明】,性质5：对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：,(1)若i = 1, 则 i 无双亲结点 若i 1, 则 i 的双亲结点为i /2 (2)若2*i n, 则 i 无左孩子 若2*in, 则 i 结点的左孩子结点为2*i (3)若 2*i+1 n ,则i 无右孩子 若 2*i+1n, 则i的右孩子结点为2* i+1,二叉树的性质

11、（五）,1、完全二叉树的顺序存储结构,二叉树的顺序存储结构：,二叉树的顺序存储结构,根据完全二叉树的性质5 ,对于深度为h 的完全二叉树, 将树中所有结点的数据信息按照编号的顺序依次存储到一维数组T1:2h-1中,由于编号与数组的下标一一对应, 该数组就是该完全二叉树的顺序存储结构.,2. 一般二叉树的顺序存储结构,单支树,1、在二叉树中“添加”一些实际上二叉树中并不存在的“虚结点” ，使其在形式上成为一棵“完全二叉树”； 2、然后按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放于数组T1: 2h -1中。,例如:,对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。我

12、们可以设计每个结点至少包括三个域：数据域、左孩子域和右孩子域：,二叉链表,二叉树T,二叉链表,二叉树的链式存储结构,typedef struct BiTNode TElemType data; struct BiTNode *lchild , *rchild ; BiTNode , *BiTree ;,结论：若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域，其中必有n +1个空的指针域。（分支数目B=n-1，即非空的指针域有n -1个，故空指针域有2n-(n-1)=n+1个。）,二叉树的链式存储结构,什么是二叉树的遍历,按照一定的顺序( 原则 )对二叉树中每一个结点都访问一次(仅访

13、问一次), 得到一个由该二叉树的所有结点组成的序列, 这一过程称为二叉树的遍历.,二叉树的遍历与线索化,“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。,二叉树的遍历,用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，那么对二叉树的遍历顺序有：,访问根，遍历左子树，遍历右子树 (记做DLR)。 遍历左子树，访问根，遍历右子树 (记做LDR)。 遍历左子树，遍历右子树，访问根 (记做LRD)。,常用的二叉树的遍历方法: 1.前序遍历 2.中

14、序遍历 3.后序遍历 4.按层次遍历,二.前序遍历,前序序列:,A,B,D,E,J,C,F,I,原则: 若被遍历的二叉树非空, 则 1. 访问根结点; 2. 以前序遍历原则遍历根结点的左子树; 3. 以前序遍历原则遍历根结点的右子树.,G,三.中序遍历,中序序列:,D,B,J,E,A,F,I,C,原则: 若被遍历的二叉树非空, 则 1. 以中序遍历原则遍历根结点的左子树; 2. 访问根结点; 3. 以中序遍历原则遍历根结点的右子树.,G,四.后序遍历,后序序列:,D,J,E,B,I,F,G,C,原则: 若被遍历的二叉树非空, 则 1. 以后序遍历原则遍历根结点的左子树; 2. 以后序遍历原则遍

15、历根结点的右子树. 3. 访问根结点;,A,前序遍历序列: A, B, D, K, J, G, C, F, I, E, H,中序遍历序列: D, B, G, J, K, A, F, I, E, C, H,后序遍历序列: D, G, J, K, B, E, I, F, H, C, A,按层次遍历序列: A, B, C, D, K, F, H, J, I, G, E,【例】对于如下图的二叉树，其先序、中序、后序遍历的序列为： 先序遍历： A、B、D、F、G、C、E、H 。 中序遍历： B、F、D、G、A、C、E、H 。 后序遍历： F、G、D、B、H、E、C、A 。,void PreOrder (

16、 BiTree T) if (T!=NULL) Visit (T -data); PreOrder (T -LChild); PreOrder (T -RChild); ,遍历算法先序,void PreOrder ( BiTree T) if (T!=NULL； Visit (T -data); PreOrder (T -LChild); PreOrder (T -RChild); ,void InOrder ( BiTree T ) if (T!=NULL) InOrder ( T -LChild ); Visit ( T -data); InOrder ( T -RChild); ,遍历算

17、法中序,void PostOrder ( BiTree T ) if(T!=NULL) PostOrder (T -LChild); PostOrder (T -RChild); Visit (T -data); ,遍历算法后序,void PreOrder ( BiTree T ) if (T!=NULL) printf (T -data); PreOrder ( T -LChild ); PreOrder ( T -RChild ); ,【 输出二叉树中的结点 】 输出二叉树中的结点并无次序要求，因此可用三种遍历算法中的任何一种完成，只需将访问操作具体变为打印操作即可。下面给出采用前序遍历实

18、现的算法。,遍历算法的应用（一）,【 输出二叉树中的叶子结点 】 输出二叉树中的叶子结点与输出二叉树中的结点相比，它是一个有条件的输出问题，即在遍历过程中走到每一个结点时需进行测试，看是否满足叶子结点的条件。,void PreOrder ( BiTree T ) if ( T!=NULL ) if (T -LChild=NULL ,遍历算法的应用（二）,【统计叶子结点数目】 统计二叉树中的叶子结点数目并无次序要求，因此可用三种遍历算法中的任何一种完成，只需将访问操作具体变为判断是否为叶子结点及统计操作即可。,void leaf(BiTree T) if(T!=NULL) leaf ( T-LC

19、hild ); leaf ( T-RChild ); if ( T -LChild=NULL ,遍历算法的应用（三）,【建立二叉链表方式存储的二叉树】 采用类似先序遍历的递归算法，首先读入当前根结点的数据，如果是 则将当前树根置为空，否则申请一个新结点，存入当前根结点的数据，分别用当前根结点的左子域和右子域进行递归调用，创建左右子树。,void CreateBiTree ( BiTree ,遍历算法的应用（四）,【 二叉树T的高度 】 若T为空，则高度为0 若T非空，其高度应为其左右子树高度的最大值加1,int PostTreeDepth ( BiTree T ) int hl, hr, ma

20、x; if ( T!=NULL ) hl =PostTreeDepth ( T-LChild ); hr=PostTreeDepth ( T-RChild ); max = hlhr ? hl:hr ; return(max+1); else return(0); ,遍历算法的应用（五）,二叉树遍历的应用,中序遍历：当遍历到某一结点时，说明其左子树上的所有结点均已访问完毕。可以完成对其左子树上结点的操作。,后序遍历：当遍历到某一结点时，其所有子树上的结点均已访问完毕。可以完成统计某结点子孙结点信息的操作、删去以某结点为根的子树、求其子孙结点的个数等操作。,先序遍历：当遍历到某一结点时，说明该结

21、点的所有祖先结点已经访问完了，所以，对二叉树进行先序遍历的同时记录下所访问的结点的特定信息，就可以完成统计某个结点所有祖先结点的个数，还可以求出两棵二叉树的共同祖先，以及求出从根结点到某个特定结点的路径等操作。,层次遍历：可以用来完成统计树的高度、按编号大小输出结点等操作。,1、在树的先序遍历序列中，第一个结点必是根D； 2、由于中序遍历是先遍历左子树L，然后是根D，最后遍历右子树R，则根结点D将中序序列分割成两部分：在D之前是左子树结点的中序序列，在D之后是右子树结点的中序序列。 3、根据左子树的中序序列中结点个数，又可将先序序列除根以外分成左子树的先序序列和右子树的先序序列两个部分。 依次

22、类推，便可递归得到整棵二叉树 。,遍历序列确定二叉树,1、首先由先序序列得知二叉树的根为18。 2、再由其中序序列将根结点的左右子树划分出来，其左子树的中序序列为（3，7，11，14），右子树的中序序列为（22，27，35）。 3、由上可知，其左子树的先序序列必为（14，7，3，11），右子树的先序序列为（22 35 27）。类似地，可由左子树的先序序列和中序序列来判断根结点的左子树的具体结构，由右子树的先序序列和中序序列来判断根结点的左子树的具体结构。 依此类推，最终得到整棵树的结构。,例：已知结点的先序序列和中序序列 先序序列：18 14 7 3 11 22 35 27 中序序列：3 7

23、11 14 18 22 27 35 则可按上述分解求得整棵二叉树。,例：已知结点的先序序列和中序序列 先序序列：A B D E J C F I G 中序序列：D B J E A F I C G 则可按上述分解求得整棵二叉树。,例：已知结点的中序序列和后序序列 中序序列：A B C E F G H D 后序序列：A B F H G E D C 则可按上述分解求得整棵二叉树。,遍历序列确定二叉树,结论一：已知一棵二叉树的后序序列和中序序列，则可唯一确定一棵二叉树。 结论二：已知一棵二叉树的先序序列和中序序列，则可唯一确定一棵二叉树。 结论三：只知道先序序列和后序序列不能唯一确定一棵二叉树。,二叉树

24、的遍历运算是将二叉树中结点按一定规律线性化的过程。当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在遍历序列中的前驱和后继信息。,线索二叉树,第一种方法：是将二叉树遍历一遍，在遍历过程中便可得到结点的前驱和后继，但这种动态访问浪费时间； 第二种方法：是充分利用二叉链表中的空指针域，将遍历过程中结点的前驱、后继信息保存下来。,线索二叉树,一.什么是线索二叉树,二.线索二叉树的构造,利用二叉链表中空的指针域指出结点在遍历序列中的直接前驱和直接后继;这些指向前驱和后继的指针称为线索, 加了线索的二叉树称为线索二叉树.,利用结点的空的左指针域存放该结点的直接前驱的地址,空的

25、右指针域存放该结点直接后继的地址; 而非空的指针域仍然存放结点的左孩子或右孩子的地址.,在有n个结点的二叉链表中共有2n个链域，但只有n-1个有用非空链域，其余n+1个链域是空的。我们可以利用剩下的n+1个空链域来存放遍历过程中结点的前驱和后继信息。,中序序列： D, B, J, E, A, H, F, I, C, G,为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域，如下图所示：,线索二叉树结点结构,中序序列: D, B, J, E, A, H, F, I, C, G,线 索：在这种存储结构中，指向前驱和后继结点的指针叫做线索。 线 索链 表：以这种结构组成的二叉链表作为二叉树的存

26、储结构，叫做线索链表。 线 索 化：对二叉树以某种次序进行遍历并且加上线索的过程叫做线索化。 线索二叉树：线索化了的二叉树称线索二叉树。,线索二叉树的相关概念,下面是对同一棵二叉树的遍历方法不同得到的不同线索树。,typedef enum Link, Thread PointerThr ; / Link=0:指针，Thread=1:线索 typedef struct BiThrNod TElemType data; struct BiThrNode *lchild , *rchild; PointerThr LTag , RTag ; BiThrNode, *BiThrTree;,二叉树的二叉

27、线索存储表示,void InOrderTraverse_Thr(BiThrTree T, ) p = T-lchild ; / p指向根结点 while (p != T) / 空树或遍历结束时，p=T while ( p-LTag=Link ) p = p-lchild; while ( p-RTag=Thread ,中序遍历双向线索链表,void InThreading(BiThrTree p) if (p) / 对以p为根的非空二叉树进行线索化 InThreading ( p-lchild ) ; / 左子树线索化 if (!p-lchild) / 建前驱线索 p-LTag = Threa

28、d; p-lchild = pre; if ( !pre-rchild ) / 建后继线索 pre-RTag = Thread ; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驱 InThreading(p-rchild); / 右子树线索化 ,中序遍历建立中序线索链表,1. 树转换为二叉树,我们约定树中每一个结点的孩子结点按从左到右的次序顺序编号，也就是说，把树作为有序树看待。,树、森林与二叉树的转换, 树中所有相邻兄弟之间加一条连线。 对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。 以树的根结点为轴心，将整棵树顺

29、时针旋转一定的角度，使之结构层次分明。,树与二叉树的转换,1、树中的任意一个结点都对应于二叉树中的一个结点； 2、树中某结点的第一个孩子在二叉树中是相应结点的左孩子； 3、树中某结点的右兄弟结点在二叉树中是相应结点的右孩子； 4、在二叉树中，左分支上的各结点在原来的树中是父子关系； 5、在二叉树中，右分支上的各结点在原来的树中是兄弟关系； 6、由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必然为空。,结论：,森林转换为二叉树的方法为：,（1）将森林中的每棵树转换成相应的二叉树。 （2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当

30、所有二叉树连在一起后，即为由森林转换得到的二叉树。,森林与二叉树的转换,一棵二叉树还原为树或森林，具体方法为：,(1)若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、都与该结点的双亲结点用线连起来。 (2)删掉原二叉树中所有双亲结点与右孩子结点的连线。 (3)整理由（1）、（2）两步所得到的树或森林，使之结构层次分明。,二叉树还原为树或森林,1. 树的遍历,（1）先根遍历,若树非空，则： 访问根结点。 从左到右，依次先根遍历根结点的每一棵子树。,如图中树的先根遍历序列为：A B E C F H G D。,树 的 遍 历,(2)后根遍历,树 的 遍 历,如图中树的后根遍历序列为：E

31、 B H F G C D A。,从左到右，依次后根遍历 根结点的每一棵子树。 访问根结点。,(1) 先序遍历,访问森林中第一棵树的根结点。 先序遍历第一棵树的根结点的子树森林。 先序遍历除了第一棵树以外剩余的树构成的森林。,森林的遍历先序,先序遍历序列为：A B C D E F G H I J。,中序遍历森林中第一棵树的根结点的子树森林。 访问第一棵树的根结点。 中序遍历除了第一棵树以外剩余的树构成的森林。,中序遍历序列为：B C D A F E H J I G。,(2) 中序遍历,森林的遍历中序,路径：从根结点到树中其余某个结点所经过的分支构成 由根结点到这个结点的路径。 路径长度：一条路径

32、上的分支数目称这条路径的路径长度。,哈夫曼树及其应用,带权路径长度： 设二叉树有n个带权值的叶子结点，定义从二叉树的根结点到二叉树中所有叶子结点的路径长度li与相应叶子结点权值wi的乘积之和称作该二叉树的带权路径长度。,WPL =,T,WPL(T) =72+52+23+43+92 = 60,WPL(T) =72+52+23+43+92 = 60,WPL(T) = 74+94+53+42+21 = 89,哈夫曼树（最优二叉树）：它是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最短的二叉树。,T,T,第1步：初始化,例：已知5个带权叶子结点的权值分别为W 4，6，3，9，5，求这五个叶子

33、结点所构造的哈夫曼树,第2步：选取与合并,第3步：删除与加入,9,4,6,3,5,7,4,3,重复(2)、(3)两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。,第1步：初始化,第2步：选取与合并,第3步：删除与加入,9,6,5,6,5,例：已知5个带权叶子结点的权值分别为W 4，6，3，9，5，求这五个叶子结点所构造的哈夫曼树,重复(2)、(3)两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。,第1步：初始化,第2步：选取与合并,第3步：删除与加入,9,9,例：已知5个带权叶子结点的权值分别为W 4，6，3，9，5，求这五个叶子结点所构造的哈夫曼树,重复(2)、(3)

34、两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。,第1步：初始化,第2步：选取与合并,第3步：删除与加入,例：已知5个带权叶子结点的权值分别为W 4，6，3，9，5，求这五个叶子结点所构造的哈夫曼树,重复(2)、(3)两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。,初始化的带权值的结点构造成哈夫曼树以后构成了树中的叶子结点。 给定一组带权值的结点，所能够造的哈夫曼树是不唯一。 哈夫曼树的根结点的权值等于所有叶子结点的权值之和。 在一棵哈夫曼树中，离根节点较远的叶子结点一般都是权值比较小的，离根节点较近的叶子结点都是权值比较大的。,哈夫曼树的特点,哈夫曼树最典型的应用是

35、在编码技术上的应用。利用哈夫曼树，我们可以得到平均长度最短的编码。,(1)前缀码：如果在一个编码系统中，任一个编码都不是其他任何编码的前缀（最左子串），则称该编码系统中的编码是前缀码。例如，一组编码01，001，010，100，110就不是前缀码，因为01是010的前缀，若去掉01或010就是前缀码。例如，名字中的郑霞、郑霞锦就不是前缀码。 (2)哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。,哈夫曼编码,定理6-1 哈夫曼编码是前缀码。,定理6-2 哈夫曼编码是最优前

36、缀码。 即对于n个字符，分别以它们的使用频度为叶子权值，构造哈夫曼树，则该树对应的哈夫曼编码，能使各种报文（由这n种字符构成的文本）对应的二进制串的平均长度最短。,哈夫曼编码,例如：对5个权值 5 , 6 , 3 , 9 , 7 构造最优二叉树。,哈夫曼树是一种二叉树 ,由于哈夫曼树中没有度为1的结点，则一棵有n个叶子的哈夫曼树共有2n1个结点，可以用一个大小为2n1 的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。,静态三叉链表中：每个结点的结构为 :,各结点存储在一维数组中，0号单元不使用，从1号位置开始使用。,哈夫曼编码实现,

37、存储结构,例：传送数据中的二进制编码。要传送数据 state , seat , act , tea , cat , set , a , eat ，如何使传送的长度最短？,先计算各个字符出现的次数，然后将出现次数当作权，构造哈夫曼树,建立哈夫曼树的结果如下表：,哈夫曼编码,c: 000 s: 001 e: 01 a: 10 t: 11,c: 010 s: 011 e: 00 a: 10 t: 11,1、Huffman编码不是唯一的。 2、Huffman编码对不同信源的编码效率是不同的。 3、Huffman编码结果不等长，硬件实现困难，另外误码传播严重。 4、一般情况下，Huffman 编码的效率

38、要比其它编码方法的效率高，是最佳变长码。但Huffman编码依赖于信源的统计特性，必须先统计出信源的概率特性才能编码，这就限制了实际的应用。,哈夫曼编码的特点,哈夫曼树的类型定义,typedef struct int weight ; /* 结点的权值*/ int parent ; /* 双亲的下标*/ int LChild ; /* 左孩子结点的下标*/ int RChild ; /* 右孩子结点的下标*/ HTNode, *HuffmanTree; /* 动态分配数组存储哈夫曼树。 */ typedef char *HuffmanCode; /* 动态分配数组存储哈夫曼编码。*/,【算法描

39、述】 void HoffmanCoding(HuffmanTree ,【算法描述】/从叶子到根逆向求每个字符的哈夫曼编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cd=(char *)malloc(n*sizeof(char);/分配求编码的工作空间 cdn-1=“0“;/编码结束符 for (i=1;i=n;+i) start=n-1;/编码结束符位置 for (c=i,f=HTi.parent ; f!=0 ; c=f , f=HTf.parent) if ( HTf.lchild=c ) cd-start=“0“; else cd-start=“1“; HCi=(char *)malloc(n-start)*sizeof(char strcpy(HCi,/释放工作空间 ,