哈夫曼树与哈夫曼编码.ppt

一、最优树的定义

树的带权路径长度定义为：
树中所有叶子结点的带权路径长度之和
WPL(T)=wklk(对所有叶子结点)。根据给定的n个权值{w1,w2,…,wn}，
构造n棵二叉树的集合
F={T1,T2,…,Tn}，
其中每棵二叉树中均只含一个带权值
为wi的根结点，其左、右子树为空树；在F中选取其根结点的权值为最
小的两棵二叉树，分别作为左、
右子树构造一棵新的二叉树，并
置这棵新的二叉树根结点的权值
为其左、右子树根结点的权值之
和；从F中删去这两棵树，同时加入
刚生成的新树；96若要设计不等长的编码，则必须任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀，这种编码称为前缀编码。四、赫夫曼编码利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。
例6－2：
1.熟练掌握二叉树的结构特性，了解相应的证明方法。
2.熟悉二叉树的各种存储结构的特点及适用范围。
3.遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。4.理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握1至2种建立二叉树和树的存储结构的方法。
6.学会编写实现树的各种操作的算法。
7.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。复习题以下说法错误的是（）
存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同。
二叉树是树的特殊情形。
由树转换成二叉树，其根结点的右子树总是空的。
在二叉树只有一棵子树的情况下，也要明确指出该子树是左子树还是右子树。
答案：B树的基本遍历策略可分为先根遍历和后根遍历，二叉树的基本遍历策略分为先序、中序和后序三种遍历。我们把由树转化得到的二叉树称该树对应的二叉树，则下面（）是正确的。
树的先根遍历序列与其对应的二叉树先序遍历序列相同。
树的后根遍历序列与其对应的二叉树后序遍历序列相同。
树的先根遍历序列与其对应的二叉树中序遍历序列相同。
以上均不对。
答案：A下面几个符号串编码集合中，不是前缀编码的是（）。
{0,10,110,1111}
{11,10,001,101,0001}
{00,010,0110,1000}
{b,c,aa,ac,aba,abb,abc}
答案：B对于前序遍历与中序遍历结果相同的二叉树为（），对于前序遍历和后序遍历结果相同的二叉树为（）。
一般二叉树
只有根结点的二叉树
根结点无左孩子的二叉树
根结点无右孩子的二叉树
所有结点只有左子树的二叉树
所有结点只有右子树的二叉树
答案：F,B
一、已知一棵完全二叉树共有892个结点，试求：
1、树的高度。
2、叶子结点数
3、单支结点数
4、最后一个非终端结点的序号。