第六章二叉树 1教学内容:6.1定义与性质 6.2存储实现基本操作的实现 6.3二叉树的遍历 64线索二叉树 6.5二又树的应用 2教学目的:①深刻理解一义树的定义c质及其存 储方法 (2)熟练掌握二叉树的链表方式 结点结构和类型定义 (3)理解并掌握二叉树的 (4)掌握二叉树的线索代 5)灵活运用二又树的热相关 的应用问题 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 1 第六章 二叉树 ⒈教学内容： 6.1 定义与性质 6.2 存储实现基本操作的实现 6.3 二叉树的遍历 6.4 线索二叉树 6.5 二叉树的应用 ⒉教学目的： ⑴ 深刻理解二叉树的定义、性质及其存 储方法； ⑵ 熟练掌握二叉树的二叉链表存储方式、 结点结构和类型定义； ⑶ 理解并掌握二叉树的三种遍历算法； ⑷ 掌握二叉树的线索化方法； ⑸ 灵活运用二叉树的遍历方法解决相关 的应用问题；
3教学重点:(1)二叉树的定义、逻辑特点及性质,在三叉 树上定义的基本运算 (2)二叉树的链式存储结构及其类型说明, 叉树的顺序存储结构及其 类型说明 (3)二叉树链式存储结构的组织方式 (4)二叉树的三种遍历方法及其算法; (5)以遍历为基础在二叉树上实现的几种运算 (6)哈夫曼树和哈夫曼算法; 4教学难点:(1)二叉树的递归定义 (2)二叉树链式存储结构的组织方式 (3)三种遍历的主要区别: 4)二叉树上的复杂运算 (5)哈夫曼算法及其应用 5学时安排:10学时 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 2 ⒊教学重点：⑴二叉树的定义、逻辑特点及性质，在二叉 树上定义的基本运算； ⑵二叉树的链式存储结构及其类型说明，二 叉树的顺序存储结构及其 类型说明； ⑶二叉树链式存储结构的组织方式； ⑷二叉树的三种遍历方法及其算法； ⑸以遍历为基础在二叉树上实现的几种运算； ⑹哈夫曼树和哈夫曼算法； ⒋教学难点：⑴二叉树的递归定义； ⑵二叉树链式存储结构的组织方式； ⑶三种遍历的主要区别； ⑷二叉树上的复杂运算； ⑸哈夫曼算法及其应用； ⒌学时安排： 10学时
6.1定义与性质 二叉树的基本概念 ◆二叉树的主要性质 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 3 6.1 定义与性质 二叉树的基本概念 二叉树的主要性质
1.二叉树 二叉树( Binary Tree)是个有限元素的集合,该集 合或者为空、或者由一个称为根roo的元素及两个不 相交的、被分别称为左子树和右子树的二叉树组成。当 集合为空时,称该二叉树为空二叉树。在二叉树中, 个元素也称作一个结点。 二叉树是有序的,即若将其左、右子树颠倒,就成 为另一棵不同的二叉树。即使树中结点只有一棵子树, 也要区分它是左子树还是右子树。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 4 1．二叉树 二叉树（Binary Tree）是个有限元素的集合，该集 合或者为空、或者由一个称为根(root)的元素及两个不 相交的、被分别称为左子树和右子树的二叉树组成。当 集合为空时，称该二叉树为空二叉树。在二叉树中，一 个元素也称作一个结点。 二叉树是有序的，即若将其左、右子树颠倒，就成 为另一棵不同的二叉树。即使树中结点只有一棵子树， 也要区分它是左子树还是右子树
因此二叉树具有五种基本形态,如图所示 左子树 左子树 左子树)(左子树 二叉树的五种基本形态 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 5 • 因此二叉树具有五种基本形态，如图所示