数据结构(第7章).ppt

《数据结构(第7章).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章树与森林⒈教学内容：7.1树的概念与表示7.2基本操作与存储7.3树、森林与二叉树的转换7.4树或森林的遍历7.5树的应用⒉教学目的：⑴深刻理解树的定义、术语；⑵领会并掌握树的各种存储结构；⑶熟练掌握森林与二叉树间的相互转换；⑷领会树和森林的遍历；⑸了解树的简单应用。1⒊教学重点：⑴树的存储结构；⑵森林与二叉树的转换。⒋教学难点：⑴森林与二叉树的转换；⑵判定树；⑶等价关系与等价类问题。⒌学时安排：4学时27.1树的概念与表示7.1.1树的定义及相关术语7.1.2树的表示37.1.1树的定义及相关术语1．树的定义树（Tree）是n（n≥0）个有限数据元

2、素的集合。当n＝0时，称这棵树为空树。在一棵非树T中：⑴有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。⑵若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。--------递归的概念4树的定义还可形式化的描述为二元组的形式：T＝（D，R）其中D为树T中结点的集合，R为树中结点之间关系的集合。当树为空树时，D＝Φ；当树T不为空树时有：D＝{Root}∪DF其中，Root为树T的根结点，DF为树T的根Root的子树集合。

3、DF可由下式表示：DF＝D1∪D2∪…∪Dm且Di∩Dj＝Φ（i≠j，1≤i≤m，1≤j≤m当树T中结点个数n≤1时，R＝Φ；当树T中结点个数n>1时有：R＝{，i＝1，2，…，m}其中，Root为树T的根结点，ri是树T的根结点Root的子树Ti的根结点。5下图是一棵具有9个结点的树，即T＝{A，B，C，…，H，I}，结点A为树T的根结点，除根结点A之外的其余结点分为两个不相交的集合：T1＝{B,D,E,F,H,I}和T2={C,G}，T1和T2构成了结点A的两棵子树，T1和T2本身也分别是一棵树。例如，子树T1的根结点为B，其余结点又

4、分为两个不相交的集合：T11＝{D}，T12＝{E,H,I}和T13＝{F}。T11、T12和T13构成了子树T1的根结点B的三棵子树。如此可继续向下分为更小的子树，直到每棵子树只有一个根结点为止。6从树的定义和图7.1(a)的示例可以看出，树具有下面两个特点：⑴树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。⑵树中所有结点可以有零个或多个后继结点。由此特点可知，下图所示的都不是树结构。72．相关术语在二叉树中介绍的有关概念在树中仍然适用。除此之外，再介绍两个关于树的术语。⑴有序树和无序树。如果一棵树中结点的各子树丛左到右是有次序的，即

5、若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。⑵森林。零棵或有限棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根结点就变成了森林。87.1.2树的表示树的表示方法有四种，各用于不同的目的。1．直观表示法树的直观表示法就是以倒着的分支树的形式表示，下图就是一棵树的直观表示。其特点就是对树的逻辑结构的描述非常直观。是数据结构中最常用的树的描述方法。92．嵌套集合表示法所谓嵌套集合是指一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个。用

6、嵌套集合的形式表示树，就是将根结点视为一个大的集合，其若干棵子树构成这个大集合中若干个互不相交的子集，如此嵌套下去，即构成一棵树的嵌套集合表示。下图就是一棵树的嵌套集合表示。103．凹入表示法树的凹入表示法如左图所示。4．广义表表示法树用广义表表示，就是将根作为由子树森林组成的表的名字写在表的左边，这样依次将树表示出来。(A(B(D,E(H,I),F),C(G)))117.2树的基本操作与存储树的基本操作树的存储结构12树的基本操作通常有以下几种：⑴Initiate（t）初始化一棵空树t。⑵Root（x）求结点x所在树的根结点。⑶Parent（t，x）求树

7、t中结点x的双亲结点。⑷Child（t，x，i）求树t中结点x的第i个孩子结点。⑸RightSibling（t，x）求树t中结点x的第一个右边兄弟结点。13⑹Insert（t，x，i，s）把以s为根结点的树插入到树t中作为结点x的第i棵子树。⑺Delete（t，x，i）在树t中删除结点x的第i棵子树。⑻Tranverse（t）是树的遍历操作，即按某种方式访问树t中的每个结点，且使每个结点只被访问一次。147.2.2树的存储结构1．双亲表示法由树的定义可以知道，树中的每个结点都有唯一的一个双亲结点，根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各

8、个结点，数组中的一个元素表示树中的一个结点，数组元素为结构体类型，