第章树形结构 树形结构是结点之间有分支和层次关系的结构 树形结构是一种非线性结构 在客观世界中,有许多事物本身就呈现树形结 构 家族关系 部门机构设置
1 • 树形结构是结点之间有分支和层次关系的结构 • 树形结构是一种非线性结构 • 在客观世界中，有许多事物本身就呈现树形结 构 – 家族关系 – 部门机构设置
§5.1树结构的基本概念 §5.1.1树结构的定义 非递归定义 树结构是二元组(①D,R),其中,D是n个数据元素的有穷 集合(n0)(数据元素称为结点),R是D上的一个关 系。n=0时,称为空树;否则它满足以下条件: a)有且仅有一个结点d∈D,满足:不存在任何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， 使<d, d0>∈R。我们称它为树的根。 b) 除根结点d0外，D上每个结点d（若有的话），总存在 一个唯一的结点d'∈D，d≠d'，使得<d', d>∈R
【例51】设有数据结构T=(D,R),其 中 D=fa,b, c, d, e, f, g) R={r} a, b>< a,c> a, dx<c, e> <c, f, f g>) 图一棵树
3 【例5.1】设有数据结构T=(D, R)，其 中， D={a,b,c,d,e,f,g} R={r} r={<a,b>,<a,c>,<a,d><c,e>,<c,f>,<f,g>} a b c d e f g 图 - 一棵树
其他几个概念 路径、通路:如果存在一个结点序列d,dl,y…,d,使 得<d1,d1>∈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上的关系,则如果<D,R>满足上面的树 的定义,则称其为<D,R>的子树 若<D,R>的根为x,且<d,x>∈R,d∈D,则 称<D,R>为d的子树。 ·若对某结点d,不存x∈D使在<d,x>∈R,则称d 的子树为空(空子树)
5 其他几个概念 • 子树：若对上面的树(D, R)，有D'∈D, R'∈R， R'是D'上的关系，则如果<D', R'>满足上面的树 的定义，则称其为<D, R>的子树。 • 若<D', R'>的根为x，且<d, x>∈R，d∈D，则 称<D', R'>为d的子树。 • 若对某结点d，不存x∈D使在<d,x>∈R，则称d 的子树为空（空子树）