8哈夫曼树与哈夫曼编码课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,6.8,哈 夫 曼 树 与 哈 夫 曼 编 码,最优树的定义,如何构造最优树,前缀编码,赫夫曼编码,6.8 哈 夫 曼 树 与 哈 夫 曼 编 码,1,一、最优树的定义,树的路径长度,定义为：,树中每个结点的路径长度之和。,结点的路径长度,定义为：,从根结点到该结点的路径上,分支的数目。,一、最优树的定义树的路径长度定义为：结点的路径长度定义为,2,树的带权路径长度,定义为：,树中所有叶子,结点的带权路径长度,之和,WPL(T)=,w,k,l,k,(对所有叶子结点)。,假设有n个权值w,1,w,2,w,n,，构造一棵,有n个叶子结点的二叉树，每个叶子结点,带权为W,i,，则其中,带权路径长度取最小,值,的二叉树称为“,最优树,”。,例如：,树的带权路径长度定义为：假设有n个权值w1,w2,w,3,2,7 9,7,5,4,9,2,WPL(T)=7,2+52+23+43+92 =60,WPL(T)=7,4+94+53+42+21 =89,5,4,27 9 75492WPL(T)=7,4,根据给定的,n,个权值,w,1,w,2,w,n,，,构造,n,棵二叉树的集合,F,=T,1,T,2,T,n,，,其中每棵二叉树中均只含一个带权值,为,w,i,的根结点，其左、右子树为空树；,二、如何构造最优树,(1),(赫夫曼算法)以二叉树为例：,根据给定的 n 个权值 w1,w2,5,在,F,中选取其根结点的权值为最,小的两棵二叉树，分别作为左、,右子树构造一棵新的二叉树，并,置这棵新的二叉树根结点的权值,为其左、右子树根结点的权值之,和；,(2),在 F 中选取其根结点的权值为最(2),6,从,F,中删去这两棵树，同时加入,刚生成的新树；,重复,(2),和,(3),两步，直至,F,中只,含一棵树为止。,(3),(4),从F中删去这两棵树，同时加入 重复(2,7,9,例如:已知权值,W=5,6,2,9,7,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,9例如:已知权值 W=5,6,2,9,7 5,8,6,7,13,9,5,2,7,9,5,2,7,16,6,7,13,29,0,0,0,0,1,1,1,1,00,01,10,110,111,从根结点到叶子结点的路径上分支字符组成的字符串，可以作为每个叶子结点编码。,约定左分支表示字符0，右分支表示字符1。,671395279527166713290000111100,9,若要设计不等长的编码，则必须,任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀,，,这种编码称为前缀编码。,三、前缀编码,以传送的电文为例比较等长编码和不等长编码方法：,一、,等长编码：,电文中所需传送的字符有A、B、C、D，编码分别为00、01、10、11，若要发送ABACCDA电文，则以字符串00010010101100发送，根据字符对应的编码，在接收端能知道发送的电文为ABACCDA。,二、,不等长编码：,当A、B、C、D的编码分别为0、00、1、10，要发送上述电文以电文ABACCDA，相应的字符串为000011100，在接收端，对于子串0000的译法就有多种，可以是AAAA、BB、ABA、BAA等等。,若要设计不等长的编码，则必须任何一个字符的编码都不是同一,10,四、赫夫曼编码,如何得到使电文 总长最短的二进制前缀编码呢？假设每种字符在电文中出现的次数为wi，其编码长度为li，电文中只有n种字符，则电文总长为,wili。,对应到二叉树上，置wi为叶子结点的权，li为根到叶子的路径长度，则,wili,恰为二叉树上带权路径长度。,设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码称为赫夫曼编码。,四、赫夫曼编码 如何得到使电文 总长最短的二进,11,利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的,赫夫曼编码,是一种,最优前缀编码,，即使所传,电文的总长度最短,。,例62：,利用赫夫曼树可以构造一种不等长的二进制编码，,12,1.熟练掌握,二叉树的结构特性,，了解相应的证明方法。,2.熟悉二叉树的各种,存储结构,的特点及适用范围。,3.,遍历二叉树,是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的,递归算法,，,灵活运用遍历算法,实现二叉树的其它操作。,层次遍历,是按另一种搜索策略进行的遍历。,1.熟练掌握二叉树的结构特性，了解相应的证明方法。,13,4.理解二叉树,线索化的实质,是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的,线索化过程,以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的,线索化过程,是,基于,对二叉树进行,遍历,，而线索二叉树上的,线索又为相应的遍历提供,了,方便,。,4.理解二叉树线索化的实质是建立结点与其在相应序列中的,14,5.熟悉,树的,各种,存储结构,及其特点，掌握,树和森林与二叉树的转换,方法。建立存储结构是进行其它操作的前提，因此读者应,掌握,1 至 2 种,建立,二叉树和树的,存储结构的方法,。,6.学会编写,实现树的各种操作,的算法。,7.了解,最优树的特性,，掌握,建立最优树和哈夫曼编码,的方法。,5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的,15,复习题,一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。,250,500,254,505,以上答案都不是,答案：E,复习题一棵完全二叉树上有1001个结点，其中叶子结点的个数是,16,以下说法错误的是（）,存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同。,二叉树是树的特殊情形。,由树转换成二叉树，其根结点的右子树总是空的。,在二叉树只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。,答案：B,以下说法错误的是（）,17,树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略分为先序、中序和后序三种遍历。我们把由树转化得到的二叉树称该树对应的二叉树，则下面（）是正确的。,树的先根遍历序列与其对应的二叉树先序遍历序列相同。,树的后根遍历序列与其对应的二叉树后序遍历序列相同。,树的先根遍历序列与其对应的二叉树中序遍历序列相同。,以上均不对。,答案：A,树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策,18,下面几个符号串编码集合中，不是前缀编码的是（）。,0,10,110,1111,11,10,001,101,0001,00,010,0110,1000,b,c,aa,ac,aba,abb,abc,答案：B,下面几个符号串编码集合中，不是前缀编码的是（）。,19,对于前序遍历与中序遍历结果相同的二叉树为（），对于前序遍历和后序遍历结果相同的二叉树为（）。,一般二叉树,只有根结点的二叉树,根结点无左孩子的二叉树,根结点无右孩子的二叉树,所有结点只有左子树的二叉树,所有结点只有右子树的二叉树,答案：F,B,对于前序遍历与中序遍历结果相同的二叉树为（），对于前序遍历和,20,一、已知一棵完全二叉树共有892个结点，试求：,1、树的高度。,2、叶子结点数,3、单支结点数,4、最后一个非终端结点的序号。,1.10 2.446 3.1 4.446,1.10 2.446 3.1,21,