23根树及其应用.ppt

7-8 7-8 根树及其应用根树及其应用一、根树一、根树1、有向树、有向树定义定义定义定义7-8.17-8.1 如果一个有向图在不考虑边的方向时如果一个有向图在不考虑边的方向时是一棵树，那么，该有向图称为是一棵树，那么，该有向图称为 有向树有向树有向树有向树 2、根树、根树 定义定义7-8.2 一棵有向树一棵有向树,如果恰有一个如果恰有一个结点的入度为结点的入度为0，其余所有结点的入度都为，其余所有结点的入度都为1,则称为则称为根树根树(rooted tree)入度为入度为0的结点称的结点称为为T的的树根树根出度为0的结点称为的结点称为树叶树叶，出度，出度不为不为0的结点称为的结点称为分支点分支点或或内点内点 根树的画法有：根树的画法有：树根在下，向上生长；树根在下，向上生长； 树根在上，向下生长树根在上，向下生长 习惯把有向树的根画在最上方，边的箭头全指习惯把有向树的根画在最上方，边的箭头全指向下，则可以省略全部箭头，树根到一个结点的有向下，则可以省略全部箭头，树根到一个结点的有向通路的长度称为该点的层数。

所有结点的最大层向通路的长度称为该点的层数所有结点的最大层数称为树高数称为树高3、子树、子树 定义定义7-8.3：任一结点：任一结点v及其后代导出的子图及其后代导出的子图称为根树的子树称为根树的子树 定义定义定义定义7-8.37-8.3 根树包含一个或多个结点根树包含一个或多个结点,这些结这些结点中的某一个称为根点中的某一个称为根,其他所有结点被分成有限个其他所有结点被分成有限个子根树 在有向树中，结点的出现次序是没有意义的在有向树中，结点的出现次序是没有意义的但实际应用中，有时要给出同一级中结点的相对但实际应用中，有时要给出同一级中结点的相对次序，这便导出有序树的概念次序，这便导出有序树的概念4、有序树：在根树中规定了每一层上结点的次、有序树：在根树中规定了每一层上结点的次序，称为有序树序，称为有序树 为表示结点间的关系，有时借用家族中的术语为表示结点间的关系，有时借用家族中的术语 定义定义定义定义 在以在以v0为根的树中，为根的树中， （（1））v1，，v2,…，，vk称为称为v0的的 儿子儿子儿子儿子，，v0称为它们称为它们的的父亲父亲父亲父亲。

vi，，vj 同为一顶点同为一顶点v的儿子时，称它们为的儿子时，称它们为兄兄兄兄弟弟弟弟 （（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为为m叉完全树，若叉完全树，若T的所有树叶的层数均的所有树叶的层数均相同，则称相同，则称T正则正则m元树 若若m元树是有序的，则称元树是有序的，则称T为为m元有序树，若元有序树，若m元完全树是有序的则称元完全树是有序的则称T为完全为完全m元有序树，若元有序树，若m元元正则树是有序的，则称正则树是有序的，则称T为为m元正则有序树。

元正则有序树 当当m=2时，称为二元树，二元有序树的每个结点时，称为二元树，二元有序树的每个结点至多有两个儿子，其序按左右分，分别为左儿子，右至多有两个儿子，其序按左右分，分别为左儿子，右儿子，任一分支点最多有两棵子树，称为左子树和右儿子，任一分支点最多有两棵子树，称为左子树和右子树 当当m=2时，便可得到常用的二叉树、完全二叉时，便可得到常用的二叉树、完全二叉树和正则二叉树不难看出，二叉树中的每个结树和正则二叉树不难看出，二叉树中的每个结点点v，，至多有两个子树，分别称为至多有两个子树，分别称为v的左子树和右的左子树和右子树若v只有一个子树，则称它为左子树或右子只有一个子树，则称它为左子树或右子树均可在二叉树的图形表示中，树均可在二叉树的图形表示中，v的左子树画在的左子树画在v的左下方，的左下方，v的右子树画在的右子树画在v的右下方的右下方 有很多实际应用，可用二叉树或有很多实际应用，可用二叉树或m叉树表示叉树表示可以指出，按下面算法，任何一棵有序树均能转可以指出，按下面算法，任何一棵有序树均能转成二叉树其算法是：成二叉树其算法是：(1) 除最左边的分枝结点外，删去所有从每一个结除最左边的分枝结点外，删去所有从每一个结点长出的分枝。

