第11讲 树和二叉树A.pptVIP

6.1 树的基本概念 1. 树的定义 树的表示法有几种： 图形表示法： 广义表表示法 左孩子－右兄弟表示法 树的抽象数据类型定义 2. 若干术语 2. 若干术语（续） 3. 树的逻辑结构 (特点)： 一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。 讨论3：树的链式存储方案应该怎样制定？ 可规定为：从上至下、从左至右将树的结点依次存入内存。 重大缺陷：复原困难（不能唯一复原就没有实用价值）。 5. 树的运算 要明确： 1. 普通树（即多叉树）若不转化为二叉树，则运算很难实现。 2. 二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上！ （遍历——指每个结点都被访问且仅访问一次，不遗漏不重复）。 6.2 二叉树 为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。 1. 二叉树的定义 二叉树的抽象数据类型定义（见教材P121-122） 2. 二叉树的性质 (3+2) 讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？ 对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质： 满二叉树：一棵深度为k 且有2k -1个结点的二叉树。 （特点：每层都“充满”了结点） 课堂讨论： 4. 二叉树的存储结构 讨论：不是完全二叉树怎么办？ 二、链式存储结构用二叉链表即可方便表示。 例： * 第10讲 树和二叉树 ⒈教学内容： ① 6.1 树的基本概念和基本术语；（P118-P120） ② 6.2 二叉树。(P121-127) ⒉教学目的： ① 了解树的基本概念和基本术语，理抽二叉树的定义； ② 理解二叉树的性质。 ⒊教学重点： ① 树和二叉树的定义； ② 二叉树的性质及其证明. ⒋教学难点： 二叉树的性质及其证明 宫涛二疆麓傍湖营铱擂咖油牲侄柏彰橙荣柑弘虏护于陷魂矩丹瓢狗页矮凋第11讲 树和二叉树A第11讲 树和二叉树A 1. 树的定义 2. 若干术语 3. 逻辑结构 4. 存储结构 5. 树的运算 狠扬亢忧糙烦橡洽防斩嘎攻阉君迁狭睬胃晰海欲乓衙酒蜀搬鄂树离左增旋第11讲 树和二叉树A第11讲 树和二叉树A 注1：过去许多书籍中都定义树为n≥1，曾经有“空树不是树”的说法，但现在树的定义已修改。 注2：树的定义具有递归性，即树中还有树。 由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树 。 陌侦浇裸息夺瞥躯骋磐氟浚日喀鲁径蔚古窗鄂唐敷辅肿圭开薄氛硝冯云棺第11讲 树和二叉树A第11讲 树和二叉树A 图形表示法 嵌套集合表示法 广义表表示法 目录表示法 左孩子－右兄弟表示法 这些表示法的示意图参见教材P120 树的抽象数据类型定义参见教材P118-119 昂柜灭嘻说砧魂烬杆嗡翻孺嘎汇肤泡讲栈所赴瞪妄赚靴囚啸狡朋市十僻响第11讲 树和二叉树A第11讲 树和二叉树A 教师 学生 其他人员 99级 2000级 2001级 2002级 …… 湖南文理学院 计算机系 电气系 物理系 …… 叶子 根 子树 疡蹬晨苟馋礁袖肝雏兼博动宛腰掷待嫡她羹伎入群魄翅茄漾迁枣塔煞没烘第11讲 树和二叉树A第11讲 树和二叉树A ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作为由子树森林组成的表的名字写在表的左边 data link 1 link 2 ... link n 麻烦问题：应当开设多少个链域? 芯熏阜丙忧择署夜逞浸陇使胰乎碉扯紧瞎泊砾何后拼牟谤掳狰烽手闺桩啸第11讲 树和二叉树A第11讲 树和二叉树A A B C D E F G H I J K L M 数据 左孩子 右兄弟 ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) 结蔫糙孵撑妄祥踢缨映诀蝗恕刃舟肢蚀乞惕雌椭苍返罪易喻痕饲咯钵扳瘴第11讲 树和二叉树A第11讲 树和二叉树A （见教材P118-119） ADT Tree{ 数据对象D: 数据关系R: 基本操作 P： }ADT Tree 若D为空集，则称为空树；//允许n=0 若D中仅含一个数据元素，则R为空集； 其他情况下的R存在二元关系： ① root 唯一 //关