图论和应用期末论文正稿.doc

《图论和应用期末论文正稿.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、......哈夫曼树及其在通信编码中的应用摘要在通信领域中，传输信息的方法有两种，其一是等长码制方法，其二是非等长码制方式；字符出现的频率不同,在传输中采用非等长二进制编码传输会提高传输效率,在字符的出现频率已知前提下,采用最优二叉正则树算法,可以得到最佳前缀码。关键字正则二叉树前缀码最优二叉树哈夫曼编码频率java程序引言在通信中,通常采用二进制编码表示符号,如果每个要传输的符号使用频率相同,则采用等长码表示即可,但事实上不同符号在传输过程中出现的频率并不相同,有些符号出现频率相差很大,此时采用非等长编码可节省二进制数位,可达到提高效率的目的。相关基础知识下面介绍有关二

2、叉树以及哈夫曼编码的相关知识：定义1：一个有向图，若不考虑他的方向，他是一棵树，则称这个有向图为有向树。一颗有向树，如果恰有一个结点的入度为0，其余所有结点的入度都为1，则称为根树，其中入度为0的结点称为树根，出度为0的结点称为树叶，出度不为0的结点称为分支点或内点。在根树中，称从树根到结点v的距离称为该点的层次。定义2：在根树中，若从到可达，则称是的祖先，是的后代，又若是树根中的有向边，则称是的父亲，是专业技术资料......的儿子；如果两个结点是同一结点的儿子，则称这两个结点是兄弟。定义3：在根树中，任一结点及其的后代和从出发的所有有向路中的边构成的子图称为以为根的子

3、路，根树中的结点的子树是以的儿子为根的子树。定义4：如果在根树中规定了每一层次上结点的次序，这样的根树称为有序树。在有序树中规定了同一层次结点的次序是从左至右。定义5：一个有向图，如果他的每个连通分支是有向树，则称该有向图为森林；在森林中，如果所有树都是有序树且给树指定了次序，则称此森林为有序森林。在树的实际应用中，我们经常用到m叉树。定义6：在根树T中，若结点的最大出度为m，则称T为m叉树，如果T的每个分支点的出度都恰好等于m，则称T为m叉树。若完全m叉树的所有叶结点在同一层，则称他为正则m叉树。二叉树的每个结点v至多有两颗子树，分别称为v的左子树和右子树。若结点v只有

4、一颗子树，则称他为v的左子树或右子树均可。若T是正则m叉树，并且是有序树，则称T为m元有序树。简单来讲：二叉树的定义[1]：二叉树是结点的有限集合且集合是有限的，这个集合要么为空，要么是由一个根结点和不相交的左、右子树构成。二叉树的特性[2]：在二叉树中每个结点最多只能有两个孩子，分别是这个结点的左孩子和右孩子，这一点也说明了在二叉树中结点的度没有大2的，并且特别注意二叉树的左子树、右子树的次序是不能颠倒的。定义7：设有一颗二叉树，有t片树叶，使其树叶分别带权的二叉树称为带权二叉树。定义8：设有一颗带权的二叉树T，其权为的树叶的层数为专业技术资料......该带权二叉树的

5、权为W(T)定义为在所有带权的二叉树中，最小的树称为最优二叉树。哈夫曼树的有关知识哈夫曼编码（HuffmanCoding）是一种编码方式，并且是可变字长编码。它是在1952年由DavidA.Huffman提出的，这种编码方式发表于《一种构建极小多余编码的方法》一文。哈夫曼编码是一种用于无损数据压缩的权编码算法，即在计算机的数据处理中，哈夫曼编码使用的是一种变长的编码表对源文件（如文件的一个字母）进行编码，其中变长编码就是通过评估源符号出现的机率得到的。并且出现次数较高的字母使用较短的编码，出现次数较低的字母则使用较长的编码，这样就使得编码之后的字符串的平均长度和期望值大大

6、降低，从而达到节约内存、提高执行效率的目的。这个编码需要我们先建立一个哈夫曼树（关键部分），哈夫曼树建立以后从根结点到各个叶子结点的左分支为0，右分支为1，然后从上到下依次写出每个结点的哈弗曼编码。哈夫曼树：假设有t个权值，并且由这些权值按照一定的规则构造一棵共有t个叶子结点的二叉树，并且每一个叶子结点都对应一个权值，经过计算带权路径长度W(T)最小的二叉树就是哈夫曼树。由于哈夫曼树是最优二叉树，故哈夫曼树同样必须满足二叉树的特点。Huffman算法（1）给定权重序列，且。（2）连接权为的两片树叶，得一个分支点其权为；专业技术资料......在中选择两个中最小的权，连接他

7、们对应的结点（不一定是树叶），得新分支点及所带的权；（3）重复（2），直到形成t-1个分支点，t片树叶为止。用一个例子来理解一下以上概念给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：181818 1114612741224275654257专业技术资料......(a)(b)(c)(a)(b)(c)其中(c)树的最小，可以验证，它就是哈夫曼树。注意：①叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。②最优二叉树中，