7＿8根树及其应用.ppt

7-8 根树及其应用 前面我们讨论的树，都是一个无向图，下面我们讨论有向图的树。 定义7-8.1 如果一个有向图在不考虑边的方向时是一棵数，那么，这个有向图称为有向树。 定义7-8.2 一棵有向树，如果恰有一个结点的入度为0，其余所有结点的入度都为1，则称为根树。入度为0的结点称为根，出度为0的结点称为叶，出度不为0的结点称为分支点或内点。 例如图7-8.1(b)表示的是一棵根树，其中v1为根，v2，v4，v8，v9为分枝点，其余结点为叶。 在根树中，任意一个结点v的层次，就是从根到该结点的单向通路的长度。 在图7-8.1(b)中，有三个结点的层次为1，有五个结点的层次为2，有三个结点的层次为3。 从根树的结构可以看出，树中每一个结点可以看作是原来树中的某一棵子树的根，由此可知，根树亦可递归定义为： 定义7-8.3 根树包括一个或多个结点，这些结点中某一个称为根，其它所有结点被分成有限个子根树。 这个定义把n个结点的根树用结点数少于n的根树来定义，最后得到每一棵都是一个结点的根树，它就是原来那棵树的树叶。 对于一棵根树，如果用图形来表示，可以有树根在下或树根在上的两种画法。 图7-8.2(a)是根树自然表示法，即树从它的树根向上生长。图7-8.2(b)和(c)都是由树根往下生长，它们是同构图，其差别仅在于每一层上的结点从左到右出现的次序不同，为此今后要用明确的方式，指明根树中的结点或边的次序，这种树称为有序树。 设a是根树中的一个分枝点，若从a到b有一条边，即a＜b，则结点a称为结点b的“父亲”，而结点b称为结点a的“儿子”。假若a＜c，则结点a称为结点c的“祖先”，而结点c称为结点a的“后裔”。同一个分枝点的“儿子”称为“兄弟”。 m叉树是一种特殊的根树，在m=2时，称为二叉树，它在计算机科学中有着广泛的应用。 定义7-8.4 在根树中，若每一个结点的出度小于或等于m，则这棵树称为m叉树。如果每一个结点的出度恰好等于m或零，则这棵树称为完全m叉树。若所有的树叶层次相同，则这棵树称为正则m叉树，若m=2时，称为二叉树。 有许多实际问题可用二叉树或m叉树来表示。 例如M和E两人进行网球比赛，如果一人连胜两盘或共胜三盘就获胜，比赛结束。图7-8.3表示了比赛可能进行的各种情况，它有十片树叶，从根到树叶的每一条路对应比赛可能发生的一种情况，即：MM，MEMM，MEMEM，MEMEE，MEE，EMM，EMEMM，EMEME，EMEE，EE。 我们要指出，任何一棵有序树都可以改写为对应的二叉树。如图7-8.4(a)中的m叉树可用下述方法改为二叉树： ⑴除了最左边的分枝点外，删去所有从每一结点长出的分枝。在同一层次中，兄弟结点间用从左到右的有向边连接，如图7-8.4(b)所示。 ⑵选定二叉树的左儿子和右儿子如下：直接处于给定结点下面的结点，作为左儿子，对于同一水平线上给定结点右邻结点，作为右儿子，以此类推，如图7-8.4(c)所示。 用二叉树表示有序根树的方法，可以推广到有序森林上去,如图7-8.5所示。 在树的实际应用中，我们经常研究完全m叉树。 定理7-8.1 设有完全m叉树，其树叶数为t，分枝点数为i，则(m-1)i=t-1。 证明 若把m叉树当作是每局有m位选手参加比赛的单淘汰赛计划表，树叶数为t表示参加比赛的选手数，分枝点数为 i 表示比赛的局数， 因为每局比赛将淘汰(m-1)位选手，比赛的结果共淘汰(m-1) i位选手，最后剩下一个冠军， 因此(m-1)i+1=t 即(m-1) i =t-1。 例1. 设有28盏灯，拟共用一个电源插座，问需用多少块具有四种插座的接线板。 解 将四叉树每个分枝点看作是具有四插座的接线板，树叶看作电灯，则(4-1)i=28-1, i=9，所以需要九块具有四插座的接线板。 例2 设有一台计算机，它有一条加法指令，可计算三个数的和，如果要计算九个数的和，至少要执行几次加法命令。 解 若把九个数看作是完全三叉树的九片树叶，则有(3-1)i=9-1, i=4，所以，需要执行四次加法指令。 在计算机的应用中，还常常考虑二叉树的通路长度问题。 定义7-8.5 在根树中，一个结点的通路长度，就是从树根到此结点的通路中的边数。我们把分枝点的通路长度称作内部通路长度，树叶的通路长度称作外部通路长度。 定理7-8.2 若完全二叉树有n个分枝点，且内部通路长度总和为I，外部通路长度总和为E，则 E=I+2n 证明 对分枝点数目n进行归纳。 当n=1时，E=2，I=0，故E=I+2n成立。 假设n=k-1时成立，即E’=I’+2(k-1)。 当n=k时，若删除去一个分枝点v，该分枝点与根的通路长度为l，且v的两个儿子是树叶，得到新树T’。将T’与原树比较，它减少了两片长度为l+1的树叶和一个长度为l的