树(数据库)
时间：2022-11-14 18:30:01 | 来源：信息时代
时间：2022-11-14 18:30:01 来源：信息时代
树 : 在计算机科学技术中有广泛的应用的一种特殊的图。
1.无向树
连通无回路(这里指初级和简单回路)的无向图称为无向树,常用T表示树。若G无回路且至少有两个连通分支,则称G为森林。在无向树T中,1度顶点称为树叶,度数大于或等于2的顶点称为分支点。
2.无向树的重要性质:
(1)n阶树的边数m=n-1。
(2)若T是非平凡的无向树,则T至少有两片树叶。
(3)在非平凡的无向树的任何两个不同的顶点之间加一条新边,所得图中有一条唯一含此边的回路。
3.生成树
若连通无向图G的生成子图(参见图论)T是树,则称T为G的生成树。T中的边也称为树枝,G的不在T中的边称为T的弦。
例如,在图1中由实线边e1、e2、e3、e6构成的子图T是该图的一棵生成树,虚线边e4、e5为T的弦。
图1 生成树
4. 最小生成树
对图中的每一条边e关联一个实数W(e),把它称作带权图。设T是无向连通带权图G的一棵生成树,它的所有边的权之和称作T的权。无向连通带权图G的所有生成树中权最小的生成树称作G的最小生成树。例如,图2中实线边所示的生成树T为该图的最小生成树,其权W(T)=14。有多种求最小生成树的算法,如避圈法(Kruskal法)、破圈法、逐步短接法、断集法等。
图2 最小生成树
5. 根树
基图为树的有向图称作有向树。在有向树中,主要研究根树。只有一个顶点的入度为0,其余顶点的入度全为1的有向树称为根树。在根树中,入度为0的顶点称为树根;入度为1,出度为0的顶点称为树叶;入度为1,出度不为0的顶点称为内点; 内点和树根统称为分支点。从树根到顶点v的路径长度称为v的层数,树中顶点层数的最大值称为树高。在画根树时,通常将树根放在最上方,所有有向边的方向向下并略去边上的箭头。例如,图3给出一棵根树,a为树根,d、g、h、i为树叶,b、c、e、f为内点,a、b、c、e、f为分支点。
图3 根树
设T为根树, ∀u,v∈V(T), 若u到v有通路,则称u是v的祖先,v是u的后代;若<u,v>∈E(T),则称u是v的父亲,v是u的儿子;若两个顶点有共同的父亲,则称它们是兄弟。按照这样的叫法,也把根树叫作家族树。在根树T中,规定同层顶点的排成顺序,这时称T为有序树。若根树T的每个分支点至少有r个儿子,则称T为r叉树; 若T的每个分支点都恰好有r个儿子,则称T为r叉正则树;所有树叶的层数相同(都等于树高)的r叉正则树称为r叉完全正则树。最常用的是2叉树和2叉有序树。
6.最优2叉树
设2叉树T有t片树叶,每一片树叶v
i的权为w
i(i=1,2,…,t),用l(v
i)表示顶点v
i的层数,称
为T的权。给定w
1,w
2,…,w
t,在所有t片树叶的权为w
1,w
2,…,w
t的2叉树中,权最小的2叉树称为最优2叉树,简称最优树。例如,图4给出权为2、2、3、3、5的最优树,其权W(T)=34。可用Huffman算法求最优树。利用最优树可以产生最佳前缀码,这在信息传输中非常有用。
图4 最优树
在线咨询
