7-8 根树及其应用一、根树
1、有向树定义 7-8.1 如果一个有向图在不考虑边的方向时是一棵树，那么，该有向图称为 有向树 。
2、根树定义 7-8.2 一棵有向树,如果恰有一个结点的入度为 0，其余所有结点的入度都为 1,
则称为 根树 (rooted tree)。入度为 0的结点称为 T的 树根 。出度为 0的结点称为 树叶,出度不为 0的结点称为 分支点 或 内点 。
根树的画法有,树根在下，向上生长；
树根在上，向下生长。
习惯把有向树的根画在最上方，边的箭头全指向下，则可以省略全部箭头，树根到一个结点的有向通路的长度称为该点的层数。所有结点的最大层数称为树高。
3、子树定义 7-8.3：任一结点 v及其后代导出的子图称为根树的子树。
定义 7-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.定理 7-8.1 设有 完全 m叉树，其树叶的数目为 t,
分支数为 i,则 (m-1)× i=t-1。
证明思路,m位选手,单淘汰赛,每局淘汰 (m-1)位,
共比赛 i局,最后剩 1位选手。因此有：
(m-1)× i+1=t?
例题 1,2给出此定理的应用示例。
7.定义 7-8.5 在根树中，一个结点的 通路长度,就是从树根到该结点的通路中的边数。分支点的通路长度称为 内部通路长度,树叶的通路长度称为 外部通路长度 。
二、最优树二叉树的一个重要应用就是最优树问题。给定一组数 w1,w2,…,wn。令一棵二叉树有 n个叶结点，并对它们分别指派 w1,w2,…,wn作为权，则该二叉树称为加权二叉树。
8.定理 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.定义 7-8.6 在带权 二叉树 T中，若带权为 wi树叶，其通路长度为 L(wi),把
t
w(T) =? wi L(wi)
i=1
称为该带权 二叉树 权,所有带权 w1,w2,…,wt的 二叉树 树中,w(T)最小的那棵树，称为 最优树 。
定理 7-8.3 设 T为带权 w1≤ w2≤ … ≤ wt的最优树，则
1) 带权 w1,w2的树叶,vw1,vw2是兄弟。
2) 以树叶 vw1,vw2为儿子的分支点,其通路长度最长。
证明思路：设在带权 w1,w2,…,wt的最优树中,v是通路最长的分支点,v的儿子分别带权和,故有
L(wx) ≥ L(w1)
L(wy) ≥ L(w2)
若 L(wx) > L(w1),将 wx与 w1对调,得到新树 T’,则
w(T’)-w(T)=[w1L(wx)+wxL(w1)]-[wxL(wx)+ w1L(w1)]
= L(wx)(w1 - wx)+ L(w1)(wx - w1)
= (wx - w1)[L(w1) - L(wx) ]<0
即 w(T’)<w(T),与是最优树假设矛盾。故 L(wx)=L(w1)。
同理可证 L(wx)=L(w2)。因此
L(wx)=L(wy)=L(w1)=L(w2)。
分别将 w1,w2与 wx,wy对调得一最优树,vw1,vw2是兄弟。
证明思路：根据假设，有
w(T)= w(T’) +w1+ w2
若 T’不是最优树,则必有另一棵带权 w1+w2,w3,…,wt的最优树 T’’。对 T’’中带权 w1+w2的树叶 vw1+w2生成两个儿子，得到新树 T*,则
w(T*)= w(T’’) +w1+ w2
因为 T’’是带权 w1+w2,w3,…,wt的最优树，故
w(T’’)≤ w(T’)
若 w(T’’)<w(T’),则 w(T*)<w(T),与 T是 带权 w1,w2,…,wt
的最优树矛盾，因此
w(T’’) = w(T’)
T’是带权 w1+w2,w3,…,wt的最优树。
定理 7-8.4 设 T为带权 w1≤ w2≤ … ≤ wt的最优树，若将以带权 w1和 w2的树叶为儿子的分支点改为带权 w1+w2的树叶,得到一棵新树 T’,则 T’也是最优树。
根据上述两个定理，求一棵有 n个权的最优树，
可简化为求一棵有 n-1个权的最优树，而这又可简化为求一棵有 n-2个权的最优树，依此类推。具体作法是：首先找出两个最小的权值，设 w1和 w2。
然后对 n-1个权 w1+w2,w3,…,wn求作一棵最优树，并且将这棵树中的结 w1+w2代之以 w1 w2，依此类推。
定理 7-8.5 任意一棵二叉树的树叶可对应一个前缀码。
定义 7-8.7 给定一个序列的集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码。
证明思路：给定一棵二叉树，从每一个分支点引出两条边，对左侧边标以 0，对右侧边标以 1，则每片树叶将可标定一个 0和 1的序列，它是由树根到这片树叶的通路上各边标号所组成的序列，显然，没有一片树叶的标定序列是另一片树叶标定序列的前缀，因此，任何一棵二叉树的树叶可对应一个前缀码 。
定理 7-8.6 任意一个前缀码都对应一棵二叉树。
1、有向树定义 7-8.1 如果一个有向图在不考虑边的方向时是一棵树，那么，该有向图称为 有向树 。
2、根树定义 7-8.2 一棵有向树,如果恰有一个结点的入度为 0，其余所有结点的入度都为 1,
则称为 根树 (rooted tree)。入度为 0的结点称为 T的 树根 。出度为 0的结点称为 树叶,出度不为 0的结点称为 分支点 或 内点 。
根树的画法有,树根在下，向上生长；
树根在上，向下生长。
习惯把有向树的根画在最上方，边的箭头全指向下，则可以省略全部箭头，树根到一个结点的有向通路的长度称为该点的层数。所有结点的最大层数称为树高。
3、子树定义 7-8.3：任一结点 v及其后代导出的子图称为根树的子树。
定义 7-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.定理 7-8.1 设有 完全 m叉树，其树叶的数目为 t,
分支数为 i,则 (m-1)× i=t-1。
证明思路,m位选手,单淘汰赛,每局淘汰 (m-1)位,
共比赛 i局,最后剩 1位选手。因此有：
(m-1)× i+1=t?
例题 1,2给出此定理的应用示例。
7.定义 7-8.5 在根树中，一个结点的 通路长度,就是从树根到该结点的通路中的边数。分支点的通路长度称为 内部通路长度,树叶的通路长度称为 外部通路长度 。
二、最优树二叉树的一个重要应用就是最优树问题。给定一组数 w1,w2,…,wn。令一棵二叉树有 n个叶结点，并对它们分别指派 w1,w2,…,wn作为权，则该二叉树称为加权二叉树。
8.定理 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.定义 7-8.6 在带权 二叉树 T中，若带权为 wi树叶，其通路长度为 L(wi),把
t
w(T) =? wi L(wi)
i=1
称为该带权 二叉树 权,所有带权 w1,w2,…,wt的 二叉树 树中,w(T)最小的那棵树，称为 最优树 。
定理 7-8.3 设 T为带权 w1≤ w2≤ … ≤ wt的最优树，则
1) 带权 w1,w2的树叶,vw1,vw2是兄弟。
2) 以树叶 vw1,vw2为儿子的分支点,其通路长度最长。
证明思路：设在带权 w1,w2,…,wt的最优树中,v是通路最长的分支点,v的儿子分别带权和,故有
L(wx) ≥ L(w1)
L(wy) ≥ L(w2)
若 L(wx) > L(w1),将 wx与 w1对调,得到新树 T’,则
w(T’)-w(T)=[w1L(wx)+wxL(w1)]-[wxL(wx)+ w1L(w1)]
= L(wx)(w1 - wx)+ L(w1)(wx - w1)
= (wx - w1)[L(w1) - L(wx) ]<0
即 w(T’)<w(T),与是最优树假设矛盾。故 L(wx)=L(w1)。
同理可证 L(wx)=L(w2)。因此
L(wx)=L(wy)=L(w1)=L(w2)。
分别将 w1,w2与 wx,wy对调得一最优树,vw1,vw2是兄弟。
证明思路：根据假设，有
w(T)= w(T’) +w1+ w2
若 T’不是最优树,则必有另一棵带权 w1+w2,w3,…,wt的最优树 T’’。对 T’’中带权 w1+w2的树叶 vw1+w2生成两个儿子，得到新树 T*,则
w(T*)= w(T’’) +w1+ w2
因为 T’’是带权 w1+w2,w3,…,wt的最优树，故
w(T’’)≤ w(T’)
若 w(T’’)<w(T’),则 w(T*)<w(T),与 T是 带权 w1,w2,…,wt
的最优树矛盾，因此
w(T’’) = w(T’)
T’是带权 w1+w2,w3,…,wt的最优树。
定理 7-8.4 设 T为带权 w1≤ w2≤ … ≤ wt的最优树，若将以带权 w1和 w2的树叶为儿子的分支点改为带权 w1+w2的树叶,得到一棵新树 T’,则 T’也是最优树。
根据上述两个定理，求一棵有 n个权的最优树，
可简化为求一棵有 n-1个权的最优树，而这又可简化为求一棵有 n-2个权的最优树，依此类推。具体作法是：首先找出两个最小的权值，设 w1和 w2。
然后对 n-1个权 w1+w2,w3,…,wn求作一棵最优树，并且将这棵树中的结 w1+w2代之以 w1 w2，依此类推。
定理 7-8.5 任意一棵二叉树的树叶可对应一个前缀码。
定义 7-8.7 给定一个序列的集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码。
证明思路：给定一棵二叉树，从每一个分支点引出两条边，对左侧边标以 0，对右侧边标以 1，则每片树叶将可标定一个 0和 1的序列，它是由树根到这片树叶的通路上各边标号所组成的序列，显然，没有一片树叶的标定序列是另一片树叶标定序列的前缀，因此，任何一棵二叉树的树叶可对应一个前缀码 。
定理 7-8.6 任意一个前缀码都对应一棵二叉树。
