《二叉树及其应用》ppt课件
58页1、二叉树及其应用,雅礼 朱全民,二叉树,二叉树是一种特殊的树型结构,它的特点是每个节点至多只有两个子节点。 二叉树每个节点的子树有左右之分,其次序不能任意颠倒。 二叉树也有特殊形式,例如满二叉树、完全二叉树等。 例如右图就是一棵二叉树,并且是一棵完全二叉树。,二叉树的存储结构,常用的存储结构 type bitree=node node=record data :datatype; lchild,rchild:bitree; end;,二叉树的遍历,遍历( 先序遍历, 中序遍历, 后序遍历) Proc preorder(bt:bitree); if btNil then visit(bt) preorder(bt.lchild); preorder(bt.rchild); endP,二叉树的性质,在二叉树的第i层上最多有2i-1个结点 深度为K的二叉树最多有2k-1个结点 在二叉树中,叶子结点的总数总比为度数为2的结点多1 有n个结点的完全二叉树的结点按层序编号,则对任意一结点i,有 (1)如果i=1,则结点i是二查树的根,无双亲;如果i1,则双亲是i/2 (2)如果2in,则结点i无左孩
2、子,否则左孩子为2i (3)如果2i+1n,则结点i无右孩子,否则右孩子为2i+1,树、森林转化为二叉树,用“孩子兄弟表示法”可以将任意一棵树转化为二叉树的形式 森林转化为二叉树 如果F=T1, T2, ,Tm是森林,则可按如下规则转化为一棵二叉树。 1)若F为空,即m=0,则B为空树 2)若F非空,即m0,则B的根root即为森林中第一棵树的根root(T1),B的左子树为从T1中子树森林F1=T11, T12, ,T1i转换而成的二叉树;其右子树Rb 是从森林F=T2, ,Tm中转换出来的二叉树,树的儿子兄弟表示法,在一棵树中,拥有同一个父结点的结点互称为兄弟。我们不妨假设树中每个结点的子结点是有序的(就像二叉树一样),则我们可以将一棵树这样转化成二叉树: 二叉树中每个结点对应原树的每个结点 对于二叉树中的某个结点 它的左子结点对应原树中该结点的第一个子结点; 它的右子结点对应原树中该结点的下一个兄弟。,转化后的树,树的儿子兄弟表示法,这样我们可以类似于二叉树的链式结构写出树的儿子兄弟表示法的存储结构: TYPE tree = node; node = record data :
3、datatype; parent, child, brother : tree; / 分别记录父亲、第一个儿子、下一个兄弟 end;,树的儿子兄弟表示法,给定m个实数w1, w2, wm,(m=2) ,要求一个具有m个外部节点的扩充二叉树,每个外部ki节点有一个wi与之对应,作为它的权,使得带权外部路径长度 最小,其中li是从根到外部节点的路径长度。,最优二叉树(哈夫曼树),算法,1.构造m个只有1个节点的树 2.找两个最小的权 3.以这两个节点为左右儿子构造一个二叉树,并将该数的根节点权之为左右儿子权值之和 4.继续第二步,直到剩下一棵树为止,讨论,最优k叉树就是指在一个节点最多可以有k个叶子节点的时候,假设有n(n=k)个权值w1,w2,.wn,试构造出一棵有个叶子节点的k叉树。每个叶子节点有一个不同的权值i。其中树的带权路径长度最小的那棵树叫做最优k叉树。 怎么构造?,分析,最优k叉树必须具备的性质: 每个节点如果不是叶子节点,那么一定有k个儿子节点。 权值大的节点不能在比权值小的节点下方。就是权值大的节点到树根的长度要小于等于权值小的节点到树根的长度。,算法,根据给定的n个权值
4、w1,w2,wn构成n棵k叉树的森林F=T1,T2,Tn,其中每棵k叉树Ti中都只有一个权值为wi的根结点,其左右子树均空。 在森林F中选出k棵根结点权值最小的树(当这样的树不止k棵树时,可以从中任选k棵),将这k棵树合并成一棵新树,为了保证新树仍是k叉树,需要增加一个新结点作为新树的根,并将所选的k棵树的根分别作为新根的左右孩子,将这k个孩子的权值之和作为新树根的权值。 对新的森林F重复(2),直到森林F中只剩下一棵树为止。这棵树便是最优k叉树。,反例,假设k=3,当n=5时,这样做是对的。但是当n=4时,用刚才的方法得到的“最优3叉树”,但是,明显右图的那颗树会比左图的那颗树优。,分析原因,错误的原因:主要是左边的这棵树它并没有排满。可以把第3层的一个节点拉到第2层去,而这样做肯定会让WPL更小。 那么肯定要让第一次合并的时候,少合并几个点,后面的操作就和上面所说得算法一样。并且让最后一次合并能合并n棵树。从而让上面排满。 那么第一次要合并多少个点呢? 首先每次合并会让树的总数减少k-1棵,而最后还有n棵。那么完成了第一次合并后,剩下的树的个数正好模k-1后等于1。那么第一次合并的
《《二叉树及其应用》ppt课件》由会员tian****1990分享,可在线阅读,更多相关《《二叉树及其应用》ppt课件》请在金锄头文库上搜索。
2018-2019学年八年级历史上册 第3单元 新民主主义革命的兴起 第12课 国民革命导学案北师大版
2018-2019学年八年级历史上册 第六单元 中华民族的抗日战争 第21课 敌后战场的抗战导学案(新人教版
2018-2019学年八年级历史上册 第1单元 民族危机与晚晴时期的救亡运动 第1课 鸦片战争导学案2北师大版
2018-2019学年八年级历史上册 第2单元 辛亥革命与中华民国的建立 第8课 辛亥革命导学案北师大版
2018-2019学年八年级历史上册 第六单元 中华民族的抗日战争 第20课 正面战场的抗战导学案(新人教版
2018-2019学年八年级历史上册 第2单元 辛亥革命与民族觉醒 第10课 新文化运动导学案华东师大版
2018-2019学年八年级历史上册 第2单元 辛亥革命与民族觉醒 第8课 袁世凯称帝与军阀混战导学案2华东师大版
2018-2019学年八年级历史上册 第4单元 中华民族的抗日战争 第14课 民族危机的空前严重导学案华东师大版
2018-2019学年八年级历史上册 第五单元 从国共合作到国共对峙 第17课 中国工农红军长征导学案(新人教版
2018-2019学年八年级历史上册 第1单元 民族危机与晚晴时期的救亡运动 第5课 中日甲午战争导学案1北师大版
2018-2019学年八年级历史上册 第2单元 辛亥革命与民族觉醒 第8课 袁世凯称帝与军阀混战导学案1华东师大版
2018-2019学年八年级历史上册 第1单元 民族危机与晚晴时期的救亡运动 第5课 中日甲午战争导学案2北师大版
2018-2019学年八年级历史上册 第1单元 民族危机与晚晴时期的救亡运动 第1课 鸦片战争导学案1北师大版
2018-2019学年八年级历史上册 第2单元 辛亥革命与中华民国的建立 第10课 新文化运动导学案北师大版
2018-2019学年八年级历史上册 第1单元 民族危机与晚晴时期的救亡运动导学案北师大版
2018-2019学年八年级物理上册 第二章 第1节 声音的产生与传播导学案 (新版)新人教版
2018-2019学年八年级地理上册 第四章 第三节 工业的分布与发展(第1课时)学案(新版)新人教版
2018-2019学年八年级物理上册 第二章 第2节 声音的特性导学案 (新版)新人教版
2018-2019学年八年级地理上册 3.3 中国的水资源教学案(新版)湘教版
2018-2019学年八年级物理上册 第三章 第3节 汽化和液化(第1课时 汽化)导学案 (新版)新人教版
2024-05-02 431页
2024-05-02 790页
2024-04-11 25页
2024-04-11 37页
2024-04-11 28页
2024-04-11 31页
2024-04-11 36页
2024-04-11 29页
2024-04-11 22页
2024-04-11 27页