09离散数学课件资料.ppt

1、1/6/2023离散数学11/6/2023离散数学21/6/2023离散数学31/6/2023离散数学4树的等价定义定理1/6/2023离散数学5例：例：画出画出6 6阶所有非同构的无向树。阶所有非同构的无向树。(1)1，1，1，1，1，5(2)1，1，1，1，2，4(3)1，1，1，1，3，3(4)1，1，1，2，2，3 两种两种(5)1，1，2，2，2，2解：解：设设T是是6阶无向树，阶无向树，T的边数的边数m5 5，由握手定理可知，由握手定理可知，d(v)1010，且，且(T)11，(T)55。故。故T T的度数列必为以下情况之一：的度数列必为以下情况之一：1/6/2023离散数学61/

2、6/2023离散数学7：1/6/2023离散数学81/6/2023离散数学9推论推论1:推论推论2:定理1/6/2023离散数学101/6/2023离散数学11meee ,21maaa ,21maaa 21 i非环，若是环，则放弃非环，若是环，则放弃1/6/2023离散数学12abcdegf195141827168213ae12dcbgf7148531621:71218191/6/2023离散数学131/6/2023离散数学141/6/2023离散数学151/6/2023离散数学16r元树元树：每个分支点至多有：每个分支点至多有r个儿子；个儿子；r元有序树元有序树：r元树是有序的；元树是有序的

3、；r元正则树元正则树：每个分支点恰有：每个分支点恰有r个儿子；个儿子；r元正则有序树元正则有序树：r元正则树是有序的；元正则树是有序的；r元完全正则树元完全正则树：树叶层数均为树高的：树叶层数均为树高的r元正则树；元正则树；r元完全正则有序树元完全正则有序树：r元完全正则树是有序的。元完全正则树是有序的。分类分类：根据根树根据根树T中每个分支点儿子数以及是否有序：中每个分支点儿子数以及是否有序：1/6/2023离散数学171/6/2023离散数学18 tiiiWLWtW1)()(1/6/2023离散数学19例：下图所示的三棵二叉树例：下图所示的三棵二叉树T1,T2,T3都是带权为都是带权为2、

4、2、3、3、5的的二二叉树。叉树。W(T1)=22+22+33+53+32=38W(T2)=34+54+33+22+21=47W(T3)=33+33+52+22+22=36 1/6/2023离散数学20求最优树的算法求最优树的算法(Huffman算法算法)给定实数给定实数w1,w2,wt，设，设w1w2wt。连接权为连接权为w1,w2的两片树叶，得一个分支点，的两片树叶，得一个分支点，其权为其权为w1+w2。重复重复，直到形成，直到形成t-1 1个分支点、个分支点、t片树叶为止。片树叶为止。在在w1+w2,w3,wt中选出两个最小的权，连接它中选出两个最小的权，连接它们对应的顶点（不一定是树叶

5、），得新分支点及所们对应的顶点（不一定是树叶），得新分支点及所带的权。带的权。1/6/2023离散数学219例如例如:已知权值已知权值 W=5,6,2,9,7 5627527697671395271/6/2023离散数学2267139527952716671329000011110001101101111/6/2023离散数学23例：求带权为例：求带权为1、1、2、3、4、5的最优树。的最优树。1/6/2023离散数学24前缀前缀:设设=1 2 n-1 n是长度为是长度为n的符号串，称的符号串，称 其子串其子串 1,1 2,1 2 n-1分别为分别为 的长的长 度为度为1,2,n-1的的前缀前

6、缀。四、最佳前缀码四、最佳前缀码二元前缀码二元前缀码:若若 i(i=1,2,m)中只出现中只出现0 0与与1 1两个符号，两个符号，则称则称B为为二元前缀码二元前缀码。前缀码前缀码:设设B=1,2,m为一个符号串集合，若对为一个符号串集合，若对 于任意的于任意的 i,j B，i j，i,j互不为前缀，则互不为前缀，则 称称B为为前缀码前缀码。1/6/2023离散数学25四、最佳前缀码四、最佳前缀码(2)(2)如何产生二元前缀码？如何产生二元前缀码？定理定理:任何一棵二元正则树对应一个二元前缀码。任何一棵二元正则树对应一个二元前缀码。定理定理:任何一个二元前缀码对应一颗二元正则树。任何一个二元前

7、缀码对应一颗二元正则树。0，10，110，11111，11，101，00101，01，001，00000，11，011，0100，0101例：判断下列符号串集合是否是前缀码。例：判断下列符号串集合是否是前缀码。1/6/2023离散数学26方法：方法：用用HuffmanHuffman算法产生最佳前缀码。算法产生最佳前缀码。例、例、在通信中，八进制数字出现的频率如下：在通信中，八进制数字出现的频率如下：0 0：25%25%；1 1：20%20%；2 2：15%15%；3 3：10%10%4 4：10%10%；5 5：10%10%；6 6：5%5%；7 7：5%5%求传输它们的最佳前缀码？求传输它们

8、的最佳前缀码？求传输求传输1010n（n22）个按上述比例出现的八进制数字）个按上述比例出现的八进制数字需要多少个二进制数字？需要多少个二进制数字？若用等长码若用等长码(长为长为3)传输需要多少个二进制数字？传输需要多少个二进制数字？四、最佳前缀码四、最佳前缀码最佳前缀码：最佳前缀码：当要传输按着一定比例出现的符号串当要传输按着一定比例出现的符号串 时，需要寻找传输它们最省二进制数字时，需要寻找传输它们最省二进制数字 的前缀码，即最佳前缀码。的前缀码，即最佳前缀码。1/6/2023离散数学27例：以例：以100100乘各频率为权，并按小到大排列，得乘各频率为权，并按小到大排列，得w1=5,w2

9、=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25。产生的最优树如下。产生的最优树如下。0 01(25%)1 11(20%)2 001(15%)3 100(10%)4 101(10%)50001 (10%)6 00000 (5%)7 00001 (5%)传传100100个按比例出现的八进制数字所需二进制数字个按比例出现的八进制数字所需二进制数字个数个数W(T)=285)=285，所以传，所以传10n(n 2)个所用二进制数字个所用二进制数字应为应为2.85 10n。用等长码（长为用等长码（长为3 3）应该用）应该用3 10n个数字个数字,因此用最因此用最佳前缀码可节省

