根树及其应用课件

1、二叉树及其应用姓名：李 曲学院：软件学院数缺形少直觉，形缺数难入微。华罗庚（19101985）2022/7/28软件学院李曲离散数学本次课在离散数学课的地位离散数学是软件工程本科的计算机数学专业必修课。也是唯一的一门计算机数学基础课。前面我们学习了树和二叉树的基本概念。本节内容是关于树和根树的概念深化和重要应用。二叉树及其应用是后续数据结构、数据库原理、编译原理等课程的重要基础。二叉树同时也是许多前沿科学例如演化计算的重要工具。2022/7/28软件学院李曲离散数学问题的来源对于同一内容的编码，如果采用多种不同的编码，其中重码率最小，编码长度最短的编码显然效率最高。在实际的通讯和代码传输过程中

2、，我们除了考虑编码和解码的准确率以外，还要常常要考虑编码和解码的效率，以及传输的效率问题（总的编码长度问题）。2022/7/28软件学院李曲离散数学一个通信的实例假设我们需要采用二进制字符串来传送一组电文ABACCDA。我们要考虑以下几个问题：1.什么样的编码能够解决这个问题？2.什么样的编码效率最高（即总的电文码长最短）？2022/7/28软件学院李曲离散数学解决方案A原电文只有ABCD四种字符。如果采用等长二进制编码，我们只需要二位二进制编码即可解决这个问题。设ABCD的编码分别为00，01，10，1100010010101100A B A C C D A优点：简单明了，编码和译码都简单。

3、缺点：总码长较长。对稍大的问题而言，冗余太大。有没有更短的编码方案？2022/7/28软件学院李曲离散数学解决方案B假设ABCD的编码分别为0，00，1，01采用不等长编码。对电文中出现频率较高的字母采用尽可能短的编码，则总电文可减少。A B A C C D A0 00 0 1 1 01 0优点：总码长为9，更短。缺点：解码时有歧义。0000译成AAAA还是ABA还是BB？2022/7/28软件学院李曲离散数学前缀码的概念给定一个序列的集合，若没有一个序列是另外一个序列的前缀，则该集合称为前缀码。例如 000,001,01,10,11是前缀码，而111,00011,000,01就不是前缀码。2

4、022/7/28软件学院李曲离散数学解决方案C采用不定长的前缀码。假设ABCD的编码分别为01,000,001,1A B A C C D A01 000 01 001 001 1 01优点：译码时不会产生歧义。缺点：编码比等长编码还长，效率太低（16位长度）。2022/7/28软件学院李曲离散数学解决方案D高效的编码应该具备以下两个性质：编码要避免歧义（译码时不能出现同一串字符出现多种译法的情况）。编码的总长度尽可能短（出现频率高的字母的码长尽量短）。满足以上两条的编码方法是否存在？2022/7/28软件学院李曲离散数学Huffman树的引入前面我们已经学习了路径和路径长度的概念。学会了采用叶

5、节点的权值和路径长度来求树的权值。53322W(T) 22335332382+112=22022/7/28软件学院李曲离散数学最优二叉树的引入上面的二叉树是不是权为2,2,3,3,5的最优树？我们可以用Huffman算法来求最优树。如果不是最优树，那么应该如何求最优树？在所有带权w1,w2, , wt的二叉树中，w(T)最小的那棵二叉树称为最优二叉树（简称最优树）。2022/7/28软件学院李曲离散数学Huffman算法给定一组权值w1,w2,wt,且w1w2 wt。(1)连接权为w1, w2的两片树叶，得到一个分支点，其权为w1+w2。(2)在w1+w2,w3,wt中，选出两个最小的权，连接

6、它们对应的顶点，得到新分支点及其所带的权。(3)重复(2)，直到形成t-1个分支点，t片树叶为止。2022/7/28软件学院李曲离散数学Huffman算法的实例求带权2，2，3，3，5的最优二叉树。解：对于2,2,3,3,5，最小的两个权为2,2224得到权值为3,3,4,5的一个权值序列。2022/7/28软件学院李曲离散数学对于权值为3,3,4,5的一个权值序列。224336得到权值为4，5，6的权值序列。224336592022/7/28软件学院李曲离散数学最后得到权值为6，9的权值序列，得到如下的Huffman树，即为最优树。1522433659从这个最优二叉树我们可以看到它的权为： W(T)2323523232342022/7/28软件学院李曲离散数学二叉树和前缀码的关系152243365900001111000000101101112022/7/28软件学院李曲离散数学用Huffman树求通信问题的D方案1）对于电文ABACCDA，统计ABCD出现的频率。得到ABCD的对应的权分别为3,1,2,1。原问题转化成为求3，1，2，1为权的Huffman