第七章树与森林第七章树与森林⒈教学内容：7
1树的概念与表示7
2基本操作与存储7
3树、森林与二叉树的转换7
4树或森林的遍历7
5树的应用⒉教学目的：⑴深刻理解树的定义、术语；⑵领会并掌握树的各种存储结构；⑶熟练掌握森林与二叉树间的相互转换；⑷领会树和森林的遍历；⑸了解树的简单应用
⒊教学重点：⑴树的存储结构；⑵森林与二叉树的转换
⒋教学难点：⑴森林与二叉树的转换；⑵判定树；⑶等价关系与等价类问题
⒌学时安排：4学时7
1树的概念与表示树的概念与表示7
1树的定义及相关术语7
2树的表示7
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＝
