第六章二叉树 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 • 因此二叉树具有五种基本形态，如图所示
2.二叉树的相关概念 中(1)结点的度。结点所拥有的子树的个数称为该结点 的度。 (2)叶结点。度为0的结点称为叶结点,或者称为终端 结点 (3)分枝结点。度不为0的结点称为分支结点,或者称 为非终端结点。一棵树的结点除叶结点外,其余的都是分 支结点 (4)左孩子、右孩子、双亲、兄弟。树中一个结点的 子树的根结点称为这个结点的孩子。在二叉树中,左子树 的根称为左孩子,右子树的根称为右孩子。这个结点称为 它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄 弟 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 6 2．二叉树的相关概念 (1）结点的度。结点所拥有的子树的个数称为该结点 的度。 （2）叶结点。度为0的结点称为叶结点，或者称为终端 结点。 （3）分枝结点。度不为0的结点称为分支结点，或者称 为非终端结点。一棵树的结点除叶结点外，其余的都是分 支结点。 （4）左孩子、右孩子、双亲、兄弟。树中一个结点的 子树的根结点称为这个结点的孩子。在二叉树中，左子树 的根称为左孩子，右子树的根称为右孩子。这个结点称为 它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄 弟
(5)路径、路径长度。如果一棵树的一串结点 n1n2…n有如下关系:结点n是n+1的父结点(1≤ik), 就把n,n2,n称为一条由n至n的路径。这条路径的长 度是k-1 (6)祖先、子孙。在树中,如果有一条路径从结点M 到结点N,那么M就称为N的祖先,而N称为M的子孙。 (7)结点的层数。规定树的根结点的层数为1,其余 结点的层数等于它的双亲结点的层数加1。 (8)树的深度。树中所有结点的最大层数称为树的深 度 (9)树的度。树中各结点度的最大值称为该树的度。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 7 （ 5 ） 路 径 、 路 径长 度 。 如 果 一棵 树 的 一 串 结 点 n1 ,n2 ,…,nk有如下关系：结点ni是ni+1的父结点（1≤i<k）, 就把n1 ,n2 ,…,nk称为一条由n1至nk的路径。这条路径的长 度是k-1。 （6）祖先、子孙。在树中，如果有一条路径从结点M 到结点N，那么M就称为N的祖先，而N称为M的子孙。 （7）结点的层数。规定树的根结点的层数为1，其余 结点的层数等于它的双亲结点的层数加1。 （8）树的深度。树中所有结点的最大层数称为树的深 度。 （9）树的度。树中各结点度的最大值称为该树的度
(10)满一叉权 在一棵二叉树中,如果所有分支结点都存在左子树 和右子树,并且所有叶子结点都在同一层上,这样的 棵二叉树称作满二叉树。如图所示,(a)图就是 棵满二叉树,(b)图则不是满二叉树,因为,虽然其 所有结点要么是含有左右子树的分支结点,要么是叶 子结点,但由于其叶子未在同一层上,故不是满二叉 树。 B c 5 6@7 D4@506⊙7 B60000 891011 12131415 (a)一棵满二叉树 (b)一棵非满二又树 满二叉树和非满二叉树示意图 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 8 （10）满二叉树。 在一棵二叉树中，如果所有分支结点都存在左子树 和右子树，并且所有叶子结点都在同一层上，这样的 一棵二叉树称作满二叉树。如图所示，（a）图就是一 棵满二叉树，（b）图则不是满二叉树，因为，虽然其 所有结点要么是含有左右子树的分支结点，要么是叶 子结点，但由于其叶子未在同一层上，故不是满二叉 树
(11)完全二叉树。 棵深度为k的有n个结点的二叉树,对树中的结点按从 止上至下、从左到右的顺序进行编号,如果编号为i( ≤i≤n)的结点与满二叉树中编号为的结点在二叉树中 的位置相同,则这棵二叉树称为完全二叉树。完全二叉树 的特点是:叶子结点只能出现在最下层和次下层,且最下 层的叶子结点集中在树的左部。显然,一棵满二叉树必定 是一棵完全二叉树,而完全二叉树未必是满二叉树。如图 所示(a)为一棵完全二叉树,(b)不是完全二叉树 (a)一棵完全二叉树 b)一棵非完全二叉树 完全二又树和非完全二叉树示意图 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 9 (11) 完全二叉树。 一棵深度为k的有n个结点的二叉树，对树中的结点按从 上至下、从左到右的顺序进行编号 ，如果编号为i（ 1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中 的位置相同，则这棵二叉树称为完全二叉树。完全二叉树 的特点是：叶子结点只能出现在最下层和次下层，且最下 层的叶子结点集中在树的左部。显然，一棵满二叉树必定 是一棵完全二叉树，而完全二叉树未必是满二叉树。如图 所示（a）为一棵完全二叉树，（b）不是完全二叉树
6.1.2二叉树的主要性质 ◆性质1一棵非空二叉树的第层上最多有21个结点 (i≥1)。 该性质可由数学归纳法证明。证明略。 ◆性质2一棵深度为k的二叉树中,最多具有2k-1个结 点。 证明设第层的结点数为X(1≤i≤k),深度为k的二 叉树的结点数为M,X最多为21,则有: M=∑x221=2-1 2021年1月21日 数据结构讲义 10
2021年1月21日 数据结构讲义 10 6.1.2 二叉树的主要性质 性质1 一棵非空二叉树的第i层上最多有2 i-1个结点 （i≥1）。 该性质可由数学归纳法证明。证明略。 性质2 一棵深度为k的二叉树中，最多具有2 k－1个结 点。 证明 设第i层的结点数为xi（1≤i≤k），深度为k的二 叉树的结点数为M，xi最多为2 i-1 ，则有：