二叉树的每个结点v至多有两棵子树.pptVIP

计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * * 计算机学院 * 主要内容 完全二叉树 Huffman算法 * 计算机学院 * 内容回顾 定义11.4 设T是一棵有向树，如果恰有一个结点的入度为0，其余所有结点的入度均为1，则称为根树或外向树。 入度为0的结点称为树根；出度为0的结点称为树叶；入度为1，出度大于0的结点称为内点；又将内点同树根统称为分支点。 如果恰有一个结点的出度为0，其余所有结点的出度均为1，则称为内向树。（如上例中的(d)) * 计算机学院 * m叉树 定义11.5 在根树T中，若每个分支点的出度至多为m，则称T为m叉树； 若每个分支点的出度都等于m，则称T为完全的m叉树； 若T的全部叶结点位于同一层次，则称T为正则m叉树； 二叉树的每个结点v至多有两棵子树，分别称为v的左子树和右子树。 * 计算机学院 * 定理11.5 若T是完全m叉树，其树叶数为t，分支点数为 i，则下式成立： （m-1）×i＝t-1 证明 由假设知，该树有i+t个结点。 由定理11.1知，该树的边数为i+t-1。 因为所有结点的出度之和等于边数（握手定理），所以根据完全的m叉树的定义知，有 m×i＝i+t-1 即 （m-1）×i＝t-1 这个定理实质上可以用每局有m个选手参加的单淘汰制比赛来说明。t个叶表示t个参赛的选手，i则表示必须安排的总的比赛局数．每一局由m个参赛者中产生一个优胜者，即淘汰（m-1）个选手，故比赛结果共淘汰（m-1）i个选手，最后剩下一个冠军，所以 (m-1)i+1=t。 * 计算机学院 * 例11.5 设有28盏电灯，拟公用一个电源插座，问需要多少块具有四插座的接线板? 解: 这个公用插座可以看成是正则四叉树的根，每个接线板看成是其它的分枝点，灯泡看成是叶，则问题就是求总的分枝点的数目。由定理11.5可以算得i = （28 -1）/3 = 9，因此，至少需要9块接线板才能达到目的。 * 计算机学院 * * 计算机学院 * 例11.6 解 用3个结点表示3个数，将表示3个数之和的结点作为它们的父结点。这样本问题可理解为求一个完全三叉树的分支点问题。把9个数看成树叶。由定理11.5知，有(3-1)i = 9-1，得i = 4。所以至少要执行4次加法指令。 假设有一台计算机，它有一条加法指令，可 计算3个数的和。如果要求9个数x1,x2,x3,x4,x5, x6,x7,x8,x9之和，问至少要执行几次加法指令？ x1 (a) x2 x3 x4 x5 x6 x7 x8 x9 x1 x2 x3 x4 x5 x6 x7 x8 x9 (b) * 计算机学院 * 把有序树转换为二叉树 从根开始，保留每个父亲同其最左边儿子的连线，撤销与别的儿子的连线。 兄弟间用从左向右的有向边连接。 按如下方法确定二叉树中结点的左儿子和右儿子：直接位于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子，依此类推。 反过来，我们也可以将二叉树还原为有序树。 * 计算机学院 * 例11.7 将下图a转化为一棵二叉树。 v10 v3 v4 (a) v1 v2 v11 v9 v5 v6 v7 v8 v10 v6 v3 v4 (b) v1 v2 v11 v9 v5 v7 v8 v10 v9 v4 v7 v6 v3 (c) v1 v2 v11 v5 v8 * 计算机学院 * 距离、层数、高 定义11.6 在根树中，从树根到任一结点v的道路长度，称为根到该结点的距离（也称为结点的层数）；称层数相同的结点在同一层上；所有结点的层数中最大的称为根树的高。 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 * 计算机学院 * *定理11.6 若完全二叉树有i个分支点，且各 分支点的道路长度之和为L，各树叶的道路长度 之和为J， 则 J＝L+2×i。 证明：对分支点数目i进行归纳。 当i = 1时，L = 0，J = 2，故J = L + 2i成立。 假设i = k时定理结论成立。 当i=k+1时，设在完全二叉树T中，v是一个道路长度为l的分枝点且其两个儿子v1和v2都是叶，则T–{v1,v2}是含k个分枝点的完全二叉树T’，它减少了二片长度为I+1的树叶和一个长度为I的分枝点。 由归纳假设J’=L’+2k， 比较T和T’=T–{v1,v2}，可得 J = J’+ 2（I + 1）-l = J’+l+2， L= L’+l，于是 J = L’+ 2