在同一级中，兄弟结点之间用从点长出的分枝在同一级中，兄弟结点之间用从左到右的弧连接左到右的弧连接2) 选取直接位于给定结点下面的结点作为左儿子，选取直接位于给定结点下面的结点作为左儿子，与给定结点位于同一水平线上且紧靠它的右边结与给定结点位于同一水平线上且紧靠它的右边结点作为右儿子，如此类推点作为右儿子，如此类推 上述算法能够推广到有序森林上去上述算法能够推广到有序森林上去 6. 6.定理定理定理定理7-8.1 7-8.1 设有设有设有设有完全完全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给出此定理的应用示例给出此定理的应用示例 7. 7.定义定义定义定义7-8.5 7-8.5 在根树中，一个结点的在根树中，一个结点的在根树中，一个结点的在根树中，一个结点的通路长度通路长度通路长度通路长度，就，就，就，就是从树根到该结点的通路中的边数。

分支点的通路长是从树根到该结点的通路中的边数分支点的通路长是从树根到该结点的通路中的边数分支点的通路长是从树根到该结点的通路中的边数分支点的通路长度称为度称为度称为度称为内部通路长度内部通路长度内部通路长度内部通路长度，树叶的通路长度称为，树叶的通路长度称为，树叶的通路长度称为，树叶的通路长度称为外部通路外部通路外部通路外部通路长度长度长度长度二、最优树二、最优树 二叉树的一个重要应用就是最优树问题给二叉树的一个重要应用就是最优树问题给定一组数定一组数w1，，w2，，…，，wn令一棵二叉树有令一棵二叉树有n个个叶结点，并对它们分别指派叶结点，并对它们分别指派w1，，w2，，…，，wn作作为权，则该二叉树称为加权二叉树为权，则该二叉树称为加权二叉树 8. 8.定理定理定理定理7-8.2 7-8.2 设有设有设有设有完全二叉树有完全二叉树有n个分支点，个分支点，且内部通路长度为总和为且内部通路长度为总和为I ，，外部通路长度总和外部通路长度总和为为E ，，则则 E=I+2n 证明思路：对证明思路：对分支点分支点n采用数学归纳法。

采用数学归纳法 已知已知w1，，w2，，…，，wn为权，为权，T0为加权二叉树，其为加权二叉树，其权为权为w(T0)，，如果对任意加权二叉树如果对任意加权二叉树T，，它的权是它的权是w(T)，，均有均有w(T0)≥w(T)，，则称则称T0是最优树或是最优树或Huffman树 9. 9.定义定义定义定义7-8.6 7-8.6 在带权在带权在带权在带权二叉树二叉树T T中，若带权为中，若带权为中，若带权为中，若带权为w wi i树叶，树叶，树叶，树叶，其通路长度为其通路长度为其通路长度为其通路长度为L(L(w wi i) ) , ,把把把把 t w w(T) (T) =   w wi i L(L(w wi i) ) i=1 称为该带权称为该带权称为该带权称为该带权二叉树二叉树权权权权，所有带权，所有带权，所有带权，所有带权w w1 1, , w w2 2, ,……, , w wt t的的的的二叉二叉树树树中，树中，树中，树中， w w(T)(T)最小的那棵树，称为最小的那棵树，称为最小的那棵树，称为最小的那棵树，称为最优树最优树最优树最优树。

 定理定理定理定理7-8.3 7-8.3 设设设设T为带权为带权为带权为带权w w1 1≤≤w w2 2≤≤……≤≤w wt t的最优树，则的最优树，则的最优树，则的最优树，则 1) 1) 带权带权带权带权w w1 1, ,w w2 2的树叶，的树叶，的树叶，的树叶，v vw1w1, , v vw2w2是兄弟 2) 2) 以树叶以树叶以树叶以树叶v vw1w1, , v vw2w2为儿子的分支点为儿子的分支点为儿子的分支点为儿子的分支点, ,其通路长度最长其通路长度最长其通路长度最长其通路长度最长 证明思路：设在带权证明思路：设在带权w w1 1, , w w2 2, ,……, , w wt t的最优树中的最优树中, , v v是通路最长是通路最长的分支点的分支点, , v v的儿子分别带权和的儿子分别带权和, ,故有故有 L(L(w wx x) ) ≥≥ L(w L(w1 1) ) L( L(w wy y) ) ≥≥ L(w L(w2 2) ) 若若L(L(w wx x) > L(w) > L(w1 1) ), ,将将w wx x与与w w1 1对调对调, ,得到新树得到新树T’T’, ,则则 w w( (T’T’)-)-w w(T)=[(T)=[w w1 1L(L(w wx x) )+ +w wx xL L(w(w1 1) )]-[]-[w wx xL L( (w wx x) )+ + w w1 1L(wL(w1 1) )] ] = = L(L(w wx x)(w)(w1 1 - - w wx x) )+ + L(wL(w1 1)( )(w wx x - w - w1 1) ) = = ( (w wx x - w - w1 1)[L(w)[L(w1 1) - L() - L(w wx x) ]<0) ]<0即即w w( (T’T’)<)

