第章树形结构 树形结构是结点之间有分支和层次关系的结构 树形结构是一种非线性结构 在客观世界中,有许多事物本身就呈现树形结 构 家族关系 部门机构设置
1 • 树形结构是结点之间有分支和层次关系的结构 • 树形结构是一种非线性结构 • 在客观世界中，有许多事物本身就呈现树形结 构 – 家族关系 – 部门机构设置
§5.1树结构的基本概念 §5.1.1树结构的定义 非递归定义 树结构是二元组(①D,R),其中,D是n个数据元素的有穷 集合(n0)(数据元素称为结点),R是D上的一个关 系。n=0时,称为空树;否则它满足以下条件: a)有且仅有一个结点d∈D,满足:不存在任何d∈D, 使∈R。我们称它为树的根 b)除根结点d外,D上每个结点d(若有的话),总存在 个唯一的结点d∈D,d,使得<d,d∈R
2 • 非递归定义 树结构是二元组(D, R)，其中，D是n个数据元素的有穷 集合（n≥0）（数据元素称为结点），R是D上的一个关 系。n=0时，称为空树；否则它满足以下条件： a) 有且仅有一个结点d0∈D，满足：不存在任何d∈D， 使∈R。我们称它为树的根。 b) 除根结点d0外，D上每个结点d（若有的话），总存在 一个唯一的结点d'∈D，d≠d'，使得∈R
【例51】设有数据结构T=(D,R),其 中 D=fa,b, c, d, e, f, g) R={r} a, b> a, dx ) 图一棵树
3 【例5.1】设有数据结构T=(D, R)，其 中， D={a,b,c,d,e,f,g} R={r} r={,,,,} a b c d e f g 图 - 一棵树
其他几个概念 路径、通路:如果存在一个结点序列d,dl,y…,d,使 得∈R,j=2,…,k,则这样的结点序列称 为从d1到a的一条路径或通路。也称从d到d有 通路。记为 其中的结点个数称为通路长。有的文献将通路长定义 为通路中的边的个数。 例如,图5.1所示图中,下列结点序列就是几条通路: a,b),(a,c,e),(a,b, c,f, (c,f g)
4 其他几个概念 路径、通路：如果存在一个结点序列 ，使 得 ∈R，j= 2, ..., k，则这样的结点序列称 为从 到 的一条路径或通路。也称从 到 有 通路。记为 • 其中的结点个数称为通路长。有的文献将通路长定义 为通路中的边的个数。 例如，图5.1所示图中，下列结点序列就是几条通路： (a, b), (a,c,e), (a,b,c,f), (c, f, g), …. k di di di , ,..., 1 2 j− j di di , 1 1 i d k i d 1 i d k i d k di di di , ,..., 1 2
其他几个概念 子树:若对上面的树(D,R),有D∈D,R∈R, R是D上的关系,则如果满足上面的树 的定义,则称其为的子树 若的根为x,且∈R,d∈D,则 称为d的子树。 ·若对某结点d,不存x∈D使在∈R,则称d 的子树为空(空子树)
5 其他几个概念 • 子树：若对上面的树(D, R)，有D'∈D, R'∈R， R'是D'上的关系，则如果满足上面的树 的定义，则称其为的子树。 • 若的根为x，且∈R，d∈D，则 称为d的子树。 • 若对某结点d，不存x∈D使在∈R，则称d 的子树为空（空子树）
其他几个概念 例如,图5.1所示图中,下列二元组都是子树: a的子树:(D1,R1),D1={b},R1={},根为b; a的子树:(D2,R2),D2={c,e,fg},R2={C,e>,},根为c a的子树:(D3,R3),D3={d},R3={},根为d c的子树:(D4,R4),D4={e},R4={},根为e c的子树:(D5,R5),D5={h,g},R5={},根为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 a的子树：（D3, R3）, D3={ d}，R3={}，根为d c的子树：（D4, R4）, D4={e}，R4={}，根为e c的子树：（D5, R5）, D5={h, g}，R5={}，根为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={,, 则{D,R}为三叉有序树,r1r2,r3分别表示第一、第二、 第三叉
8 其他几个概念 •例如，例5.1给出的树是个3叉树，但R中只含一个集合r， 所以是无序树。若我们重新定义R(这里是重组合R): R={r1, r2, r3} r1 = {, } r2 = {, , } r3 = {} •则{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 图 - 一棵树