第四章 树和二叉树内容概述树是一种非线性数据结构。树结构经常用于描述和处理数据元素的层次关系，尤其适用于大规模的信息处理任务，例如建立数据库管理系统时所用的层次模型就是一种树型结构。本章主要以二叉树为例，讲述树结构及其应用，主要内容包括：（1）树的定义、术语及性质；（2）二叉树的定义、性质，二叉树的存储结构及二叉树的遍历等各种操作的算法实现；（3）线索二叉树；（4）树、森林与二叉树的转化；（5）赫夫曼树及其应用。重点与难点重点包括：二叉树的性质及遍历算法，线索二叉树的运算，树、森林与二叉树之间的转换，Huffman树的构造算法及Huffman编码、译码。难点包括：二叉树的遍历算法，尤其是非递归遍历算法，线索二叉树的运算，Huffman编码、译码。思考1树型结构的结构特点2树和二叉树的主要差别表现在哪些方面？3二叉树具有那些重要特性？4二叉树有哪些遍历策略？如何利用算法实现？5已知某二叉树的后序遍历序列和中序遍历序列，如何求解出其前序遍历序列。6已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。7有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的赫夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的赫夫曼编码。第一节树树是一种非线性数据结构，这种非线性结构有哪些特点？具有那些特有性质？如何描述树结构？本节从树的定义、抽象类型定义、树的基本概念与相关术语、树的性质、树的表示等方面阐述上述问题。1、树的递归与非递归定义1.树的递归定义树(Tree)是n(n0)个结点的有限集合T，不含有任何结点（元素）的树称为空树，否则它满足如下两个条件：有且仅有一个称为根(Root)的结点；其余所有结点被分成m(m0)个互不相交的集合T1,T2,T3,Tm，其中每个集合又构成一棵树，称其为根结点的子树(SubTree)。树的根结点Root是每棵子树根结点的前驱，每棵子树的根结点是根结点Root的后继。例如，在图4.1中，(a)表示只有一个根结点的树；(b)表示有8个结点的树，其中A是根结点，其余结点分成3个互不相交的子集：T1=B,E,F,G,T2=C,T3=D,H。T1、T2和T3都是根结点A的子树，且本身也是一棵树。如T1的根结点为B，其余结点分为3个互不相交的子集：T11=E,T12=F,T13=G。T11、T12和T13都是T1的根结点B的子树。2.树的非递归定义树是n(n0)个结点的有限集合T，不含有任何结点（元素）的树称为空树，而在任一非空树中定义了一个关系，它满足：（1）T中存在唯一的一个结点，它没有前驱，称为树的根；（2）除根结点外，T中每一个结点都有且仅有一个前驱结点；（3）除根结点外，T中每一个结点a，都存在一个从根结点到a的结点序列a1ak,使得a1为根结点，ak=a，而结点ai+1是ai的后继（1ik-1），这个结点序列称为从根结点到结点a的路径。例如，在图4.1(b)中，A为树的根结点。对于结点G，存在一个结点序列ABG，使得A为根结点，B为A的后继，G为B的后继，这个序列就是从根结点A到结点G的路径。2、树的抽象数据类型2、树的抽象数据类型树的抽象数据类型定义如下：ADTTree数据对象D：D=ai|aiElemSet,i=1,2,n,n0数据关系R：若D为空集，则称为空树。若D仅含一个数据元素，则R为空集，否则RH，H满足关系：(1)T中存在唯一的一个结点，它没有前驱，称为树的根，用root表示，在集合D中用a1表示；(2)若D中元素个数大于1，对于任意的数据元素ajD且j2，存在唯一的数据元素aiD，有H；(3)若D中元素个数大于1，对于任意的数据元素ajD，存在k个(k0)数据元素aiD且ij，有H；(4)对于任意的数据元素ajD且j2，存在DjD，Dj=|ElemSet,k=1,2,m,m0，有唯一的Pj=,，这个集合Pj表示从根结点到结点aj的一条路径。基本操作P：InitTree(&T);操作结果：构造空树T。CreateTree(&T,tree);初始条件：tree给出T的表示形式。操作结果：按tree构造T。TreeEmpty(T);初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则返回FALSE。TreeDepth(T);初始条件：树T存在。操作结果：返回T的深度。Root(T);初始条件：树T存在。操作结果：返回T的根。Value(T,e);初始条件：树T存在，e是需寻找的结点的值。操作结果：若找到该结点，则函数返回TRUE，否则返回FALSE。Assign(T,e,value);初始条件：树T存在，e是需寻找的结点的值。操作结果：若找到该结点，则结点e赋值为value，函数返回TRUE，否则返回FALSE。Parent(T,e,&P);初始条件：树T存在，e是需寻找的结点的值。操作结果：若树中存在值为e的结点，则函数返回TRUE，否则返回FALSE；若存在该结点，用P返回双亲结点的位置，若结点为根结点，则P返回空。DelTreeNode(&T,P);初始条件：树T存在，P指向该二叉树中的一个结点。操作结果：删除P所指向的结点及其子树。TraverseTree(T,visit();初始条件：树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。ClearTree(&T);初始条件：树T存在。操作结果：将树T清空。DestroyTree(&T);初始条件：树T存在。操作结果：将树T销毁。ADTTree该抽象数据类型中，定义了树的若干基本操作，另外，对树的操作还可有插入结点操作、插入子树操作、旋转树操作等3、树的基本术语3、树的基本术语（树结点、叶子结点、分支结点、度、深度）树的结点树的结点包含一个数据元素及若干指向其子树的分支。结点的度和树的度树中每个结点所拥有的非空子树数称为结点的度（Degree）。树的度是树中所有结点的度的最大值。如在图4.1(b)中，结点A、B的度均为3，结点D的度为1，其余结点的度均为0。因为所有结点的度的最大值为3，故树的度为3。叶子结点和分支结点树中度为0的结点称为叶子结点或终端结点，度大于0的结点称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。在分支结点中，每个结点的分支数就是该结点的度数。度为1的结点，其分支数为1，称为单分支结点；度为2的结点，其分支数为2，称为双分支结点，其余类推。如在图4.1(b)中，结点C、E、F、G、H都是叶子结点，A、B、D都是分支结点，其中A和B是多分支结点，D是单分支结点。子结点、双亲结点和兄弟结点树中每个结点的子树的根（即每个结点的后继）称为该结点的孩子、儿子或子女（Child），相应地，该结点称为子结点的双亲（Parent）。具有同一个双亲的孩子之间互称兄弟（Brothers）。双亲在同一层上的结点互称为堂兄弟。以某结点为根的子树中任一结点都称为该结点的子孙，相应地，结点的祖先是从根到该结点的路径上经过的所有分支结点。在一棵树中，根结点没有双亲结点，叶子结点没有子结点，其余结点都既有双亲结点也有子结点。如在图4.1(b)中，结点B的孩子为结点E、F、G，双亲为结点A；而E、F、G互为兄弟，结点B的子孙为结点E、F、G，结点E的祖先为结点A、B。结点的层数和树的深度树既是一种递归结构，也是一种层次结构。结点的层数（Level）从根开始定义起，根结点为第一层，它的子结点为第二层，以此类推。如果某个结点在第k层，则其子树的根位于第k+1层。树中结点的最大层数称为树的深度（Depth）或高度。如在图4.1(b)中，结点A为第一层，B、C、D为第二层，E、F、G、H为第三层，树中结点的最大层数是3，故树的深度为3。有序树和无序树如果树中各结点的子树是按照一定的次序从左向右安排的，则称该树为有序树，否则称之为无序树。在有序树中，最左边的子树的根称为第一个孩子，最右边的子树的根称之为最后一个孩子。任何无序树都可以当作是任一次序的有序树来处理，如一个单位的机构设置可用树来表示，若各层机构是按照一定的次序排列的，则为一棵有序树，否则为无序树。森林（Forest）是m（m0）棵互不相交的树的集合。对于树中每个分支结点来说，其子树的集合就是森林。如在图4.1(b)中，由结点A的子树所构成的森林为T1,T2,T3，由结点B的子树所构成的森林为T11,T12,T13。4、树的性质4、树的性质性质1：树中的结点数等于所有结点的度数加1。根据树的定义，在一个树中，除了根结点以外，其他每个结点都有且只有一个前驱结点，即每个结点与指向它的一个分支一一对应，所以除了根结点以外的结点数等于所有结点的分支数（即度数），因此可得出树中的结点数等于所有结点的度数加1。性质2：度为k的树中第i层上至多有ki-1个结点（i1）。利用数学归纳法可以证明此性质。对于第一层显然是成立的。因为树中的第一层上只有根结点，而i=1时，ki-1=k0=1，同样也得到只有一个结点。假设对于第i-1层（i1）命题成立，即度为k的树中第i-1层上至多有k(i-1)-1=ki-2个结点，则根据树的度的定义，度为k的树中每个结点至多有k个孩子，所以第i层上的最大结点数为第i-1层上的最大结点数的k倍，即ki-2k=ki-1个，故结论成立。性质3：深度为h的k叉树至多有（kh-1）/（k-1）个结点。由性质2可知，当深度为h的k叉树（即度为k的树）上每一层都达到最多结点数时，所有结点的总和为：，故深度为h的k叉树至多有个结点。当一棵k叉树上的结点数等于时，即k叉树的结点数达到了最大值时，则称该树为满k叉树。这种树的特点是每一层上的结点数都是最大结点数。性质4：具有n个结点的k叉树的最小深度为。（其中符号表示对x进行向上取整，如。）假设具有n个结点的k叉树的深度为h，若在该树中前h-1层都是满的，即第i层的结点数等于ki-1个（1ih-1），最后一层即第h层的结点数可能满也可能不满，则该树具有最小的深度。根据性质3有：，即。以k为底取对数后得。所以，。因此得到具有n个结点的一般k叉树的最小深度是。第二节二叉树二叉树是使用最广泛的树型结构，这是因为一方面应用中有许多问题都可以通过二叉树来解决，另一方面一般树的问题也可转化为二叉树的问题来简便处理。那么，二叉树具有那些性质？如何存储表示和实现二叉树？1、二叉树的抽象数据类型定义1、二叉树的抽象数据类型定义所谓二叉树，是指结点的一个有限集合，它或为空集，或为满足下列性质的非空集合：有且只有一个根结点，其余结点分成左右两个互不相交的集合TL、TR，且TL、TR均为二叉树。直观上，二叉树就是一个最多有两个分支的树。在二叉树中，每个结点的左子树的根结点被称为该结点的左孩子（LeftChild），右子树的根结点被称为该结点的右孩子（RightChild）。二叉树的左右子树次序不能任意颠倒。二叉树与一般树的区别在于二叉树的子树有左右之分，以及二叉树定义中对树的度数的限制（即二叉树中不存在度大于