23根树及其应用

《23根树及其应用》由会员分享，可在线阅读，更多相关《23根树及其应用（18页珍藏版）》请在装配图网上搜索。

1、7-8 7-8 根树及其应用根树及其应用一、根树一、根树1、有向树、有向树 如果一个有向图在不考虑边的方向时如果一个有向图在不考虑边的方向时是一棵树，那么，该有向图称为是一棵树，那么，该有向图称为。2、根树、根树 一棵有向树一棵有向树,如果恰有一个如果恰有一个结点的入度为结点的入度为0，其余所有结点的入度都为，其余所有结点的入度都为1,则称为则称为(rooted tree)。入度为。入度为0的结点称的结点称为为T的的。出度为。出度为0的结点称为的结点称为树叶树叶，出度，出度不为不为0的结点称为的结点称为分支点分支点或或内点内点。根树的画法有：根树的画法有：树根在下，向上生长；树根在下，向上生长

2、；树根在上，向下生长。树根在上，向下生长。习惯把有向树的根画在最上方，边的箭头全指习惯把有向树的根画在最上方，边的箭头全指向下，则可以省略全部箭头，树根到一个结点的有向下，则可以省略全部箭头，树根到一个结点的有向通路的长度称为该点的层数。所有结点的最大层向通路的长度称为该点的层数。所有结点的最大层数称为树高。数称为树高。3、子树、子树 定义定义7-8.3：任一结点：任一结点v及其后代导出的子图及其后代导出的子图称为根树的子树。称为根树的子树。根树包含一个或多个结点根树包含一个或多个结点,这些结这些结点中的某一个称为根点中的某一个称为根,其他所有结点被分成有限个其他所有结点被分成有限个子根树。子

3、根树。在有向树中，结点的出现次序是没有意义的。在有向树中，结点的出现次序是没有意义的。但实际应用中，有时要给出同一级中结点的相对但实际应用中，有时要给出同一级中结点的相对次序，这便导出有序树的概念。次序，这便导出有序树的概念。4、有序树：在根树中规定了每一层上结点的次、有序树：在根树中规定了每一层上结点的次序，称为有序树。序，称为有序树。为表示结点间的关系，有时借用家族中的术语。为表示结点间的关系，有时借用家族中的术语。在以在以v0为根的树中，为根的树中，（1）v1，v2,，vk称为称为v0的的，v0称为它们的称为它们的。vi，vj 同为一顶点同为一顶点v的儿子时，称它们为的儿子时，称它们为。

4、（2）顶点间的父子关系的传递闭包称为顶点间）顶点间的父子关系的传递闭包称为顶点间的的关系关系。即当。即当vi为为vi+1(i=1,2,l-1)的父亲时，的父亲时，v1是是vl的祖先，的祖先，vl为为v1的子孙。的子孙。（3）根树）根树T自身及以它的树根的子孙为根的根树自身及以它的树根的子孙为根的根树（T的子图），均称为的子图），均称为T的的（subtree），后者），后者又又 称为称为T的的。5、m叉树叉树 定义定义7-8.4：在根树中若每个结点的出度均：在根树中若每个结点的出度均m，则称则称T为为m元树元树(m叉树叉树)，若每个分支点的出度恰好，若每个分支点的出度恰好等于等于m，则称，则称T

5、为为m叉完全树，若叉完全树，若T的所有树叶的层数的所有树叶的层数均相同，则称均相同，则称T正则正则m元树。元树。若若m元树是有序的，则称元树是有序的，则称T为为m元有序树，若元有序树，若m元完全树是有序的则称元完全树是有序的则称T为完全为完全m元有序树，若元有序树，若m元元正则树是有序的，则称正则树是有序的，则称T为为m元正则有序树。元正则有序树。当当m=2时，称为二元树，二元有序树的每个结时，称为二元树，二元有序树的每个结点至多有两个儿子，其序按左右分，分别为左儿子，点至多有两个儿子，其序按左右分，分别为左儿子，右儿子，任一分支点最多有两棵子树，称为左子树右儿子，任一分支点最多有两棵子树，称

6、为左子树和右子树。和右子树。当当m=2时，便可得到常用的二叉树、完全二时，便可得到常用的二叉树、完全二叉树和正则二叉树。不难看出，二叉树中的每个叉树和正则二叉树。不难看出，二叉树中的每个结点结点v，至多有两个子树，分别称为，至多有两个子树，分别称为v的左子树和的左子树和右子树。若右子树。若v只有一个子树，则称它为左子树或右只有一个子树，则称它为左子树或右子树均可。在二叉树的图形表示中，子树均可。在二叉树的图形表示中，v的左子树画的左子树画在在v的左下方，的左下方，v的右子树画在的右子树画在v的右下方。的右下方。有很多实际应用，可用二叉树或有很多实际应用，可用二叉树或m叉树表示。叉树表示。可以指