10、传递数字。佳前缀码可节省传递数字。1/6/2023离散数学28（1）由于在每一步选择两个最小的权的选法不唯一。由于在每一步选择两个最小的权的选法不唯一。（2）因为两个权对应的顶点所放左右位置不同。因为两个权对应的顶点所放左右位置不同。（3）画出的最优树可能不同，最佳前缀码并不唯一，画出的最优树可能不同，最佳前缀码并不唯一，但有一点是共同的，就是它们的权相等，即它们都应但有一点是共同的，就是它们的权相等，即它们都应该是最优树。该是最优树。四、最佳前缀码四、最佳前缀码1/6/2023离散数学29遍历遍历：对一棵根树的每个顶点访问且仅访问一次称为对一棵根树的每个顶点访问且仅访问一次称为遍遍历历一棵树

11、一棵树。中序遍历法：中序遍历法：b a(f d g)c e五、树的遍历五、树的遍历前序遍历法：前序遍历法：a b(c(d f g)e)后序遍历法：后序遍历法：b(f g d)e c)a 对对2 2元有序正则树的遍历方式：元有序正则树的遍历方式：先序遍历法：访问次序为：树根、左子树、右子树先序遍历法：访问次序为：树根、左子树、右子树 后序遍历法：访问次序为：左子树、右子树、树根后序遍历法：访问次序为：左子树、右子树、树根 中序遍历法：访问次序为：左子树、树根、右子树中序遍历法：访问次序为：左子树、树根、右子树 1/6/2023离散数学30用用2元有序正则树存放算式：元有序正则树存放算式：最高层次

12、的运算符放在树根上。最高层次的运算符放在树根上。依次将运算符放在根子树的根上。依次将运算符放在根子树的根上。参加运算的数放在树叶上，参加运算的数放在树叶上，规定：被除数、被减数放在左子树树叶上。规定：被除数、被减数放在左子树树叶上。五、树的遍历五、树的遍历1/6/2023离散数学31例：例：用二叉有序正则树表示算式：用二叉有序正则树表示算式：(b+(c+d)a)(e f)(g+h)(i j)五、树的遍历五、树的遍历1/6/2023离散数学32波兰符号法波兰符号法:按前序遍历法访问存放算式的二元有序按前序遍历法访问存放算式的二元有序正则树，其结果不加括号，规定每个运算符号与其正则树，其结果不加括号，规定每个运算符号与其后面紧邻两个数进行运算。后面紧邻两个数进行运算。前序遍历法的访问结果为前序遍历法的访问结果为:b+c d a e f +g h i j 1/6/2023离散数学33逆波兰符号法逆波兰符号法:按后序行遍法访问，规定每个运算符与按后序行遍法访问，规定每个运算符与前面紧邻两数运算。前面紧邻两数运算。后序行遍法的访问结果为后序行遍法的访问结果为:b c d+a e f g h+i j