其他几个概念 例如,图5.1所示图中,下列二元组都是子树: a的子树:(D1,R1),D1={b},R1={},根为b; a的子树:(D2,R2),D2={c,e,fg},R2={C,e>,<c图s棵树 <g>},根为c a的子树:(D3,R3),D3={d},R3={},根为d c的子树:(D4,R4),D4={e},R4={},根为e c的子树:(D5,R5),D5={h,g},R5={<hg>},根为h f的子树:(D6,R6),D6={g},R6={},根为g b,d,e,g无子树,或说子树为空
6 其他几个概念 例如，图5.1所示图中，下列二元组都是子树： a的子树：（D1, R1）, D1={b}，R1={}, 根为b; a的子树：（D2, R2）, D2={c, e, f, g}，R2={<c, e>, <c, f>, <f, g>},根为c a的子树：（D3, R3）, D3={ d}，R3={}，根为d c的子树：（D4, R4）, D4={e}，R4={}，根为e c的子树：（D5, R5）, D5={h, g}，R5={<h, g>}，根为h f的子树：（D6, R6）, D6={g}，R6={}，根为g b, d, e, g无子树，或说子树为空。 a b c d e f g 图 - 一棵树
其他几个概念 n叉树:若各结点的后继个数均不超过n,则称该树为n 叉树。例如,例5.1给出的树是个3叉树 有序树:若二元组(D,R)中的关系集合R中含有n个关系 集合(n为各结点的最大后继数目),且每个关系集合都 不与其他关系集合相交,则称其为有序树。有序树实质 上是后继有序的树,即每个结点的n个后继次序相关,不 同的次序排列,属于不同的结构 若一棵树是不是有序的,则称为无序树
7 其他几个概念 •n叉树：若各结点的后继个数均不超过n，则称该树为n 叉树。例如，例5.1给出的树是个3叉树。 •有序树：若二元组(D, R)中的关系集合R中含有n个关系 集合（n为各结点的最大后继数目），且每个关系集合都 不与其他关系集合相交，则称其为有序树。有序树实质 上是后继有序的树，即每个结点的n个后继次序相关，不 同的次序排列，属于不同的结构。 • 若一棵树是不是有序的，则称为无序树
其他几个概念 ●例如,例5.1给出的树是个3叉树,但R中只含一个集合r, 所以是无序树。若我们重新定义R(这里是重组合R) R={r1,r2,r3} r2={<a,c>,<c,f>, 则{D,R}为三叉有序树,r1r2,r3分别表示第一、第二、 第三叉
8 其他几个概念 •例如，例5.1给出的树是个3叉树，但R中只含一个集合r， 所以是无序树。若我们重新定义R(这里是重组合R): R={r1, r2, r3} r1 = {<a, b>, <c, e>} r2 = {<a, c>, <c, f>, <f, g>} r3 = {<a, d>} •则{D, R}为三叉有序树，r1,r2, r3分别表示第一、第二、 第三叉
树的递归定义 树是具有n个结点的有限集合T(这里n≥0),若n=0 则称为空树,否则,它满足: a)有一个特殊结点d,我们称它为根。 b)若T{d}非空,则T{db}可分成m个m>0)不相 交的集合T1T2,…,Tm,而且这些集合中的每一个又 都是满足本定义的树,称作T的子树。若T{do}为 空,称T无子树(或子树为空)
9 树的递归定义 •树是具有n个结点的有限集合T(这里n≥0)，若n=0 则称为空树，否则，它满足： a)有一个特殊结点d0，我们称它为根。 b)若T-{d0 }非空，则T-{d0 }可分成m个(m>0)不相 交的集合T1 ,T2 ,...,Tm，而且这些集合中的每一个又 都是满足本定义的树，称作T的子树。若T-{d0 }为 空，称T无子树（或子树为空）
树的递归定义 【例5,2】设有下列集合: fa, b, c, d, e,f,gi )(e(d 图一棵树
10 树的递归定义 【例5.2】设有下列集合： T={a, b, c, d, e, f, g} a b c d e f g 图 - 一棵树