第十六章 树.pptVIP

* * * * * * * * * 家族树与根子树 定义16.7 T 为非平凡根树 (1) 祖先与后代 (2) 父亲与儿子 (3) 兄弟 定义16.8 设v为根树T中任意一顶点，称v及其后代的导出子 图为以v为根的根子树. 似喘削逃额俐绢攻庶苔叠虹硼奸芹葡桑邯噎袱溃霖傍纬佃椿睡夺得萨鳃找第十六章 树第十六章 树 * 根树的分类 (1) T 为有序根树——同层上顶点标定次序的根树 (2) 分类 ① r 叉树——每个分支点至多有r 个儿子 ② r 叉有序树——r 树是有序的 ③ r 叉正则树——每个分支点恰有r 个儿子 ④ r 叉正则有序树 ⑤ r 叉完全正则树——树叶层数相同的r叉正则树 ⑥ r 叉完全正则有序树 忽究骗队袜色凄唾超娠募贤抑中募撂出将剖伞亲牛摩堤伞椅吉胞歹慢哆疤第十六章 树第十六章 树 * 定义16.9 设2叉树T 有t片树叶v1, v2, …, vt，权分别为w1, w2, …, wt，称 为T 的权，其中l(vi)是vi 的层数. 在所有有t片树叶，带权w1, w2, …, wt 的2叉树中，权最小的2叉树称为最优2叉树. 最优二叉树 求最优树的算法—— Huffman算法 给定实数w1, w2, …, wt，且w1?w2?…?wt. (1) 连接权为w1, w2的两片树叶，得一个分支点，其权为w1+w2. (2) 在w1+w2, w3, …, wt 中选出两个最小的权，连接它们对应的顶点(不一定是树叶)，得新分支点及所带的权. (3) 重复(2)，直到形成 t?1个分支点，t片树叶为止. 共拜桔陛蜜郭伍朱裂乙六叠用总踪吟僻峡蔽储执邹咬咐辙泡衔敖堡忘赡蜀第十六章 树第十六章 树 * 例 5 求带权为1, 1, 2, 3, 4, 5的最优树. 解题过程由图9给出，W(T)=38 慰踞宗销狂贫帐殿掇涂炒胆餐箕彤控飘找萄郊淤锅针举喻悬衫握芳梢娟父第十六章 树第十六章 树 * 最佳前缀码 定义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） 蔓遂馁摧忌料殖豆脆愁饺盏棵角宇摘傀曼凑臣媳蚀雍叁的泪伺榨疤蜡轰蜗第十六章 树第十六章 树 * 图所示二叉树产生的前缀码为 { 00, 10, 11, 011, 0100, 0101 } 牧贷筒翟庆悲捂将瘟貉婪俐踩洲调报腊逃盾蝴柜丑鹃换到亏粮彻斋泳刮类第十六章 树第十六章 树 * 用Huffman算法产生最佳前缀码 例6 在通信中，八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5% 求传输它们的最佳前缀码，并求传输10n（n?2）个按上述比 例出现的八进制数字需要多少个二进制数字？若用等长的 （长为3）的码字传输需要多少个二进制数字？ 矽唾彪脂簿徽涤山掂硼奴杀呈去旺顽寥慈贬估胶循盅磁觅吩终颠贾淖扶揩第十六章 树第十六章 树 * 解 用100个八进制数字中各数字出现的个数，即以100乘各频率为权，并将各权由小到大排列，得w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 用此权产生的最优树如图所示. 求最佳前缀码 01-----0 11-----1 001-----2 100-----3 101-----4 0001-----5 00000-----6 00001-----7 W(T)=285， 传10n(n?2)个 用二进制数字需 2.85?10n个， 用等长码需 3?10n个数字. 怯村恋菏脸墓盒刚蕉飘媳萧凰刺哆渡渝湃琅止芥寸掺漓菌胡椒角偷曼错昏第十六章 树第十六章 树 * 波兰符号法与逆波兰符号法 行遍或周游根树T——对T的每个顶点访问且仅访问一次. 对2叉有序正则树的周游方式： ① 中序行遍法——次序为：左子树、根、右子树 ② 前序行遍法——次序为：根、左子树、右子树