《树与有序树》ppt课件

1、第十章 树与有序树10.1 树的根本概念树的根本概念10.2 连通图的生成树和带权连通图的连通图的生成树和带权连通图的最小生成树最小生成树 10.3 有序树有序树10.4 前缀码和最优二分树前缀码和最优二分树 家谱PeterGodfriedBettyAlbertMaryMarivinDorisJudyHalDeniseGregory普通假定在孩子是按年龄排序的普通假定在孩子是按年龄排序的, 那么这种树是有序的。那么这种树是有序的。语法树语法树英语句子英语句子“The big elephant ate the peanut可以图解可以图解如以下图，称之为这个英语句子的语法树。如以下图，称之为这个

2、英语句子的语法树。Thebigelephantate冠词形容词名词动词冠词名词直接宾语主语谓语句子thepeanut有向树定义定义1 1 一个有向图，假设去掉边的方向，所得无向一个有向图，假设去掉边的方向，所得无向图是一棵树，那么称这个有向图为有向树。图是一棵树，那么称这个有向图为有向树。(a)(b)例例 两个有向树的例子。两个有向树的例子。今后只讨论今后只讨论(b)这样的所谓的这样的所谓的“根树根树有一个根的树。有一个根的树。根树根树设设T=(V,E)T=(V,E)是一棵有向树，假设仅有一个顶点的入度是一棵有向树，假设仅有一个顶点的入度为为0 0，其他的顶点的入度均为，其他的顶点的入度均为1

3、 1，这样一棵有向树我们，这样一棵有向树我们称为根树。称为根树。入度为入度为0 0的顶点称为树根，的顶点称为树根，出度为出度为0 0的顶点称为树叶，的顶点称为树叶，出度不为出度不为0 0的顶点称为分枝点。的顶点称为分枝点。 例例abcdeabcde父亲、儿子、祖先、后代、兄弟父亲、儿子、祖先、后代、兄弟设设T=(V,E)T=(V,E)是一棵根树。是一棵根树。假设假设e=(v,u) e=(v,u) E E，称，称v v是是u u的父的父亲，亲， u u是是v v的儿子。的儿子。对对v1,v2v1,v2 V V，假设存在一条从，假设存在一条从v1v1到到v2v2的通路，那么称的通路，那么称v1v1

4、是是 v2v2的祖先，的祖先，v2v2是是v1v1的后代。的后代。假设假设(v0(v0，v1)v1)，(v0(v0，v2) v2) E E ，说，说v1v1与与v2v2是兄弟。是兄弟。a ab be ed di in nm m子树设设T=(V,E)T=(V,E)是一棵根树。是一棵根树。v0v0 V V，v0v0是是 中一个分支点中一个分支点, , 所谓以所谓以v0v0为根的子树是指为根的子树是指T T的的一个子图一个子图T T ，T T 以以v0v0和和v0v0的全部的后代为顶点，以的全部的后代为顶点，以从从v0v0出发的一切通路经过的出发的一切通路经过的边为边。边为边。以以v0v0的一个儿子

5、为根的子树称的一个儿子为根的子树称为为v0v0的子树。的子树。a ab be ed di in nm m例例 试回答以下问题试回答以下问题l 哪个是树根哪个是树根? ? l 哪些是树叶哪些是树叶? ? l 哪个是哪个是e e的父亲的父亲? ? l 哪些是哪些是e e的祖先的祖先? ? l 哪些是哪些是e e的儿子的儿子? ? l 哪些是哪些是e e的后代的后代? ? l 哪些是哪些是e e的兄弟的兄弟? ?l 哪些是哪些是e e的子树的子树? ? a ac cb be ed df fh hg gi il lk kj jn nm m有序树定义定义2 一棵根树，假设每一个分枝点出发的边，一棵根树，

6、假设每一个分枝点出发的边， 分别标以整数分别标以整数1，2， ，k 。那么称这样的根树为有序树。那么称这样的根树为有序树。有序树可以说是各子树从左到右是有次序的树有序树可以说是各子树从左到右是有次序的树句子句子主语主语谓语谓语描画词描画词冠词冠词名词名词The big elephant ate the peanut例例例例需求阐明的是，一棵有序树的每个分枝点出发的边的需求阐明的是，一棵有序树的每个分枝点出发的边的标号并不是要求是延续的。一个分枝点出发的边，假标号并不是要求是延续的。一个分枝点出发的边，假设被标上设被标上i ，那么称这条边是这个分枝点的，那么称这条边是这个分枝点的 i子树。如子树

