第七章树与森林 1.教学内容:7.1树的概念与表示 7.2基本操作与存储 7.3树、森林与二叉树的转换 7.4树或森林的遍历 7.5树的应用 2教学目的:(1)深刻理解树的定义、术语 2)领会并掌握树的各种存储结构 (3)熟练掌握森林与二叉树间的相互转换:c○ (4)领会树和森林的遍历 (5)了解树的简单应用 3教学重点:(1)树的存储结构 (2)森林与二叉树的转换。 4教学难点:(1)森林与二叉树的转换 (2)判定树 (3)等价关系与等价类问题。 5学时安排:4学时 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 1 第七章 树与森林 ⒈教学内容：7.1 树的概念与表示 7.2 基本操作与存储 7.3 树、森林与二叉树的转换 7.4 树或森林的遍历 7.5 树的应用 ⒉教学目的：⑴ 深刻理解树的定义、术语； ⑵ 领会并掌握树的各种存储结构； ⑶ 熟练掌握森林与二叉树间的相互转换； ⑷ 领会树和森林的遍历； ⑸ 了解树的简单应用。 ⒊教学重点：⑴ 树的存储结构； ⑵ 森林与二叉树的转换。 ⒋教学难点：⑴ 森林与二叉树的转换； ⑵ 判定树； ⑶ 等价关系与等价类问题。 ⒌学时安排： 4学时
7.1树的概念与表示 ◆树的定义及相关术语 ◆树的表示 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 2 7.1 树的概念与表示 树的定义及相关术语 树的表示
7.1.1树的定义及相关术语 41.树的定义 树(Tee)是n(n≥0)个有限数据元素的集合。当n 0时,称这棵树为空树。在一棵非树T中: (1)有一个特殊的数据元素称为树的根结点,根结点没 有前驱结点。 (2)若n>1,除根结点之外的其余数据元素被分成m (m>0)个互不相交的集合T1,下立刚。树T1,T2,…, Tm,其中每 个集合T1(1≤≤m)本身又是一棵 T称为这个根结点的子树。 ◆可以看出,在树的定义中用了递归概念,即用树来定 义树。因此,树结构的算法类同于二叉树结构的算法, 也可以使用递归方法。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 3 7.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= RootUDe 其中,Root为树T的根结点,D为树T的根Rot的子树集合。 D可由下式表示: D=D1UD2U….∪Dm且D∩D1=d (i≠j,1≤i≤m,1≤j≤m 当树T中结点个数n≤1时,R=Φ;当树T中结点个数n1时 有 R={,i=1,2,,m} 其中,Root为树T的根结点,r;是树T的根结点Rot的子树T的 根结点。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 4 树的定义还可形式化的描述为二元组的形式： 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={BDEH}和T2={CG},T1和T2 构成了结点A的两棵子树,T和T2本身也分别是一棵树。例 如,子树T的根结点为B,其余结点又分为两个不相交的集 合:T1={D},T12=EH和T13={F}。T1、T12和T3构成 了子树T1的根结点B的三棵子树。如此可继续向下分为更小 的子树,直到每棵子树只有一个根结点为止。 B 2021年1月21日
2021年1月21日 数据结构讲义 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，其余结点又分为两个不相交的集 合：T11 ＝{D}，T12 ＝{E,H,I}和T13 ＝{F}。T11、T12和T13构成 了子树T1的根结点B的三棵子树。如此可继续向下分为更小 的子树，直到每棵子树只有一个根结点为止
从树的定义和图71(a)的示例可以看出,树具有下面两个 特点: (1)树的根结点没有前驱结点,除根结点之外的所有结点 有且只有一个前驱结点。 (2)树中所有结点可以有零个或多个后继结点 由此特点可知,下图所示的都不是树结构。 A ( 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 6 从树的定义和图7.1(a)的示例可以看出，树具有下面两个 特点： ⑴树的根结点没有前驱结点，除根结点之外的所有结点 有且只有一个前驱结点。 ⑵树中所有结点可以有零个或多个后继结点。 由此特点可知，下图所示的都不是树结构
2.相关术语 在二叉树中介绍的有关概念在树中仍然适用。除此之外, 再介绍两个关于树的术语。 (1)有序树和无序树。如果一棵树中结点的各子树丛左到右 是有次序的,即若交换了某结点各子树的相对位置,则构成 不同的树,称这棵树为有序树;反之,则称为无序树 )森林。零棵或有限棵不相交的树的集合称为森林。自然 界中树和森林是不同的概念,但在数据结构中,树和森林只 有很小的差别。任何一棵树,删去根结点就变成了森林。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 7 2．相关术语 在二叉树中介绍的有关概念在树中仍然适用。除此之外， 再介绍两个关于树的术语。 ⑴有序树和无序树。如果一棵树中结点的各子树丛左到右 是有次序的，即若交换了某结点各子树的相对位置，则构成 不同的树，称这棵树为有序树；反之，则称为无序树。 ⑵森林。零棵或有限棵不相交的树的集合称为森林。自然 界中树和森林是不同的概念，但在数据结构中，树和森林只 有很小的差别。任何一棵树，删去根结点就变成了森林
7.1.2树的表示 树的表示方法有四种,各用于不同的目的。 1.直观表示法 树的直观表示法就是以倒着的分支树的形式表示,下 图就是一棵树的直观表示。其特点就是对树的逻辑结构的描 述非常直观。是数据结构中最常用的树的描述方法 2021年1月21日
2021年1月21日 数据结构讲义 8 7.1.2 树的表示 树的表示方法有四种，各用于不同的目的。 1．直观表示法 树的直观表示法就是以倒着的分支树的形式表示，下 图就是一棵树的直观表示。其特点就是对树的逻辑结构的描 述非常直观。是数据结构中最常用的树的描述方法
2.嵌套集合表示法 所谓嵌套集合是指一些集合的集体,对于其中任何两个 集合,或者不相交,或者一个包含另一个。用嵌套集合的 形式表示树,就是将根结点视为一个大的集合,其若干棵 子树构成这个大集合中若干个互不相交的子集,如此嵌套 下去,即构成一棵树的嵌套集合表示。下图就是一棵树的 嵌套集合表示。 F 2021年1月21日
2021年1月21日 数据结构讲义 9 2．嵌套集合表示法 所谓嵌套集合是指一些集合的集体，对于其中任何两个 集合，或者不相交，或者一个包含另一个。用嵌套集合的 形式表示树，就是将根结点视为一个大的集合，其若干棵 子树构成这个大集合中若干个互不相交的子集，如此嵌套 下去，即构成一棵树的嵌套集合表示。下图就是一棵树的 嵌套集合表示
3.凹入表示法 树的凹入表示法如左图所示。 ABDHI 4.广义表表示法 树用广义表表示,就是将根作为 由子树森林组成的表的名字写在表 的左边,这样依次将树表示出来 (A(BE(HDF),C(GD) 2021年1月21日 数据结构讲义 10
2021年1月21日 数据结构讲义 10 3．凹入表示法 树的凹入表示法如左图所示。 4．广义表表示法 树用广义表表示，就是将根作为 由子树森林组成的表的名字写在表 的左边，这样依次将树表示出来。 (A(B(D,E(H,I),F),C(G)))