7、出，按下面算法，任何一棵有序树均能转可以指出，按下面算法，任何一棵有序树均能转成二叉树。其算法是：成二叉树。其算法是：(1)除最左边的分枝结点外，删去所有从每一个结除最左边的分枝结点外，删去所有从每一个结点长出的分枝。在同一级中，兄弟结点之间用从点长出的分枝。在同一级中，兄弟结点之间用从左到右的弧连接。左到右的弧连接。(2)选取直接位于给定结点下面的结点作为左儿子，选取直接位于给定结点下面的结点作为左儿子，与给定结点位于同一水平线上且紧靠它的右边结与给定结点位于同一水平线上且紧靠它的右边结点作为右儿子，如此类推。点作为右儿子，如此类推。上述算法能够推广到有序森林上去。上述算法能够推广到有序森林

8、上去。完全完全m叉树，其树叶的数目为叉树，其树叶的数目为t,分支数为分支数为i,则则(m-1)i=t-1。证明思路：证明思路：m m位选手位选手,单淘汰赛单淘汰赛,每局淘汰每局淘汰(m-1)m-1)位位,共比赛共比赛i i局局,最后剩最后剩1 1位选手。因此有：位选手。因此有：(m-1)i+1=t 例题例题1 1、2 2给出此定理的应用示例。给出此定理的应用示例。二、最优树二、最优树 二叉树的一个重要应用就是最优树问题。给二叉树的一个重要应用就是最优树问题。给定一组数定一组数w1，w2，wn。令一棵二叉树有。令一棵二叉树有n个个叶结点，并对它们分别指派叶结点，并对它们分别指派w1，w2，wn作

9、作为权，则该二叉树称为加权二叉树。为权，则该二叉树称为加权二叉树。完全二叉树有完全二叉树有n个分支点，个分支点，且内部通路长度为总和为且内部通路长度为总和为I，外部通路长度总和，外部通路长度总和为为E，则，则 E=I+2n。证明思路：对证明思路：对分支点分支点n采用数学归纳法。采用数学归纳法。已知已知w1，w2，wn为权，为权，T0为加权二叉树，其为加权二叉树，其权为权为w(T0)，如果对任意加权二叉树，如果对任意加权二叉树T，它的权是，它的权是w(T)，均有均有w(T0)w(T)，则称，则称T0是最优树或是最优树或Huffman树。树。二叉树二叉树T T t (T)(T)=i=1 二叉树二叉

10、树二叉二叉树树(T)(T)T 证明思路：设在带权证明思路：设在带权的最优树中的最优树中,是通路最长是通路最长的分支点的分支点,的儿子分别带权和的儿子分别带权和,故有故有若若,将将与与对调对调,得到新树得到新树TT,则则(TT)-)-(T)=(T)=+-+=+=即即(TT)(T)(T),与是最优树假设矛盾。故与是最优树假设矛盾。故=。同理可证同理可证=。因此。因此=。分别将分别将与与对调得一最优树对调得一最优树,证明思路：根据假设，有证明思路：根据假设，有(T)=(T)=(TT)若若不是最优树不是最优树,则必有另一棵带权则必有另一棵带权的最的最优树优树。对。对中带权中带权的树叶的树叶v v生成两

11、个儿子，得到生成两个儿子，得到新树新树 ，则，则()=)=()因为因为是带权是带权的最优树，故的最优树，故()(TT)若若()(TT),则则()(T T),与与 是带权是带权的最优树矛盾，因此的最优树矛盾，因此()(TT)TT是带权是带权的最优树。的最优树。T 根据上述两个定理，求一棵有根据上述两个定理，求一棵有n个权的最优树，个权的最优树，可简化为求一棵有可简化为求一棵有n-1个权的最优树，而这又可简个权的最优树，而这又可简化为求一棵有化为求一棵有n-2个权的最优树，依此类推。具体个权的最优树，依此类推。具体作法是：首先找出两个最小的权值，设作法是：首先找出两个最小的权值，设w1和和w2。然

12、后对然后对n-1个权个权w1+w2，w3，wn求作一棵最优求作一棵最优树，并且将这棵树中的结树，并且将这棵树中的结w1+w2代之以代之以w1 w2，依，依此类推。此类推。任意一棵二叉树的树叶可对应一个前缀任意一棵二叉树的树叶可对应一个前缀码。码。给定一个序列的集合，若没有一个序列给定一个序列的集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码。是另一个序列的前缀，该序列集合称为前缀码。证明思路：给定一棵二叉树，从每一个分支点引出证明思路：给定一棵二叉树，从每一个分支点引出两条边，对左侧边标以两条边，对左侧边标以0 0，对右侧边标以，对右侧边标以1 1，则每片树叶，则每片树叶将可标定一个将可标定一个0 0和和1 1的序列，它是由树根到这片树叶的通的序列，它是由树根到这片树叶的通路上各边标号所组成的序列，显然，没有一片树叶的标路上各边标号所组成的序列，显然，没有一片树叶的标定序列是另一片树叶标定序列的前缀，因此，任何一棵定序列是另一片树叶标定序列的前缀，因此，任何一棵二叉树的树叶可对应一个前缀码二叉树的树叶可对应一个前缀码。任意一个前缀码都对应一棵二叉树。任意一个前缀码都对应一棵二叉树。