1.2离散数学1资料ppt课件

1、树的等价定义定理例：画出例：画出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 T是是6 6阶无向树，阶无向树，T T的边数的边数m m5 5，由握手定理可知，由握手定理可知，d(v)d(v)1010，且，且(T)1(T)1，(T)5(T)5。故。故T T的度数列必为以下情况之一：的度数列必为以下情况之一：推论推论1: G为为n阶阶m条边的无向连通图，则条边的无向连通图，则mn1。 (要把要把n个顶点联系起来至少需要个

2、顶点联系起来至少需要n-1条边条边) 推论推论2 : 设设G是是n阶阶m条边的无向连通图，条边的无向连通图，T为为G的生的生成树，则成树，则T的余树中含有的余树中含有m-n+1条边即条边即T有有m-n+1条弦）。条弦）。定理meee ,21maaa ,21maaa 21abcdegf195141827168213ae12dcbgf71485316217121819r元树：每个分支点至多有元树：每个分支点至多有r个儿子；个儿子；r元有序树：元有序树：r元树是有序的；元树是有序的；r元正则树：每个分支点恰有元正则树：每个分支点恰有r个儿子；个儿子；r元正则有序树：元正则有序树：r元正则树是有序的；

3、元正则树是有序的；r元完全正则树：树叶层数均为树高的元完全正则树：树叶层数均为树高的r元正则树；元正则树；r元完全正则有序树：元完全正则有序树：r元完全正则树是有序的。元完全正则树是有序的。分类：根据根树分类：根据根树T中每个分支点儿子数以及是否有序：中每个分支点儿子数以及是否有序： tiiiWLWtW1)()(例：下图所示的三棵二叉树例：下图所示的三棵二叉树T1,T2,T3T1,T2,T3都是带权为都是带权为2 2、2 2、3 3、3 3、5 5的二叉树。的二叉树。 W(T1)=22+22+33+53+32=38W(T2)=34+54+33+22+21=47W(T3)=33+33+52+22

4、+22=36 求最优树的算法求最优树的算法(Huffman(Huffman算法算法) )给定实数给定实数w1,w2,wtw1,w2,wt，设，设w1w2wtw1w2wt。 连接权为连接权为w1, w2w1, w2的两片树叶，得一个分支的两片树叶，得一个分支点，其权为点，其权为w1+w2w1+w2。 反复，直到形成反复，直到形成t-1t-1个分支点、个分支点、t t片树叶为止。片树叶为止。 在在w1+w2, w3, , wtw1+w2, w3, , wt中选出两个最小的权，连中选出两个最小的权，连接它们对应的顶点不一定是树叶），得新分支点接它们对应的顶点不一定是树叶），得新分支点及所带的权。及所

5、带的权。9例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 W= 5, 6, 2, 9, 7 5627527697671395276713952795271667132900001111000110110111例：求带权为例：求带权为1 1、1 1、2 2、3 3、4 4、5 5的最优树。的最优树。前缀前缀: :设设= =1 122n-1n-1n n是长度为是长度为n n的符号的符号串，称串，称 其子串其子串1,1,1 12,2,1 122n-1n-1分分别为别为的长的长 度为度为1,2, ,n-11,2, ,n-1的前缀。的前缀。 二元前缀码二元前缀码: :假设假设i (i

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

7、一颗二元正则树。0，10，110，11111，11，101，00101，01，001，00000，11，011，0100，0101例：判断下列符号串集合是否是前缀码。例：判断下列符号串集合是否是前缀码。方法：用方法：用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、10n10nn2n2个按上述比例出现的八进制数个按上述比例出现的八进制数字需要多少个二进制数字？字需要多少个二进制数字？ 若用等长码若用等长码( (长为长为3)3)传输需要多少个二进制数字？传输需要多少个二进制数字？最佳前缀码：当要传输按着一定比例出现的符号串最佳前缀码：当要传输按着一定比例出现的符号串 时，需要寻找传输它们最省二进制数字时，需要寻找传输它们最省二进制数字 的前缀码，即最佳前缀码。的前缀码，即最佳前缀码。例：以例：以100100乘各频率为权，并按小到大排列，得乘各频率为权，并按小到大排列，得w1=5,w2=5, w3=10, w4=10, w5=10, w6=15, w7=20

9、, w1=5,w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25w8=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)=285W(T)=285，所以传，所以传10n(n10n(n2)2)个所用二进制数字个所用二进制数字应为应为2.852.85 10n10n。用等长

10、码长为3应该用310n个数字,因此用最佳前缀码可节省传递数字。（1由于在每一步选择两个最小的权的选法不唯一。由于在每一步选择两个最小的权的选法不唯一。（2因为两个权对应的顶点所放左右位置不同。因为两个权对应的顶点所放左右位置不同。（3画出的最优树可能不同，最佳前缀码并不唯一，画出的最优树可能不同，最佳前缀码并不唯一，但有一点是共同的，就是它们的权相等，即它们都应但有一点是共同的，就是它们的权相等，即它们都应该是最优树。该是最优树。遍历：对一棵根树的每个顶点访问且仅访问一次称为遍遍历：对一棵根树的每个顶点访问且仅访问一次称为遍历一棵树。历一棵树。中序遍历法：中序遍历法：b a (f d g) b

11、 a (f d g) c ec e五、树的遍历五、树的遍历前序遍历法：前序遍历法：a b (c (d f a b (c (d f g) e)g) e)后序遍历法：后序遍历法：b (f g d) e b (f g d) e c) a c) a 对对2 2元有序正则树的遍历方式：元有序正则树的遍历方式： 先序遍历法：访问次序为：树根、左子树、右子树先序遍历法：访问次序为：树根、左子树、右子树 后序遍历法：访问次序为：左子树、右子树、树根后序遍历法：访问次序为：左子树、右子树、树根 中序遍历法：访问次序为：左子树、树根、右子树中序遍历法：访问次序为：左子树、树根、右子树 用用2 2元有序正则树存放算

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