[理学]数据结构7树形结构

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

1、第七章树形结构在前面几章中介绍了各种常用的线性结构，本章介绍非线性结构，其中树型结构就是一种典型的非线性结构。线性结构可以表示元素或结点的相邻关系，而在树型结构中，由于一个结点与多个结点相对应，所以树型结构除用于表示相邻关系外，还可以表示层次关系。树型结构是一类重要的非线性数据结构，其中又以树和二叉树最为常用。直观角度看，树是以分支关系定义的层次结构。树在计算机领域中得到广泛应用，如文件管理中的目录结构、数据库系统中的信息组织形式等。树结构在客观世界中也广泛存在，如人类社会的族谱和各种社会组织机构等都可用树来形象表示。

2、树应用举例书名第一章第二章…第…章第1节………┇┇┇+**ab-fc/dea*b+(c-d/e)*f本章重点讨论二叉树的存储结构及各种操作,并研究树和森林与二叉树之间的转换关系。7.1树的定义和基本术语7.1.1树的定义：一、非数学语言定义树(Tree)是n(n≥0，n=0为空树)个结点的有限集合。在任意一棵非空树中：1.当n>0时有且仅有一个特定的称为根(Root)的结点；2.其余结点可分为m个(m>0)互不相交的有限集T1,T2,…,Tm其中每一个集合Ti本身又是一棵树，并且称为根的子树(SubTree)。例7.1

3、：只有根结点的树A例7.2：一般的树ABECDFGHI树T该树T由子树T1和T2和组成BEDFHIT1CGT2T1包括：DT11EHIT12FT13HT121IT122GT21例7.3：ABCDEFGHIJKLM不是一棵树,因为:子树Tree-H={H，M}子树Tree-I={I，M}出现了交叉，违反树的定义。树的定义是递归的，因为在树的定义中有用到树的定义。它刻画了树的固有特性，即一棵树由若干棵子树构成，而子树又由更小的若干棵子树构成。树是一种非线性数据结构，具有以下特点：它的每个节点都可以有不止一个后继(除根以外的

4、所有结点)，都有且只有一个前驱；这些数据结点按分支关系组织起来，清晰地反映了数据元素之间的层次关系。可以看出，数据元素之间存在的关系是一对多的，或者多对一的关系。补充说明树的分类：(1)自由树(无根树)：结点的排列无关紧要。结点数为1结点数为2结点数为3结点数为4(2)有根树：根结点位于树的顶。(默认讨论的树)结点数为1结点数为2结点数为3结点数为4(3)有序树：能表示第一个孩子、第二孩子……(如族谱、二叉树就是有序的)二、树的形式化定义：(数学语言定义)树定义为集合：T＝{K,R}。K是包含n个结点的有穷集合(n≥0

5、)，关系R满足以下条件：(1)有且仅有一个结点k0∈K，它对于关系R来说没有前驱结点，结点k0称作树的根。(2)除结点k0外，K中的每个结点对于关系R来说都有且仅有一个前驱结点。(3)K中每个结点对于关系R来说可以有多个后继结点。三、抽象数据类型树的定义：ADTTree{数据对象：D={ai

6、1≤i≤n,n>0，ai∈ElemType类型}数据关系：R={

7、ai,aj∈D,1≤i≤n,1≤j≤n,其中每个元素只有一个前驱，可以有零个或多个后继结点，有且仅有一个元素没有前驱}基本运算：InitTree(&t

8、);/*初始化树：构造一个只有一个元素的树*/ClearTree(&t);/*销毁树：释放树t占用的存储空间*/Parent(t);/*求元素t的前驱*/Sons(t);/*求元素t的后继*/…}7.1.2树的逻辑表示方法(其它表示形式)1.树形表示法：这是树的最基本的表示，使用一棵倒置的树表示树结构，非常直观和形象。ABCDEFGHIJKLM2.集合法Tree-A的结构：结点A包括{B,C,D}结点B包括{E,F}结点C包括{G}结点D包括{H,I,J}结点E包括{K,L}结点H包括{M}ABCDEFGHIJKLM3

9、.范式图法或文氏图法(VennDiagram)每棵树对应一个圆圈，圆圈包含根结点和子树的圆圈，同一棵根结点下的各子树对应的圆圈是不能相交的。ABCDEFGHIJKLMA:{B,C,D}B:{E,F}C:{G}D:{H,I,J}E:{K,L}H:{M}4.缩格法(Indentation)或凹入表示法ABCDEFGHIJKLM5.嵌套括弧法(NestedParentheses)用最外层括弧表示树的根，子树嵌套在根括弧之内。(A(B,C,D))(E,F)(G)(H,I,J)(K,L)(M)6.层数号码法(LevelNumbe

10、rFormat)用层数来表示结点所在的位置1…………………………A2…………………………B2…………………………C2…………………………D3…………………………E3…………………………F3…………………………G3…………………………H3…………………………I3…………………………J4…………………………K4…………………………L4