【精品数据结构】树形结构

《【精品数据结构】树形结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树形结构是结点之间有分支和层次关系的结构树形结构是一种非线性结构在客观世界中，有许多事物本身就呈现树形结构家族关系部门机构设置第5章树形结构1非递归定义树结构是二元组(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。§5.1树结构的基本概念§5.1

2、.1树结构的定义2【例5.1】设有数据结构T=(D,R)，其中，D={a,b,c,d,e,f,g}R={r}r={,,,,}abcdefg图‑一棵树3其他几个概念路径、通路：如果存在一个结点序列，使得∈R，j=2,...,k，则这样的结点序列称为从到的一条路径或通路。也称从到有通路。记为其中的结点个数称为通路长。有的文献将通路长定义为通路中的边的个数。例如，图5.1所示图中，下列结点序列就是几条通路：(a,b),(a,c,e),(a,b,c,f),(c,f,g),….4其

3、他几个概念子树：若对上面的树(D,R)，有D'∈D,R'∈R，R'是D'上的关系，则如果满足上面的树的定义，则称其为的子树。若的根为x，且∈R，d∈D，则称为d的子树。若对某结点d，不存x∈D使在∈R，则称d的子树为空（空子树）。5其他几个概念例如，图5.1所示图中，下列二元组都是子树：a的子树：（D1,R1）,D1={b}，R1={},根为b;a的子树：（D2,R2）,D2={c,e,f,g}，R2={,,},根为ca的子树：（

4、D3,R3）,D3={d}，R3={}，根为dc的子树：（D4,R4）,D4={e}，R4={}，根为ec的子树：（D5,R5）,D5={h,g}，R5={}，根为hf的子树：（D6,R6）,D6={g}，R6={}，根为gb,d,e,g无子树，或说子树为空。abcdefg图‑一棵树6其他几个概念n叉树：若各结点的后继个数均不超过n，则称该树为n叉树。例如，例5.1给出的树是个3叉树。有序树：若二元组(D,R)中的关系集合R中含有n个关系集合（n为各结点的最大后继数目），且每个关系集合都不与其他关系集合相交，则称其为有序

5、树。有序树实质上是后继有序的树，即每个结点的n个后继次序相关，不同的次序排列，属于不同的结构。若一棵树是不是有序的，则称为无序树。7其他几个概念例如，例5.1给出的树是个3叉树，但R中只含一个集合r，所以是无序树。若我们重新定义R(这里是重组合R):R={r1,r2,r3}r1={,}r2={,,}r3={}则{D,R}为三叉有序树，r1,r2,r3分别表示第一、第二、第三叉。8树的递归定义树是具有n个结点的有限集合T(这里n≥0)，若n=0则称为空树，否则，它满足：a)

6、有一个特殊结点d0，我们称它为根。b)若T-{d0}非空，则T-{d0}可分成m个(m>0)不相交的集合T1,T2,...,Tm，而且这些集合中的每一个又都是满足本定义的树，称作T的子树。若T-{d0}为空，称T无子树（或子树为空）。9树的递归定义【例5.2】设有下列集合：T={a,b,c,d,e,f,g}abcdefg图‑一棵树10树的递归定义abcdefg图‑一棵树若T1,T2,…,Tk是子树（T1可以不是其他树的子树），它们的根分别是a1,a2,…,ak，T1的子树是T2,T2的子树是T3，…,Tk-1的子树是Tk，则称a1

7、到ak有路径（通路），记为：11树枝（分枝）：结点之间的二元关系（序偶）。度：结点拥有的子树（后继）的个数称为该结点的度，这实质上是出度。叶子：无后继（子树）的结点称为叶子。分枝结点：有后继的结点称为分枝结点。儿子：结点x的子树的根称为x的儿子。双亲（父亲）：结点x的前趋结点称为x的双亲。祖先：结点x的父亲称为该结点的祖先；结点x的父亲的祖先也称x的祖先。§5.1.2基本术语12§5.1.2基本术语后代：结点x的儿子称x的后代，结点x的儿子的后代也称x的后代。兄弟：同父亲的结点称为兄弟结点。堂兄弟：父亲是兄

8、弟关系的结点称为堂兄弟结点。层次（层号）：根为第1层，对任何其它结点，若它父亲为第k层结点，则它为第(k+1)层结点(层号为k+1)。深度：树中的具有最大层号的结点的层号，称为树的深度。13§5.1.2基本术语结点按层编号（层序编号）：将树中结点按