第4章树结构第2页1．教学内容二叉树和树的概念、二叉树的遍历及其应用、线索二叉树、哈夫曼树及哈夫曼编码、树和森林与二叉树之间的转换、树或森林的遍历。⒉教学目的深刻理解二叉树的定义、性质及其存储方法；熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义；掌握二叉树的三种遍历算法；了解二叉树的线索化方法；灵活运用二叉树的遍历方法解决相关的应用问题;掌握森林与二叉树间的相互转换；掌握树和森林的遍历方法。第3页⒊教学重点：二叉树的定义、逻辑特点及性质；二叉树的存储结构；二叉树的遍历方法及其算法；以遍历为基础在二叉树上实现的几种运算；哈夫曼树和哈夫曼算法；树的存储结构；森林与二叉树的转换。⒋教学难点：二叉树的递归定义；二叉树链式存储结构的组织方式；三种遍历的算法；二叉树上的复杂运算；哈夫曼算法及其应用；第4页4.1引言4.1.1问题提出线性结构是指元素之间至多有一个前驱元素或一个后继元素的情况，然而在现实生活中或数学抽象中还有一种情况是元素至多有一个前驱元素，而可有多个后继元素的情况，我们称之为树结构。看下面这些问题，它们涉及的数据元素之间的关系是怎样的：问题1：组织结构层次关系的存储与查找。问题2：家族族谱中家族成员之间的关系表示与查找。问题3：图书馆中图书的分类关系的建立。。。。。。。第5页1．二叉树的定义二叉树（BinaryTree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。4.1.2相关概念第6页2．树的定义树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0时，称这棵树为空树。在一棵非空树T中：(1)有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。(2)若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1,T2,…,Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1,T2,…,Tm称为这个根结点的子树。第7页第8页树具有下面两个特点：⑴树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。⑵树中所有结点可以有零个或多个后继结点。由此特点可知，下图所示的都不是树结构。第9页满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。第10页完全二叉树一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。第11页4.2.1二叉树的基本运算二叉树的基本操作通常有以下几种：(1)Initiate(bt)(2)Create(x,lbt,rbt)(3)InsertL(bt,x,parent)(4)InsertR(bt,x,parent)(5)DeleteL(bt,parent)(6)DeleteR(bt,parent)(7)Search(bt,x)(8)Traverse(bt)4.2二叉树第12页4.2.2二叉树的主要性质性质1一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。性质2一棵深度为k的二叉树中，最多具有2k－1个结点。性质3对于一棵非空的二叉树，若叶子结点数为n0，度数为2的结点数为n2，则有：n0＝n21。性质4具有n个结点的完全二叉树的深度k为：log2n+1第13页性质5:对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：⑴如果i>1，则序号为i的结点的双亲结点的序号为i/2；如果i＝1，则序号为i的结点是根结点，无双亲结点。⑵如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则序号为i的结点无左孩子。⑶如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1>n，则序号为i的结点无右孩子。此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为(i－1)/2，左孩子的编号为2i＋1，右孩子的编号为2i＋2。第14页4.2.3二叉树的存储1．顺序存储结构所谓二叉树的顺序存储，是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。因此...
