一、根树1、有向树定义7-8.1如果一个有向图在不考虑边的方向时是一棵树，那么，该有向图称为有向树。2、根树定义7-8.2一棵有向树,如果恰有一个结点的入度为0，其余所有结点的入度都为1,则称为根树(rootedtree)。入度为0的结点称为T的树根。出度为0的结点称为树叶，出度不为0的结点称为分支点或内点。习惯把有向树的根画在最上方，边的箭头全指向下，则可以省略全部箭头，树根到一个结点的有向通路的长度称为该点的层数。所有结点的最大层数称为树高。3、子树定义7-8.3：任一结点v及其后代导出的子图称为根树的子树。在有向树中，结点的出现次序是没有意义的。但实际应用中，有时要给出同一级中结点的相对次序，这便导出有序树的概念。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。二、最优树二叉树的一个重要应用就是最优树问题。给定一组数w1，w2，…，wn。令一棵二叉树有n个叶结点，并对它们分别指派w1，w2，…，wn作为权，则该二叉树称为加权二叉树。已知w1，w2，…，wn为权，T0为加权二叉树，其权为w(T0)，如果对任意加权二叉树T，它的权是w(T)，均有w(T0)≥w(T)，则称T0是最优树或Huffman树。定理7-8.3设T为带权w1≤w2≤…≤wt的最优树，则1)带权w1,w2的树叶，vw1,vw2是兄弟。2)以树叶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的最优树。根据上述两个定理，求一棵有n个权的最优树，可简化为求一棵有n-1个权的最优树，而这又可简化为求一棵有n-2个权的最优树，依此类推。具体作法是：首先找出两个最小的权值，设w1和w2。然后对n-1个权w1+w2，w3，…，wn求作一棵最优树，并且将这棵树中的结w1+w2代之以w1w2，依此类推。最优树的定义树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和WPL(T)=wklk(对所有叶子结点)。根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树；在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树