7、。如上图，一个分枝点出发的两条边被分别标上上图，一个分枝点出发的两条边被分别标上1，3，我，我们说这个分枝点没有第们说这个分枝点没有第2子树。子树。句子句子主语主语谓语谓语描画词描画词冠词冠词名词名词The elephant ate the peanut13m分树、正那么分树、正那么m分树分树假设一棵有序树的每个分枝点最多有假设一棵有序树的每个分枝点最多有 m m个儿个儿子，称这棵有序树为子，称这棵有序树为 m m分树。分树。假设一棵假设一棵 m m分树的每一个分枝点恰好有分树的每一个分枝点恰好有m m 个儿子，称这样的个儿子，称这样的 m m分树为正那么分树为正那么m m分树分树。2分树分树

8、: 左子树、右子树左子树、右子树对于对于2 2分树，它的每一个分枝点的第一个子树和第二分树，它的每一个分枝点的第一个子树和第二子树又分别叫左子树和右子树。子树又分别叫左子树和右子树。例例 单淘汰赛的正那么单淘汰赛的正那么2-分树分树 定理定理9 一棵正那么一棵正那么m m分树的分枝点的个数为分树的分枝点的个数为i i，树叶的个，树叶的个数为数为t t，那么有，那么有 (m-1)i=t-1 (m-1)i=t-1证明：总共有证明：总共有 i个分枝点，每个分枝点有个分枝点，每个分枝点有 m个儿子，个儿子，故总的儿子数目为故总的儿子数目为 mi 。而一切的儿子包括全。而一切的儿子包括全部顶点减去一个根

9、，即为部顶点减去一个根，即为 i+t-1，所以有：，所以有：mi=i+t-1即为即为 m-1)i=t-1。例5 用带用带4 4个插座的接线板，衔接个插座的接线板，衔接1919个灯到一个总插座上个灯到一个总插座上，问至少需求多少块接线板。，问至少需求多少块接线板。 解：任何一个衔接方法都是一棵解：任何一个衔接方法都是一棵4分树，分树， 按定理按定理9中公式，有中公式，有 (4-1)i 191, 所以所以 i6树形图的高度、顶点的路长树形图的高度、顶点的路长在一棵树形图中，在一棵树形图中，一个顶点的路长规定为从树根到这个顶点的通路的一个顶点的路长规定为从树根到这个顶点的通路的长。长。一棵树形图的高

10、度即为该树中最长路的长度。一棵树形图的高度即为该树中最长路的长度。在一棵树形图中从树根到每一个顶点有且仅有独一的在一棵树形图中从树根到每一个顶点有且仅有独一的一条通路。一条通路。高为高为h的正那么的正那么m分树分树 高为高为h h的正那么的正那么m m分树，分树，最多有最多有mhmh片树叶，而至少有片树叶，而至少有m+(m-1)(h-1)m+(m-1)(h-1)片树叶。片树叶。 例 求证一棵正那么2分树必有奇数个顶点。证明证明: 假设一棵正那么假设一棵正那么2分树有分树有 i个分枝点、个分枝点、t个树叶。个树叶。每个分枝点有每个分枝点有 2个儿子，故总的儿子数目为个儿子，故总的儿子数目为 2i

11、 。而一切的儿子包括全部顶点减去一个根，所以而一切的儿子包括全部顶点减去一个根，所以有：有：2i=i+t-1即为即为i=t-1。从而全部顶点数目为从而全部顶点数目为 i+t=(t-1)+t=2t-1显然显然, 它是一个奇数，结论得证明。它是一个奇数，结论得证明。例例 数学表达式的二分树数学表达式的二分树(二叉树二叉树)以二叉树表示数学表达式的递归定义：以二叉树表示数学表达式的递归定义：假设表达式假设表达式=(第一表达式第一表达式)(运算符运算符)(第二表达式第二表达式), 那么那么 以左子树表示第一表达式以左子树表示第一表达式 以右子树表示第二表达式以右子树表示第二表达式 根结点的数据库存放运算符根结点的数