第七章树与森林第七章树与森林⒈教学内容：7.1树的概念与表示7.2基本操作与存储7.3树、森林与二叉树的转换7.4树或森林的遍历7.5树的应用⒉教学目的：⑴深刻理解树的定义、术语；⑵领会并掌握树的各种存储结构；⑶熟练掌握森林与二叉树间的相互转换；⑷领会树和森林的遍历；⑸了解树的简单应用。⒊教学重点：⑴树的存储结构；⑵森林与二叉树的转换。⒋教学难点：⑴森林与二叉树的转换；⑵判定树；⑶等价关系与等价类问题。⒌学时安排：4学时7.17.1树的概念与表示树的概念与表示7.1.1树的定义及相关术语7.1.2树的表示7.1.17.1.1树的定义及相关术语树的定义及相关术语1．树的定义树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0时，称这棵树为空树。在一棵非树T中：⑴有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。⑵若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。----------------递归的概念递归的概念树的定义还可形式化的描述为二元组的形式：T＝（D，R）其中D为树T中结点的集合，R为树中结点之间关系的集合。当树为空树时，D＝Φ；当树T不为空树时有：D＝{Root}∪DF其中，Root为树T的根结点，DF为树T的根Root的子树集合。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的根结点。•下图是一棵具有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，其余结点又分为两个不相交的集合：T11＝{D}，T12＝{E,H,I}和T13＝{F}。T11、T12和T13构成了子树T1的根结点B的三棵子树。如此可继续向下分为更小的子树，直到每棵子树只有一个根结点为止。从树的定义和图7.1(a)的示例可以看出，树具有下面两个特点：⑴树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。⑵树中所有结点可以有零个或多个后继结点。由此特点可知，下图所示的都不是树结构。2．相关术语在二叉树中介绍的有关概念在树中仍然适用。除此之外，再介绍两个关于树的术语。⑴有序树和无序树。如果一棵树中结点的各子树丛左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。⑵森林。零棵或有限棵不相交的树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根结点就变成了森林。7.1.27.1.2树的表示树的表示树的表示方法有四种，各用于不同的目的。1．直观表示法树的直观表示法就是以倒着的分支树的形式表示，下图就是一棵树的直观表示。其特点就是对树的逻辑结构的描述非常直观。是数据结构中最常用的树的描述方法。2．嵌套集合表示法所谓嵌套集合是指一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个。用嵌套集合的形式表示树，就是将根结点视为一个大的集合，其若干棵子树构成这个大集合中若干个互不相交的子集，如此嵌套下去，即构成一棵树的嵌套集合表示。下图就是一棵树的嵌套集合表示。3．凹入表示法树的凹入表示法如左图所示。4．广义表表示法树用广义表表示，就是将根作为由子树森林组成的表的名字写在表的左边，这样依次将树表示出来。(A(B(D,E(H,I),F),C(G)))7.27.2树的基本操作与存储树的基本操作与存储树的基本操作树的存储结构•树的基本操作通常有以下几种：⑴Initiate（t）初始化一棵空树t。⑵Root（x）求结点x所在树的根结点。⑶Parent（t，x）求树t中结点x的双亲结点。⑷Child（t，x，i）求树t中结点x的第i个孩子结点。⑸RightSibling（t，x）求树t中结点x的第一个右边兄弟结点。⑹Insert（t，x，i，s）把以s为根结点的树插入到树t中作为结点x的第...
