32.二叉树与最优二叉树

《32.二叉树与最优二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二叉树与最优二叉树1教师：田检2教师：田检有向树与根树的定义有向树:基图为无向树的有向图根树:有一个顶点入度为0,其余的入度均为1的非平凡的有向树树根:有向树中入度为0的顶点树叶:有向树中入度为1,出度为0的顶点内点:有向树中入度为1,出度大于0的顶点分支点:树根与内点的总称3教师：田检v1的层次为０，v2、v3的层次为１，其余结点的层次均为２。树高2层。4教师：田检m叉树在树的实际应用中，我们经常研究完全m叉树。定义在根树中，若结点的最大出度等于m，则称这棵树为m叉树。如果每个结点的出度恰好等于０或m，则称这棵树为完全m叉树。二叉树(binarytree)的每个结点v至多有

2、两棵子树，分别称为v的左子树和右子树。5教师：田检图7.7.36教师：田检图7.7.4【例7.7.1】甲、乙两人进行球赛，规定三局两胜。图7.7.4表示了比赛可能出现的各种情况（图中结点标甲者表示甲胜，标乙者表示乙胜），这是一棵完全二叉树。7教师：田检定理7.7.1在完全m叉树中，若树叶数为t，分枝点数为i，则(m-1)i＝t-１证明:由假设知，该树有i+t个结点，所以，该树边数为i+t-１。因为所有结点出度之和等于边数,所以根据完全m叉树的定义知，mi＝i+t-１即(m-1)i＝t-１8教师：田检【例7.7.2】假设有一台计算机，它有一条加法指令，可计算3个数之和。如果要

3、求9个数x1，x2，…，x9之和，问至少要执行几次加法指令？解:用3个结点表示3个数，把9个数看成树叶，将表示3数之和的结点作为它们的父亲结点。这样本问题可理解为求一个完全三叉树的分枝点的个数问题。9教师：田检由定理7.7.1知，有(３-１)i＝９-１得i＝４所以要执行4次加法指令。图7.7.5表示了两种可能的顺序。图7.6.510教师：田检【例7.7.3】设有28盏灯，拟公用一个电源，则至少需要多少个4插头的接线板?解:把28盏灯看成树叶，将4插头的接线板看成分枝点,这样本问题可理解为求一个完全四叉树的分枝点的个数i的问题。由定理7.7.1知，有(4-１)i＝28-1得i＝

4、9所以至少需要9个4插头的接线板。11教师：田检【例7.7.4】8枚硬币问题。若有8枚硬币a，b，c，d，e，f，g，h，其中7枚重量相等，只有1枚稍轻。现要求以天平为工具，用最少的比较次数挑出轻币来。解:可用图7.7.6所示的树表示判断过程。从图中可知，只需称2次即可挑出轻币。这种用于描述判断过程的树叫判定树。12教师：田检在所有的m叉树中，二叉树居重要地位，对计算机来说，二叉树最容易处理，因此常将有序树转化为二叉树，步骤如下：（1）对于每个顶点只保留左儿子。（2）兄弟间从左到右连接。（3）对于每个分支点，保留的左儿子仍做左儿子，右边邻接的顶点做作为兄弟的右儿子。13教师：

5、田检例如，图（a）是棵有序树，图（b）是表示图（a）的一棵二叉树，图（c）是相应的二叉位置树。567891012340(a)14教师：田检15教师：田检16教师：田检17教师：田检18教师：田检19教师：田检20教师：田检21教师：田检22教师：田检前缀码的设计——最优二叉树的应用23教师：田检24教师：田检{000，001，01，10，11}{000，001，01，1}25教师：田检例：假设在通讯中，十进制数字出现的频率是0：20%；1：15%；2：10%；3：10%；4：10%；5：5%；6：10%；7：5%；8：10%；9：5%（1）求传输它们的最佳前缀码。（2）用最佳

6、前缀码传输10000个按上述频率出现的数字需要多少个二进制码？（3）它比用等长的二进制码传输10000个数字节省多少个二进制码？26教师：田检解（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的最优二叉树。27教师：田检图9.2.11w0=20；w1=15；w2=10；w3=10；w4=10；w5=5；w6=10；w7=5；w8=10；w9=5。28教师：田检即最佳前缀码为：{10，010，111，11

7、0，001，0111，0001，0110，00000，00001}。(2)(2×20%+3×(10%+15%+10%+10%)+4×(5%+10%+10%)+5×(5%+5%))×10000=32500即传输10000个数字需32500个二进制码。（3）因为用等长码传输10个数字码长为4，即用等长的码传10000个数字需40000个二进制码，故用最佳前缀码传节省了7500个二进制码。29教师：田检0123456730%20％15%10％10％5%5%5％012345670111001101000000