第十章树与有序树.ppt

《第十章树与有序树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章树与有序树10.1树的基本概念10.2连通图的生成树和带权连通图的最小生成树10.3有序树10.4前缀码和最优二分树家谱PeterGodfriedBettyAlbertMaryMarivinDorisJudyHalDeniseGregory一般假定在孩子是按年龄排序的,则这种树是有序的。语法树英语句子“Thebigelephantatethepeanut”可以图解如下图，称之为这个英语句子的语法树。有向树定义1一个有向图，若去掉边的方向，所得无向图是一棵树，则称这个有向图为有向树。(a)(b)例两个有向

2、树的例子。今后只讨论(b)这样的所谓的“根树”——有一个根的树。根树设T=(V,E)是一棵有向树，若仅有一个顶点的入度为0，其余的顶点的入度均为1，这样一棵有向树我们称为根树。入度为0的顶点称为树根，出度为0的顶点称为树叶，出度不为0的顶点称为分枝点。例abcdeabcde父亲、儿子、祖先、后代、兄弟设T=(V,E)是一棵根树。如果e=(v,u)∊E，称v是u的父亲，u是v的儿子。对v1,v2∊V，若存在一条从v1到v2的通路，则称v1是v2的祖先，v2是v1的后代。若(v0，v1)，(v0，v2)∊E，说v

3、1与v2是兄弟。abedinm子树设T=(V,E)是一棵根树。v0∊V，v0是中一个分支点,所谓以v0为根的子树是指T的一个子图T’，T’以v0和v0的全部的后代为顶点，以从v0出发的所有通路经过的边为边。以v0的一个儿子为根的子树称为v0的子树。abedinm例试回答问题哪个是树根?哪些是树叶?哪个是e的父亲?哪些是e的祖先?哪些是e的儿子?哪些是e的后代?哪些是e的兄弟?哪些是e的子树?acbedfhgilkjnm有序树定义2一棵根树，若每一个分枝点出发的边，分别标以整数1，2，⋯，k。则称这样的根树为有

4、序树。有序树可以说是各子树从左到右是有次序的树句子主语谓语形容词冠词名词Thebigelephantatethepeanut例例需要说明的是，一棵有序树的每个分枝点出发的边的标号并不是要求是连续的。一个分枝点出发的边，若被标上i，则称这条边是这个分枝点的i子树。如上图，一个分枝点出发的两条边被分别标上1，3，我们说这个分枝点没有第2子树。句子主语谓语形容词冠词名词Theelephantatethepeanut13m－分树、正则m－分树如果一棵有序树的每个分枝点最多有m个儿子，称这棵有序树为m－分树。若一棵m－

5、分树的每一个分枝点恰好有m个儿子，称这样的m－分树为正则m－分树。2－分树:左子树、右子树对于2－分树，它的每一个分枝点的第一个子树和第二子树又分别叫左子树和右子树。例单淘汰赛的正则2-分树定理9一棵正则m－分树的分枝点的个数为i，树叶的个数为t，则有(m-1)i=t-1证明：总共有i个分枝点，每个分枝点有m个儿子，故总的儿子数目为mi。而所有的儿子包括全部顶点减去一个根，即为i+t-1，所以有：mi=i+t-1即为（m-1)i=t-1。例5用带4个插座的接线板，连接19个灯到一个总插座上，问至少需要多少块接

6、线板。解：任何一个连接方法都是一棵4－分树，按定理9中公式，有(4-1)i≥19－1,所以i≥6树形图的高度、顶点的路长在一棵树形图中，一个顶点的路长规定为从树根到这个顶点的通路的长。一棵树形图的高度即为该树中最长路的长度。在一棵树形图中从树根到每一个顶点有且仅有唯一的一条通路。高为h的正则m－分树高为h的正则m－分树，最多有mh片树叶，而至少有m+(m-1)(h-1)片树叶。例求证一棵正则2－分树必有奇数个顶点。证明:假设一棵正则2－分树有i个分枝点、t个树叶。每个分枝点有2个儿子，故总的儿子数目为2i。而

7、所有的儿子包括全部顶点减去一个根，所以有：2i=i+t-1即为i=t-1。从而全部顶点数目为i+t=(t-1)+t=2t-1显然,它是一个奇数，结论得证明。例数学表达式的二分树(二叉树)以二叉树表示数学表达式的递归定义：若表达式=(第一表达式)(运算符)(第二表达式),则以左子树表示第一表达式以右子树表示第二表达式根结点的数据库存放运算符+*/cdab(a*b)+(c/d)++d+cab((a+b)+c)+d第十章树与有序树10.1树的基本概念10.2连通图的生成树和带权连通图的最小生成树10.3有序树10.

8、4前缀码和最优二分树