故与是最优树假设矛盾故L(L(w wx x) )= =L(wL(w1 1) ) 同理可证同理可证L(L(w wx x) )= =L(wL(w2 2) )因此因此 L(L(w wx x) )= =L(L(w wy y)=L(w)=L(w1 1) )= =L(wL(w2 2) )分别将分别将w w1 1, , w w2 2与与w wx x, , w wy y对调得一最优树对调得一最优树, ,v vw1w1, , v vw2w2是兄弟 证明思路：根据假设，有证明思路：根据假设，有 w w(T)= (T)= w w( (T’T’) ) +w +w1 1+ + w w2 2 若若T’T’不是最优树不是最优树, , 则必有另一棵带权则必有另一棵带权w w1 1+w+w2 2, , w w3 3, ,……, , w wt t的的最优树最优树T’’T’’对T’’T’’中带权中带权w w1 1+w+w2 2的树叶的树叶v vw1+w2w1+w2生成两个儿子，得生成两个儿子，得到新树到新树T*T* ，，则则 w w( (T*T*)= )= w w( (T’’T’’) ) +w +w1 1+ + w w2 2因为因为T’’T’’是带权是带权w w1 1+w+w2 2, , w w3 3, ,……, , w wt t的最优树，故的最优树，故 w w( (T’’T’’) ) ≤ ≤ w w( (T’T’) ) 若若w w( (T’’T’’)<)

 定理定理定理定理7-8.4 7-8.4 设设设设T为带权为带权为带权为带权w w1 1≤≤w w2 2≤≤……≤≤w wt t的最优树，若将以带的最优树，若将以带的最优树，若将以带的最优树，若将以带权权权权w w1 1和和和和w w2 2的树叶为儿子的分支点改为带权的树叶为儿子的分支点改为带权的树叶为儿子的分支点改为带权的树叶为儿子的分支点改为带权w w1 1+w+w2 2的树叶的树叶的树叶的树叶, ,得到一得到一得到一得到一棵新树棵新树棵新树棵新树T’T’, ,则则则则T’T’也是最优树也是最优树也是最优树也是最优树 根据上述两个定理，求一棵有根据上述两个定理，求一棵有n个权的最优树，个权的最优树，可简化为求一棵有可简化为求一棵有n-1个权的最优树，而这又可简个权的最优树，而这又可简化为求一棵有化为求一棵有n-2个权的最优树，依此类推具体个权的最优树，依此类推具体作法是：首先找出两个最小的权值，设作法是：首先找出两个最小的权值，设w1和和w2然后对然后对n-1个权个权w1+w2，，w3，，…，，wn求作一棵最优求作一棵最优树，并且将这棵树中的结树，并且将这棵树中的结w1+w2代之以代之以w1 w2，，依依此类推。

此类推 定理定理定理定理7-8.57-8.5 任意一棵二叉树的树叶可对应一个前缀任意一棵二叉树的树叶可对应一个前缀码 定义定义定义定义7-8.77-8.7 给定一个序列的集合，若没有一个序列给定一个序列的集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码是另一个序列的前缀，该序列集合称为前缀码 证明思路：给定一棵二叉树，从每一个分支点引出两证明思路：给定一棵二叉树，从每一个分支点引出两条边，对左侧边标以条边，对左侧边标以0 0，对右侧边标以，对右侧边标以1 1，则每片树叶将，则每片树叶将可标定一个可标定一个0 0和和1 1的序列，它是由树根到这片树叶的通路的序列，它是由树根到这片树叶的通路上各边标号所组成的序列，显然，没有一片树叶的标定上各边标号所组成的序列，显然，没有一片树叶的标定序列是另一片树叶标定序列的前缀，因此，任何一棵二序列是另一片树叶标定序列的前缀，因此，任何一棵二叉树的树叶可对应一个前缀码叉树的树叶可对应一个前缀码  定理定理定理定理7-8.67-8.6 任意一个前缀码都对应一棵二叉树。

任意一个前缀码都对应一棵二叉树。