第六章树和二叉树6.4.3树和森林的遍历6.6赫夫曼树及其应用6.6.1最优二叉树（赫夫曼树）6.6.2赫夫曼编码树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。6.1树的定义和基本术语定义：树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…TmT1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。如图6.1树还有其他的表示形式，如图6.2的三种表示法：（1）嵌套集合（2）广义表的形式（3）凹入表示法下面是树结构的一些基本术语：度：结点拥有的子树称为结点的度。叶子（终端结点）：度为0的结点。其余结点称为非终端结点或分支结点。树的度：树内各结点的度的最大值。孩子：结点的子树的根称为该结点的孩子。相应地，该结点称为双亲。同一个双亲的孩子称为兄弟。依此可以递归定义祖先和子孙的概念。结点的层次：从根开始定义，根为第一层，根的孩子为第二层。若某个结点在第l层，则其子树的根就在第l+1层。双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度或高度。有序树：如果该树中结点的各子树看成从左至右是有次序的，则该树称为有序树。否则称为无序树。森林：是m（m>=0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，可以森林和树相互递归的定义来描述树。Tree=(root,F)，其中F是m棵树的森林。F=(T1,T2,T3…Tm)，其中Ti称做根root的第i棵子树。6.2二叉树二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。图6.8列出二差树的5种基本形态，图6.8(C)和图6.8（d）是不同的两棵二叉树。6.2.2二叉树的性质二叉树具有下列重要性质：性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)。采用归纳法证明此性质。当i=1时，只有一个根结点，2i-1=20=1,命题成立。现在假定对于所有的j，1<=j<i,命题成立，即第j层上至多有2j-1个结点，那么可以证明j＝i时命题也成立。由归纳假设可知，第i－1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i－1层上最大结点数的二倍，即2×2i-2＝2i-1。命题得到证明。性质2：深度为k的二叉树至多有2k－1个结点（k>=1).深度为k的二叉树的最大的结点数`为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数：EkI=1（第i层上的最大结点数）=EkI=12i-1=2k–1性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：N＝n0＋n1＋n2(6-1)再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：N＝B＋1。由于这些分支都是由度为1和2的结点射出的，所有有：B＝n1+2*n2N＝B＋1＝n1＋2×n2＋1（6－2)由式（6－1）和（6－2）得到：n0+n1+n2=n1+2*n2+1n0＝n2＋1下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。下图6.9就是一棵满二叉树，对结点进行了顺序编号。如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，1完全二叉树的特点是：（1)所有的叶结点都出现在第k层或k－1层。（2）任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l＋1。性质4：具有n个结点的完全二叉树的深度为【log2n】＋1。符号【x】表示不大于x的最大整数。假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1<n<=2k-1或2k-1<=n<2k取对数得到：k－1<=log2n<k因为k是整数。所以有：k＝【log2n】＋1。性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第【log2n】+1层，每层从左到右),则对任一结点i（1