***解答（续）17 24 17 19 20 34 24 19 20 第31页，共45页，星期日，2025年，2月5日解答（续）24 34 19 203924 34第32页，共45页，星期日，2025年，2月5日解答（续）24 34 395839第33页，共45页，星期日，2025年，2月5日解答（续）583997W(T)=6(2+3)+5*5+4*7+3(11+13+17)+2(19+20)=264第34页，共45页，星期日，2025年，2月5日最佳前缀码定义16.10设?1,?2,…,?n-1,?n是长度为n的符号串(1)前缀——?1,?1?2,…,?1?2…?n?1(2)前缀码——{?1,?2,…,?m}中任何两个元素互不为前缀(3)二元前缀码——?i(i=1,2,…,m)中只出现两个符号，如0与1.如何产生二元前缀码？定理16.6一棵2叉树产生一个二元前缀码.推论一棵正则2叉树产生惟一的前缀码（按左子树标0，右子树标1）*第35页，共45页，星期日，2025年，2月5日图所示二叉树产生的前缀码为{00,10,11,011,0100,0101}*第36页，共45页，星期日，2025年，2月5日用Huffman算法产生最佳前缀码例6在通信中，八进制数字出现的频率如下：0：25%1：20%2：15%3：10%4：10%5：10%6：5%7：5%求传输它们的最佳前缀码，并求传输10n（n?2）个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的（长为3）的码字传输需要多少个二进制数字？*第37页，共45页，星期日，2025年，2月5日解用100个八进制数字中各数字出现的个数，即以100乘各频率为权，并将各权由小到大排列，得w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.用此权产生的最优树如图所示.求最佳前缀码01-----011-----1001-----2100-----3101-----40001-----500000-----600001-----7W(T)=285，传10n(n?2)个用二进制数字需2.85?10n个，用等长码需3?10n个数字.*第38页，共45页，星期日，2025年，2月5日波兰符号法与逆波兰符号法行遍或周游根树T——对T的每个顶点访问且仅访问一次.对2叉有序正则树的周游方式：①中序行遍法——次序为：左子树、根、右子树②前序行遍法——次序为：根、左子树、右子树③后序行遍法——次序为：左子树、右子树、根对图所示根树按中序、前序、后序行遍法访问结果分别为：ba(fdg)ce，ab(c(dfg)e)，b((fgd)ec)a*第39页，共45页，星期日，2025年，2月5日用2叉有序正则树存放算式存放规则最高层次运算放在树根后依次将运算符放在根子树的根上数放在树叶上规定：被除数、被减数放在左子树树叶上算式((b+(c+d))?a)?((e?f)?(g+h)?(i?j))存放在图所示2叉树上.*第40页，共45页，星期日，2025年，2月5日波兰符号法波兰符号法按前序行遍法访问存放算式的2叉有序正则树，其结果不加括号，规定每个运算符号与其后面紧邻两个数进行运算，运算结果正确.称此算法为波兰符号法或前缀符号法.对上图的访问结果为???b+cda??ef?+gh?ij逆波兰符号法按后序行遍法访问，规定每个运算符与前面紧邻两数运算，称为逆波兰符号法或后缀符号法.对上图的访问结果为bcd++a?ef?gh+ij????*第41页，共45页，星期日，2025年，2月5日第十六章习题课主要内容无向树及其性质生成树、最小生成树、基本回路系统、基本割集系统根树及其分类、最优树、最佳前缀码、波兰符号法、逆波兰符号法基本要