叉树与最优二叉树.ppt

教师：田检,1,二叉树与最优二叉树,教师：田检,2,3,有向树与根树的定义,有向树: 基图为无向树的有向图 根树: 有一个顶点入度为0, 其余的入度均为1的 非平凡的有向树 树根: 有向树中入度为0的顶点 树叶: 有向树中入度为1, 出度为0的顶点 内点: 有向树中入度为1, 出度大于0的顶点 分支点: 树根与内点的总称,教师：田检,4,v1的层次为， v2、 v3的层次为， 其余结点 的层次均为。树高2层。,教师：田检,5,m叉树 在树的实际应用中， 我们经常研究完全m 叉树。 定义 在根树中， 若结点的最大出度等于m， 则称这棵树为m叉树。 如果每个结点的出度恰好等于或m， 则称这棵树为完全m叉树。 二叉树(binary tree )的每个结点v 至多有两棵子树， 分别称为v的左子树和右子树。,教师：田检,6,图 7.7.3,教师：田检,7,图7.7.4,【例7.7.1】甲、 乙两人进行球赛， 规定三局两胜。 图7.7.4表示了比赛可能出现的各种情况（图中结点标甲者表示甲胜， 标乙者表示乙胜）， 这是一棵完全二叉树。,教师：田检,8,定理7.7.1 在完全m叉树中， 若树叶数为 t， 分枝点数为 i， 则 (m-1)it- 证明: 由假设知， 该树有 i+t 个结点， 所以， 该树边数为 i+t -。 因为所有结点出度之和等于边数,所以根据完全 m叉树的定义知， mi i+t - 即 (m-1)it-,教师：田检,9,【例7.7.2】假设有一台计算机， 它有一条加法指令， 可计算 3 个数之和。 如果要求 9 个数x1， x2， ， x9之和， 问至少要执行几次加法指令？ 解: 用 3 个结点表示 3 个数， 把 9 个数看成树叶， 将表示 3 数之和的结点作为它们的父亲结点。 这样本问题可理解为求一个完全三叉树的分枝点的个数问题。,教师：田检,10,由定理7.7.1知， 有 (-)i- 得 i 所以要执行 4 次加法指令。 图7.7.5表示了两种可能的顺序。,图 7.6.5,教师：田检,11,【例7.7.3】设有28盏灯，拟公用一个电源，则至少需要多少个4插头的接线板 ? 解:把 28盏灯看成树叶， 将4插头的接线板看成分枝点, 这样本问题可理解为求一个完全四叉树的分枝点的个数 i的问题。 由定理7.7.1知， 有 (4-)i28-1 得 i9 所以至少需要9个4插头的接线板 。,教师：田检,12,【例7.7.4】 8 枚硬币问题。 若有 8 枚硬币a， b， c， d， e， f， g， h， 其中 7 枚重量相等， 只有 1 枚稍轻。 现要求以天平为工具， 用最少的比较次数挑出轻币来。 解: 可用图7.7.6所示的树表示判断过程。 从图中可知， 只需称 2 次即可挑出轻币。 这种用于描述判断过程的树叫判定树。,教师：田检,13,在所有的m 叉树中，二叉树居重要地位，对计 算机来说，二叉树最容易处理，因此常将有序树 转化为二叉树，步骤如下：,（1）对于每个顶点只保留左儿子。 （2）兄弟间从左到右连接。 （3）对于每个分支点，保留的左儿子仍做左儿子，右边邻接的顶点做作为兄弟的右儿子。,教师：田检,14,例如，图（a）是棵有序树，图（b）是表示图（a）的一棵二叉树，图（c）是相应的二叉位置树。,教师：田检,15,教师：田检,16,教师：田检,17,教师：田检,18,教师：田检,19,教师：田检,20,教师：田检,21,教师：田检,22,教师：田检,23,前 缀 码 的 设 计,最优二叉树的应用,教师：田检,24,教师：田检,25,000，001，01，10，11,000，001，01，1,教师：田检,26,例： 假设在通讯中，十进制数字出现的频率是 0：20%； 1：15%； 2：10%； 3：10%； 4：10%； 5：5%； 6：10%； 7：5%； 8：10%； 9：5% （1）求传输它们的最佳前缀码。 （2）用最佳前缀码传输10000个按上述频率出现的数字需要多少个二进制码？ （3）它比用等长的二进制码传输10000个数字节省多少个二进制码？,教师：田检,27,解 （1）令i对应树叶权为wi，wi=100i，则 w0=20；w1=15； w2=10；w3=10； w4=10；w5=5； w6=10；w7=5； w8=10；w9=5。 构造一棵带权5,5,5,10,10,10,10,10,15, 20的最优二叉树。,教师：田检,28,图 9.2.11,w0=20；,w1=15；,w2=10；,w3=10；,w4=10；,w5=5；,w6=10；,w7=5；,w8=10；,w9=5。,教师：田检,29,即最佳前缀码为：10，010，111，110，001，0111，0001，0110，00000，00001。,(2) (220%+3(10%+15%+10%+10%)+4(5%+10%+10%)+5(5%+5%)10000=32500 即传输10000个数字需32500