最优编码与译码的实现.ppt

《最优编码与译码的实现.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2教学目标教学目标1、知识目标1）了解二叉树的有关概念以及二叉树的存储结构；2）了解哈夫曼树的概念，会生成哈夫曼树；3）掌握哈夫曼基本操作的实现算法。2、能力目标1）具有恰当的选择二叉树作为数据的逻辑结构和存储结构的能力；2）具有应用二叉树解决实际问题的能力。3、素质目标养成善于思考解决实际问题的良好习惯。一、任务描述任务描述：利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要

2、一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。3二、相关知识（一）二叉树1．二叉树的定义和基本运算1．1定义定义：二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。4二叉树也可以用递归的形式定义。即：二叉树是n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。51．2二叉树的基本运算（1）构造一棵二叉树CreateBTree(BT)（2）清空

3、以BT为根的二叉树ClearBTree(BT)（3）判断二叉树是否为空BTreeEmpty(BT)（4）获取给定结点的左孩子和右孩子LeftChild(BT,node)，RightChild(BT,node)（5）获取给定结点的双亲Parent(BT,node)（6）遍历二叉树Traverse(BT)62．二叉树的性质二叉树具有下列5个重要的性质。【性质1】在二叉树的第i层上最多有2i-1个结点（i≥1）。证明：二叉树的第1层只有一个根结点，所以，i=1时，2i-1=21-1=20=1成立。假设对所有的j，1≤j

4、成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2=2i-1。7【性质2】深度为K的二叉树最多有2K-1个结点（K≥1）。证明：由性质1可以得出，1至K层各层最多的结点个数分别为：20,21,22,23,...,2K-1。这是一个以2为比值的等比数列，前n项之和的计算公式为：8【性质3】对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。证明：假设度为1的结点个数为n1，结点总数为

5、n，B为二叉树中的分支数。因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：n=n0+n1+n2（1）再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数n与分支数B之间的关系为：n=B+1。又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。将此式代入上式，得：n=n1+2n2+1（2）用（1）式减去（2）式，并经过调整后得到：n0=n2+1。9满二叉树：如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。10完全二叉树：有

6、一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树。【性质4】具有n个结点的完全二叉树的深度为log2n+1。其中，log2n的结果是不大于log2n的最大整数。证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出：2K-1-1

7、log2n=K-1。整理后得到：K=log2n+1。11【性质5】对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i（1≤i≤n），都有：（1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为i/2。（2）如果2i>n，则结点i没有左孩子；否则其左孩子结点的编号为2i。（3）如果2i+1>n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。下面我们利用数学归纳法证明这个性质。我们首先证明（2）和（3）。当i=1时，若n≥3，则根的左、右孩子的编号分别是2，3；若n<3，

8、则根没有右孩子；若n<2，则根将没有左、右孩子；以上对于（2）和（3）均成立。假设：对于所有的