数据结构与算法 Java版 教学课件 ppt 作者罗文劼 第4章 树结构.ppt

文档介绍：第4章树结构*、二叉树的遍历及其应用、线索二叉树、哈夫曼树及哈夫曼编码、树和森林与二叉树之间的转换、树或森林的遍历。⒉教学目的深刻理解二叉树的定义、性质及其存储方法;熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义;掌握二叉树的三种遍历算法;了解二叉树的线索化方法;灵活运用二叉树的遍历方法解决相关的应用问题;掌握森林与二叉树间的相互转换;掌握树和森林的遍历方法。*⒊教学重点:二叉树的定义、逻辑特点及性质;二叉树的存储结构;二叉树的遍历方法及其算法;以遍历为基础在二叉树上实现的几种运算;哈夫曼树和哈夫曼算法;树的存储结构;森林与二叉树的转换。⒋教学难点:二叉树的递归定义;二叉树链式存储结构的组织方式;三种遍历的算法;二叉树上的复杂运算;哈夫曼算法及其应用;* ,然而在现实生活中或数学抽象中还有一种情况是元素至多有一个前驱元素,而可有多个后继元素的情况,我们称之为树结构。看下面这些问题,它们涉及的数据元素之间的关系是怎样的:问题1:组织结构层次关系的存储与查找。问题2:家族族谱中家族成员之间的关系表示与查找。问题3:图书馆中图书的分类关系的建立。。。。。。。*(BinaryTree)是个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个结点。*(Tree)是n(n≥0)个有限数据元素的集合。当n=0时,称这棵树为空树。在一棵非空树T中:(1)有一个特殊的数据元素称为树的根结点,根结点没有前驱结点。(2)若n>1,除根结点之外的其余数据元素被分成m(m>0)个互不相交的集合T1,T2,…,Tm,其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1,T2,…,Tm称为这个根结点的子树。**树具有下面两个特点:⑴树的根结点没有前驱结点,除根结点之外的所有结点有且只有一个前驱结点。⑵树中所有结点可以有零个或多个后继结点。由此特点可知,下图所示的都不是树结构。*满二叉树在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子结点都在同一层上,这样的一棵二叉树称作满二叉树。*完全二叉树一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。