第五章树第五章树第五章树知识点二叉树及二叉树的存储结构二叉树的遍历树的基本概念二叉排序树哈夫曼树难点二叉树遍历算法的设计修改二叉树遍历算法，进行二叉树其它相关的操作，解决实际应用问题要求熟练掌握以下内容:理解树形结构的基本概念和术语二叉树定义和存储结构二叉树的遍历次序及二叉树遍历算法了解以下内容：树和二叉树之间的相互转换方法线索二叉树的建立及遍历算法树的应用：二叉排序树和哈夫曼树第五章目录第五章目录5.1树的定义和基本术语5.2二叉树5.3二叉树的遍历5.4线索二叉树5.5树的应用5.6应用实例及分析小结习题与练习5.1.15.1.1树的定义树的定义树是n个结点的有限集合T，在一棵非空树中（n>0）有且仅有一个称作根的结点；其余结点可分为m个（m≥0）互不相交的集合T1，T2……Tm，其中，每一个集合本身又是一棵树,并称为根的子树。当n=0时，称为空树。有限集合T1，T2……Tm应该“互不相交”，即任意两个集合不能有相重的结点。树的各个结点有不同层次关系，这种关系通常用图形表示，但与自然界的树木相反，习惯上将整棵树的根画在最上层，如图5.1所示。图图5.15.1树的表示法树的表示法NoImage5.1.25.1.2基本术语基本术语1.结点的度：树中每个结点具有的子树数或者后继结点数称为该结点的度（Degree）。度数为0的结点，即没有子树的结点叫作端结点或叶子结点。一棵树中各个结点度数的最大值叫做这个树的度。2.儿子结点和父亲结点：一个结点的子树的根或者后继结点称为该结点的儿子结点，反之，该结点则称为其后继结点的父亲结点。3.兄弟结点：同一个结点的儿子结点之间互称为兄弟结点。4.子孙结点和祖先结点：一个结点的子树中所有结点均称之为该结点的子孙结点。反之，从根结点到达一个结点的路径上的所有结点，都叫做该结点的祖先结点。5.树的深度：树是一种层次结构，树中结点的层次（Level）是从根结点算起的。根结点为第一层，其儿子结点为第二层。其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度或高度。6.森林：n个树的集合叫森林(Forest)。树形结构的逻辑特征树形结构的逻辑特征树形结构的逻辑特征可用树中结点之间的父子关系来描述：树中任一结点都可以有零个或多个直接后继结点（即儿子结点），但至多只能有一个直接前趋结点（即父亲结点）。树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点。树形结构是非线性结构。返回5.2.15.2.1二叉树的定义及其性质二叉树的定义及其性质一个二叉树是n个结点的有限集合（n≥0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。由上述定义可知，二叉树可以是空集，其根可以有空的左子树或右子树，或者左、右子树皆为空。一般地，二叉树有五种基本形态，如图5.2所示。图图5.25.2二叉树的基本形态二叉树的基本形态(a)空二叉树(b)仅有一个根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左、右子树均非空的二叉树(a)○A(b)○B○A(c)○B○A(d)○B○A○C(e)1.1.满二叉树满二叉树在一个二叉树中，若第i层的结点数为2i-1，则称此层的结点数是满的，当树中的每一层都是满的，则称此二叉树为满二叉树。即如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。满二叉树的第一层有一个结点（即根结点），第二层有两个结点，依此类推。每一层的结点数都是上一层结点数的二倍。所以，在满二叉树的第i层共有2i-1个结点（i≥1），一个深度为h的满二叉树的结点总数为2h-1。图图5.35.3满二叉树满二叉树NoImage2.2.完全二叉树完全二叉树如果一个二叉树各层都是“满”的，只是最下面一层从右边起连续缺n个结点，这种二叉树叫做完全二叉树。例如图5.3中的满二叉树，如果缺少从第11号至第15号结点（没有图中虚框里的几个结点），就是一个完全二叉树。对于完全二叉树，对其结点采用“按层编号”比较方便，即从根结点开始由上而下逐层给结点编号，同一层的结点由左向右编号。对于完全二叉...
