山大《数据结构》讲义04树和二叉树

1、第四章 树和二叉树内容概述树是一种非线性数据结构。树结构经常用于描述和处理数据元素的层次关系，尤其适用于大规模的信息处理任务，例如建立数据库管理系统时所用的层次模型就是一种树型结构。本章主要以二叉树为例，讲述树结构及其应用，主要内容包括：（1）树的定义、术语及性质；（2）二叉树的定义、性质，二叉树的存储结构及二叉树的遍历等各种操作的算法实现；（3）线索二叉树；（4）树、森林与二叉树的转化；（5）赫夫曼树及其应用。重点与难点重点包括：二叉树的性质及遍历算法，线索二叉树的运算，树、森林与二叉树之间的转换，Huffman树的构造算法及Huffman编码、译码。难点包括：二叉树的遍历算法，尤其是非递归

2、遍历算法，线索二叉树的运算，Huffman编码、译码。思考1树型结构的结构特点2树和二叉树的主要差别表现在哪些方面？3二叉树具有那些重要特性？4二叉树有哪些遍历策略？如何利用算法实现？5已知某二叉树的后序遍历序列和中序遍历序列，如何求解出其前序遍历序列。6已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。7有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的赫夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的赫夫曼编码。第一节树树是一种非线性数据结构，这种

3、非线性结构有哪些特点？具有那些特有性质？如何描述树结构？本节从树的定义、抽象类型定义、树的基本概念与相关术语、树的性质、树的表示等方面阐述上述问题。1、树的递归与非递归定义1.树的递归定义树(Tree)是n(n0)个结点的有限集合T，不含有任何结点（元素）的树称为空树，否则它满足如下两个条件：有且仅有一个称为根(Root)的结点；其余所有结点被分成m(m0)个互不相交的集合T1,T2,T3,Tm，其中每个集合又构成一棵树，称其为根结点的子树(SubTree)。树的根结点Root是每棵子树根结点的前驱，每棵子树的根结点是根结点Root的后继。例如，在图4.1中，(a)表示只有一个根结点的树；(b

4、)表示有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，都存在一个从根结点到

5、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表示，在集

6、合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为空树，

7、则返回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，否则返回FALS

8、E；若存在该结点，用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该抽象数据类型中，定义了树的若干基本操作，

9、另外，对树的操作还可有插入结点操作、插入子树操作、旋转树操作等3、树的基本术语3、树的基本术语（树结点、叶子结点、分支结点、度、深度）树的结点树的结点包含一个数据元素及若干指向其子树的分支。结点的度和树的度树中每个结点所拥有的非空子树数称为结点的度（Degree）。树的度是树中所有结点的度的最大值。如在图4.1(b)中，结点A、B的度均为3，结点D的度为1，其余结点的度均为0。因为所有结点的度的最大值为3，故树的度为3。叶子结点和分支结点树中度为0的结点称为叶子结点或终端结点，度大于0的结点称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。在分支结点中，每个结点的分支数就是该结点

10、的度数。度为1的结点，其分支数为1，称为单分支结点；度为2的结点，其分支数为2，称为双分支结点，其余类推。如在图4.1(b)中，结点C、E、F、G、H都是叶子结点，A、B、D都是分支结点，其中A和B是多分支结点，D是单分支结点。子结点、双亲结点和兄弟结点树中每个结点的子树的根（即每个结点的后继）称为该结点的孩子、儿子或子女（Child），相应地，该结点称为子结点的双亲（Parent）。具有同一个双亲的孩子之间互称兄弟（Brothers）。双亲在同一层上的结点互称为堂兄弟。以某结点为根的子树中任一结点都称为该结点的子孙，相应地，结点的祖先是从根到该结点的路径上经过的所有分支结点。在一棵树中，根结

11、点没有双亲结点，叶子结点没有子结点，其余结点都既有双亲结点也有子结点。如在图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。有序树和无序树如果

12、树中各结点的子树是按照一定的次序从左向右安排的，则称该树为有序树，否则称之为无序树。在有序树中，最左边的子树的根称为第一个孩子，最右边的子树的根称之为最后一个孩子。任何无序树都可以当作是任一次序的有序树来处理，如一个单位的机构设置可用树来表示，若各层机构是按照一定的次序排列的，则为一棵有序树，否则为无序树。森林（Forest）是m（m0）棵互不相交的树的集合。对于树中每个分支结点来说，其子树的集合就是森林。如在图4.1(b)中，由结点A的子树所构成的森林为T1,T2,T3，由结点B的子树所构成的森林为T11,T12,T13。4、树的性质4、树的性质性质1：树中的结点数等于所有结点的度数加1。根

13、据树的定义，在一个树中，除了根结点以外，其他每个结点都有且只有一个前驱结点，即每个结点与指向它的一个分支一一对应，所以除了根结点以外的结点数等于所有结点的分支数（即度数），因此可得出树中的结点数等于所有结点的度数加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层上的最大结点数为

14、第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层的结

15、点数可能满也可能不满，则该树具有最小的深度。根据性质3有：，即。以k为底取对数后得。所以，。因此得到具有n个结点的一般k叉树的最小深度是。第二节二叉树二叉树是使用最广泛的树型结构，这是因为一方面应用中有许多问题都可以通过二叉树来解决，另一方面一般树的问题也可转化为二叉树的问题来简便处理。那么，二叉树具有那些性质？如何存储表示和实现二叉树？1、二叉树的抽象数据类型定义1、二叉树的抽象数据类型定义所谓二叉树，是指结点的一个有限集合，它或为空集，或为满足下列性质的非空集合：有且只有一个根结点，其余结点分成左右两个互不相交的集合TL、TR，且TL、TR均为二叉树。直观上，二叉树就是一个最多有两个分支的

16、树。在二叉树中，每个结点的左子树的根结点被称为该结点的左孩子（LeftChild），右子树的根结点被称为该结点的右孩子（RightChild）。二叉树的左右子树次序不能任意颠倒。二叉树与一般树的区别在于二叉树的子树有左右之分，以及二叉树定义中对树的度数的限制（即二叉树中不存在度大于2的结点）。下面我们将重点介绍二叉树，这是因为一方面应用中有许多问题都可以通过二叉树来解决，另一方面一般树的问题也可转化为二叉树的问题来简便处理。前面引入的有关树的术语也都适用于二叉树。二叉树的抽象数据类型定义如下：ADTBinaryTree数据对象D：D=ai|aiElemSet,i=1,2,n,n0数据关系R：若

17、D为空集，则称为空二叉树。若D仅含一个数据元素，则R为空集，否则RH，H满足关系：(1)T中存在唯一的一个结点，它没有前驱，称为树的根，用root表示，在集合D中用a1表示；(2)若D中元素个数大于1，对于任意的数据元素ajD且j2，存在唯一的数据元素aiD，有H；(3)若D中元素个数大于1，对于任意的数据元素aiD，仅存在不多于2个数据元素aj,akD且j,ki，有,H，其中，若jK，则称aj为ai的左孩子节点，ak为ai的右孩子节点。(4)对于任意的数据元素ajD且j2，存在DjD，Dj=|ElemSet,k=1,2,m,m0，有唯一的Pj=,，这个集合Pj表示从根结点到结点aj的一条路径

18、。基本操作P：InitBiTree(&T);操作结果：构造空二叉树T。CreateBiTree(&T,tree);初始条件：tree给出二叉树T的表示形式。操作结果：按tree构造二叉树T。BiTreeEmpty(T);初始条件：二叉树T存在。操作结果：若T为空树，则返回TRUE，否则返回FALSE。BiTreeDepth(T);初始条件：二叉树T存在。操作结果：返回T的深度。Root(T);初始条件：二叉树T存在。操作结果：返回T的根。Value(T,e);初始条件：二叉树T存在，e是需寻找的结点的值。操作结果：若找到该结点，则函数返回TRUE，否则返回FALSE。Assign(T,e,va

19、lue);初始条件：二叉树T存在，e是需寻找的结点的值。操作结果：若找到该结点，结点e赋值为value，则函数返回TRUE，否则返回FALSE。Parent(T,e,P);初始条件：二叉树T存在，e是需寻找的结点的值。操作结果：若树中存在值为e的结点，则函数返回TRUE，否则返回FALSE；若存在该结点，用P返回双亲结点的位置，若结点为根结点，则P返回空。LeftChild(T,e,P);初始条件：二叉树T存在，e是需寻找的结点的值。操作结果：若树中存在值为e的结点，则函数返回TRUE，否则返回FALSE；若存在该结点，用P返回左孩子结点的位置，若结点无左孩子结点，则P返回空。RightChi

20、ld(T,e,P);初始条件：二叉树T存在，e是需寻找的结点的值。操作结果：若树中存在值为e的结点，则函数返回TRUE，否则返回FALSE；若存在该结点，用P返回右孩子结点的位置，若结点无右孩子结点，则P返回空。DelBiTreeNode(&T，P);初始条件：二叉树T存在，P指向该二叉树中的一个结点。操作结果：删除P所指向的结点及其子树。TraverseBiTree(T,visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。ClearBiTree(&T);初始条件：

21、二叉树T存在。操作结果：将二叉树T清空。ADTBinaryTree2、二叉树的性质2、二叉树的性质性质1：二叉树的终端结点（叶子结点）数等于双分支结点数加1。假设二叉树中终端结点数为n0，单分支结点数为n1，双分支结点数为n2，二叉树中总结点数为n，因为二叉树中所有结点度数均小于或等于2，所以有：nn0n1n2；另一方面，二叉树中所有结点的分支数（即度数）应等于单分支结点数加上两倍的双分支结点数，即n12n2。由树的性质1，有：nn12n21。根据以上两个式子，我们可以得出下面这个等式成立：n0n1n2=n12n21，所以n0n21。性质2：在二叉树的第i层上至多有2i-1个结点(i1)。由树

22、的性质2可知，度为k的树中第i层上至多有ki-1个结点。对于二叉树，树的度为2，将k=2代入ki-1即可得此性质。性质3：深度为h的二叉树至多有2h1个结点（h1)。由树的性质3可知，深度为h的k叉树至多有（kh-1）/（k-1）个结点。对于二叉树，树的度为2，将k=2代入（kh-1）/（k-1）即可得此性质。性质4：具有n个（n0）结点的完全二叉树的深度为。由树的性质4可知，具有n个结点的k叉树的最小深度为。对于二叉树，树的度为2，将k=2代入上式即可得此性质。性质5：对有n个结点的完全二叉树中编号为i的结点（1in,n1)，有：（1）如果n为奇数，则树中每个分支结点都既有左孩子，又有右孩子

23、；如果n为偶数，则编号最大的分支结点即n/2只有左孩子，没有右孩子，其余分支结点左、右孩子都有。（2）如果i1，则结点i无双亲，是二叉树的根；如果i1，则其双亲是结点。当i为偶数时，其双亲结点的编号为i/2，它是双亲结点的左孩子；当i为奇数时，其双亲结点的编号为(i-1)/2，它是双亲结点的右孩子。其中一对符号表示对x进行向下取整，如。（3）如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。（4）如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。3、满二叉树、完全二叉树3、满二叉树、完全二叉树下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。在一棵二叉树中，当第i

24、层的结点数为2i-1个时，则称此层的结点数是满的。当树中每一层都满时，则称此二叉树为满二叉树。图4.2(a)为一棵深度为4的满二叉树，其结点数为15。图中每个结点的值是用该结点的编号来表示的。这种树的特点是每一层上的结点数都是最大结点数。由性质3可以得出，深度为h的满二叉树共有2h-1个结点。可以对满二叉树的结点进行顺序编号。其规则是：树中根结点的编号是1，然后按照层数从小到大、同一层内从左到右的顺序对树的每一个结点进行编号。若一棵深度为h的有n个结点的二叉树，当其每一个结点都与深度为h的顺序编号的满二叉树中编号从1至n的结点一一对应时，称这样的二叉树为完全二叉树。满二叉树是完全二叉树的特例。

25、图4.2(b)为一棵完全二叉树，它与等深度的满二叉树相比，在最后一层的右边缺少了4个结点。该树中每个结点的值也是用该结点的编号来表示的。完全二叉树的特点是：除最后一层外，其余各层都是满的，并且最后一层或者是满的，或者是在最右边缺少连续若干个结点。4、二叉链表数据类型描述4、二叉链表数据类型描述二叉树的链式存储结构可以有多种形式，通常使用的形式为：在每个结点中设置三个域，分别为数据域、左指针域和右指针域，其结点的结构如图4.5(a)所示。其中data表示数据域，用于存储对应的数据元素，left和right分别表示左指针域和右指针域，用来分别存储左孩子和右孩子结点的存储位置，这种结构称为二叉链表。

26、有时，为了便于找到结点的双亲，还可在结点结构中增加一个指向其双亲结点的指针域，如图4.5(b)所示，这种结构称为三叉链表。例如图4.6(a)所示的二叉树，它的链式存储结构有两种表示方法，在图4.6(b)中，用二叉链表表示，结点不带双亲指针，其中T1为指向根结点的指针，简称为根指针；在图4.6(c)中，用三叉链表表示，结点带有双亲指针，其中T2为根指针。在图4.6(b)中，二叉树的6个结点中共有7个空链域，容易证得，在含有n个结点的二叉链表中有n+1个空链域。在下一节中，我们将会看到可以利用这些空链域存储其它有用信息，从而得到另一种链式存储结构线索链表。根据以上所述，二叉链表的结点类型可定义为：

27、typedefstructBiTreeNodeElemTypedata;structBiTreeNode*left;structBiTreeNode*right;BiTreeNode,*BiTreePtr;在元素结点中，data用来存储数据元素，left和right分别用来存储左孩子和右孩子结点的存储位置。与线性表中的静态链表相似，我们还可以利用一组地址连续的内存空间来描述二叉树，把数组元素作为存储结点，元素类型包含数值域data和游标指示器left和right，游标定义为整型，left和right分别指示该结点的左孩子和右孩子结点在数组中的相对位置，若left或right游标值为0，则该结点

28、无左孩子或右孩子结点。整个数组下标为零的元素被看成是空闲链表的头结点，该结点的left指向树的根结点（一般设定树的根结点存放在下标为1的数组元素中，即根指针为1；当然，树为空时可设置根指针为0），该结点的right指向空闲链表的头结点；在空闲链表中，结点的right指针指向下一个空闲结点。上述方式下存储结构的数据类型描述如下：typedefstructSBiTreeNodeElemTypedata;intleft,right;SBiTreeNode;下面我们用一个例子来具体描述其存储结构，如图4.7所示。该存储结构的优点是：建立好后可以把整个数组写入到文件中保存起来，当需要时再从文件整体读入到

29、数组进行处理，但也有一些缺点，例如要预先分配一个较大的空间。5、二叉树遍历策略5、二叉树遍历策略二叉树的遍历二叉树的遍历是二叉树中最重要的运算，也是各种操作的基础。二叉树的遍历是指按照某个搜索路径寻访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。在遍历的过程中，可以对结点进行各种操作，如：对于一棵已知树可求结点的双亲，求结点的孩子结点，判定结点所在的层次等。根据二叉树的递归定义，一棵非空二叉树由根结点、左子树和右子树组成，因此，遍历一棵二叉树可以分解为三个问题：访问根结点、遍历左子树、遍历右子树。若分别用D、L、R表示上述三个子问题，则可能有DLR、LDR、LRD、DRL、RDL

30、、RLD几种情况。若限定先左后右，则只有前3种情况：（1）DLR，此时访问根结点的操作在遍历左、右子树之前，故称之为先序遍历或先根遍历；（2）LDR，此时访问根结点的操作在遍历左子树之后、右子树之前，故称之为中序遍历或中根遍历；（3）LRD，此时访问根结点的操作在遍历左、右子树之后，故称之为后序遍历或后根遍历。显然，遍历左、右子树的问题仍然是遍历二叉树的问题，当二叉树为空时递归结束，所以，很容易给出这三种遍历的递归算法。而上述的后三种情况与前三种情况的不同仅为前三种都是先遍历左子树，后遍历右子树，而后三种则相反。由于二者对称故我们只讨论前三种遍历方案，熟悉了前三种，后三种也就不成问题了。6、二

31、叉树遍历递归算法6、二叉树遍历递归算法（二叉树的先序遍历递归算法、二叉树的中序遍历递归算法、二叉树的后序遍历递归算法）(1)先序遍历算法StatusPreOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)/采用二叉链表存储结构，visit是对数据元素操作的应用函数/该算法采用递归的方式，对每个数据元素调用函数visitif(T)if(visit(T-data,visit)if(PreOrderTraverse(T-left)if(PreOrderTraverse(T-right,visit)returnOK;returnERROR;elsere

32、turnOK;/PreOrderTraverse算法4-1二叉树的先序遍历递归算法(2)中序遍历算法StatusInOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)/采用二叉链表存储结构，visit是对数据元素操作的应用函数/该算法采用递归的方式，对每个数据元素调用函数visitif(T)if(InOrderTraverse(T-left,visit)if(visit(T-data)if(InOrderTraverse(T-right,visit)returnOK;returnERROR;elsereturnOK;/InOrderTraver

33、se算法4-2二叉树的中序遍历递归算法(3)后序遍历算法StatusPostOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)/采用二叉链表存储结构，visit是对数据元素操作的应用函数/该算法采用递归的方式，对每个数据元素调用函数visitif(T)if(PostOrderTraverse(T-left,visit)if(PostOrderTraverse(T-right,visit)if(visit(T-data)returnOK;returnERROR;elsereturnOK;/PostOrderTraverse算法4-3二叉树的后序遍

34、历递归算法以上的三种算法均为递归算法，在运行过程中，函数需要使用系统设立的“递归工作栈”存储调用函数和被调用函数之间的链接及信息的交换。下面我们以中序算法为例，结合图4.8(a)的二叉树，分析它的执行过程。当开始调用中序遍历算法时（此次称为第0次递归调用），需要以指向根结点a的指针Ta作为实参，把它传递给形参T，递归栈中应包括形参T的值和返回地址。现假定指向每个结点的指针用该结点的值作为T的后缀，如指向结点d的指针就用Td表示，并且假定进行第0次递归调用后的返回地址为0，以及假设访问函数为打印输出结点的值，则函数递归调用的过程中，递归工作栈的状态如图4.9所示。StatusInOrderTra

35、verse(BiTreePtrT,Status(*visit)(ElemTypee)if(T)if(InOrderTraverse(T-left,visit)if(visit(T-data)if(InOrderTraverse(T-right,visit)returnOK;returnERROR;elsereturnOK;s递归层次、语句行号及执行结果递归工作栈状态（返址，指针值）(1)一层1,2,30,Ta(2)二层1,2,34,Tb0,Ta(3)三层1,2,34,Td4,Tb0,Ta(4)四层1,2,94,Td4,Tb0,Ta4,(5)三层4,5输出d4,Td4,Tb0,Ta(6)四层1,

36、2,34,Td4,Tb0,Ta6,Tg(7)五层1,2,94,Td4,Tb0,Ta6,Tg4,(8)四层4,5输出g4,Td4,Tb0,Ta6,Tg(9)五层1,2,94,Td4,Tb0,Ta6,Tg6,(10)四层64,Td4,Tb0,Ta6,Tg(11)三层64,Td4,Tb0,Ta(12)二层4,5输出b4,Tb0,Ta(13)三层1,2,96,4,Tb0,Ta(14)二层64,Tb0,Ta(15)一层4,5输出a0,Ta(16)二层1,2,36,Tc0,Ta(17)三层1,2,34,Te6,Tc0,Ta(18)四层1,2,94,Te6,Tc0,Ta4,(19)三层4,5输出e4,Te6

37、,Tc0,Ta(20)四层1,2,94,Te6,Tc0,Ta6,(21)三层64,Te6,Tc0,Ta(22)二层4,5输出c6,Tc0,Ta(23)三层1,2,36,Tf6,Tc0,Ta(24)四层1,2,96,Tf6,Tc0,Ta4,(25)三层4,5输出f6,Tf6,Tc0,Ta(26)四层1,2,96,Tf6,Tc0,Ta6,(27)三层66,Tf6,Tc0,Ta(28)二层66,Tc0,Ta(29)一层60,Ta(30)0层0栈空图4.9二叉树中序遍历调用的过程中，递归工作栈的状态上述分析的中序遍历的算法，最终打印出的结点序列为：dgbaecf若按照前序遍历算法和后序遍历算法遍历图4

38、.8所示的二叉树，则打印出的结点序列分别为：abdgcef和gdbefca对于上述遍历递归算法执行过程中递归工作栈状态的变化，我们可以通过人工建立栈仿照上述过程。具体算法描述如下：StatusInOrderTaverse(BiTreePtrT,Status(*visit)(ElemTypee)/中序遍历二叉树T的非递归算法，对每个数据元素调用函数visit。InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-left;/根指针进栈后，先遍历左子树else/根指针退栈，访问根结点，遍历右子树Pop(S,p);if(!visit(p-

39、data)returnERROR;p=p-right;/else/whilereturnOK;/InOrderTraverse算法4-4二叉树的中序遍历非递归算法对于二叉树进行遍历操作的路径除了上述的按先序、中序或后序外，还可以从上到下、从左到右按层次进行。在二叉树的遍历算法中，访问每个结点的每一个域，并且每个结点的每一个域仅被访问一次，所以算法的时间复杂度为O(n)。7、二叉树中序遍历非递归算法7、二叉树中序遍历非递归算法StatusInOrderTaverse(BiTreePtrT,Status(*visit)(ElemTypee)/中序遍历二叉树T的非递归算法，对每个数据元素调用函数vi

40、sit。InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-left;/根指针进栈后，先遍历左子树else/根指针退栈，访问根结点，遍历右子树Pop(S,p);if(!visit(p-data)returnERROR;p=p-right;/else/whilereturnOK;/InOrderTraverse算法4-4二叉树的中序遍历非递归算法8、二叉树的其他运算8、二叉树的其他运算（二叉树生成算法、二叉树的深度求解算法、删除二叉树中指定结点的算法、清空二叉树的算法）生成二叉树建立二叉树的过程中，既可以使用逐个输入结点的方式，也可

41、以一次性输入树的所有结点。本算法采用后者的方式建立树，对于这种方式，我们可使用广义表一次性输入所有结点。二叉树广义表表示的规定如下：1）每棵树的根结点作为由子树构成的表的名字而放在表的前面；2）每个结点的左子树和右子树用逗号隔开，若只有右子树，则逗号不能省略。例如，对于图4.10所示的二叉树，其广义表表示为：a(b(,e(h),c(f(,i)通过二叉树的广义表建立二叉树的链式存储结构的基本思路是：从保存二叉树广义表的字符串tree中读取每个字符，i.若遇到空格则不进行任何操作；ii.若遇到左括号，则表明子表开始，应首先用栈存储指向它前面的字母所在结点的指针，以便括号内的孩子结点向双亲结点链接，

42、然后由于左括号后面紧跟的字母（若存在）必为刚进栈结点的左孩子，设定变量k=1，表示将进行左孩子结点链接（k=2表示将进行右孩子结点链接）；iii.若遇到的是字母（假设以字母作为结点的值），应为它建立一个新结点，并把该结点（若它不是根结点）作为左孩子（若k=1）或右孩子（若k=2）链接到其双亲结点上，即当前栈顶元素所指向的结点；iv.若遇到逗号，则表明应开始处理右孩子结点向其双亲结点的链接，使k=2;v.若遇到右括号，则表明该子表结束，应退栈。按照如上所述方式处理每个字符，直到字符串读完为止。具体算法如下：voidCreatBiTree1(BiTreePtr&T,char*tree)/通过保存二

43、叉树广义表的字符串tree建立链式存储结构BiTreePtrp,e;/p为指向二叉树结点的指针intk；/用k作为链接结点的左子树和右子树的标记/k=1表示左子树，k=2表示右子树inti=0;/用i扫描字符串treeInitStack(S);/建立链栈，栈元素为二叉树结点的指针T=NULL;/树初始化为空while(treei)/每循环一次处理一个字符，直到扫描到字符串结束符为止switch(treei)case:/对空格不作任何处理break;case(:Push(S,p);k=1;break;case):if(StackEmpty(S)print(“存储二叉树广义表的字符串有错误”);e

44、xit(1);Pop(S,e);break;case,:k=2;break;default:p=(BiTreePtr)malloc(sizeof(BiTreeNode);p-data=treei;p-left=p-right=NULL;if(T=NULL)T=p;elseGetTop(S,e);if(k=1)e-left=p;elsee-right=p;/switchi+;/扫描下一个字符/while算法4-6二叉链表的生成算法在上述算法中，我们使用栈存储指向二叉树结点的指针，那么，我们能否不通过定义栈直接按照上述算法中的思想完成树的建立呢？在栈的遍历中，我们看到递归思想的应用，下面给出的改写

45、算法，也是通过递归的方式完成上述操作，本算法具体思想由读者去进一步思考。StatusCreatBiTree2(BiTreePtr&T)staticchartree100;staticintx=0;if(x=0)scanf(%s,tree);switch(treex)case:break;/读入空格后继续读取case(:x+;CreatBiTree2(T-left);/开始递归处理该结点的左子树if(treex=,)x+;CreatBiTree2(T-right);/对于逗号，退出到该层递归后处理结点右子树if(treex=)x+;CreatBiTree2(T);/对于右括号，退出到该层递归后处

46、理新结点break;case):break;/对于右括号不作任何处理，退出一层递归case,:break;/对于逗号，退出一层递归后处理结点右子树caseNULL:break;/数组tree尾部default:if(!(T=(BiTreeNode*)malloc(sizeof(BiTreeNode)exit(OVERFLOW);T-data=treex;T-left=T-right=NULL;x+;CreatBiTree2(T);returnOK;算法4-7二叉链表的递归生成算法求二叉树的深度该算法采用递归的思想：若一棵二叉树为空，则它的深度为0，否则它的深度等于左子树和右子树中的最大深度加1

47、。设depthL为左子树的深度，depthR为右子树的深度，则二叉树的深度为：max(depthL,depthR)+1其中max函数表示取参数中的较大者。该算法具体描述如下：IntBiTreeDepth(BiTreePtrT)if(T=NULL)return0;/对于空树，返回0并结束递归elseintdepthL=BiTreeDepth(T-left);/计算左子树的深度intdepthR=BiTreeDepth(T-right);/计算右子树的深度return(depthLdepthR)?depthL+1:depthR+1;/返回树的深度算法4-8二叉树的深度求解算法删除二叉树中指定结点要

48、删除指定结点及其左右子树，需分三种情况讨论：i.被删除结点无前驱，即树的根结点，则先清空根结点的左子树，再清空右子树，最后删除（即释放）根结点，并把根指针置空。ii.被删除结点无后继，即叶子结点，则释放该结点，并且将其双亲结点指向该结点的指针置空。iii.被删除结点有后继和前驱，则清空该结点左右子树，然后释放该结点，且将其双亲结点指向该结点的指针置空。以上三种情况可归结为，判断该结点是否有后继，若有，则以递归的方式清空左右子树，若无则不操作；判断该结点是否有双亲结点，若有则将其指向该结点的指针置空，若无则不操作；释放该结点空间。具体算法描述如下：StatusDelBiTreeNode(BiTr

49、eePtr&T)/删除T指向的结点及其子树if(T!=NULL)DelBiTreeNode(T-left);/删除左子树DelBiTreeNode(T-right);/删除右子树if(Parent(T,T-data,P)/双亲结点中指向该结点的指针置空if(p!=NULL)if(P-left=T)P-left=NULL;if(P-right=T)P-right=NULL;free(T);/释放该结点returnOK;算法4-10删除二叉树中指定结点的算法清空二叉树该算法与删除指定结点的算法类似，即为删除根结点。算法描述如下：StatusClearBiTree(BiTreePtr&T)if(T!

50、=NULL)ClearBiTree(T-left);/删除左子树ClearBiTree(T-right);/删除左子树free(T);/释放根结点T=NULL;/根指针置空算法4-11清空二叉树的算法第三节线索二叉树遍历二叉树实现了树型非线性结构的线性化，形成了二叉树结点的线性序列。为了便于查找某个结点在线性序列中的前驱和后继信息，需要将二叉树线索化。1、线索链表的数据类型1、线索链表的数据类型作为二叉树基本的操作，遍历二叉树是以一定规则将二叉树中的结点排成一个线性序列，这可看成是对树这种非线性结构进行线性化的操作，它使得每个结点（除第一个和最后一个外）在这个线性序列中都有唯一的直接前驱和直接

51、后继。当以二叉链表作为存储结构时，只能较为方便地找到结点的左右孩子的信息，而不能直接得到在结点的线性序列中的前驱与后继信息，这种信息只有在遍历的动态过程中才能得到。为了能方便获得和利用某种遍历过程中的前驱与后继结点的信息，可以在每个结点中设置两个指针分别保存它们，但我们注意到在二叉链表中有大量的空指针（n个结点的二叉链表中有n+1个空链域），我们可以充分利用这些空链域来存放结点的前驱和后继的信息。具体来说，每个结点有左（右）子结点时，其左（右）指针指向该子结点，或无左（右）子结点，则其左（右）指针指向其前驱（后继）结点。当然为了区分这些指针是指向其子结点还是指向其前驱或后继结点，需要在结点的数

52、据类型中增加两个标志域ltag、rtag，如图4.11所示。以这种结点类型构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱或后继的指针称为线索，加上线索的二叉树称为线索二叉树。其中：所以，线索二叉树结点的存储结构为：typedefenumLink,ThreadPTag;/Link=0：指针，Thread=1：线索typedefstructBiThrNodeElemTypedata;structBiThrNode*left,*right;/左右孩子指针PTagltag,rtag;/左右标志BiThrNode,*BiThrTree;2、二叉树的中序线索化算法2、二叉树的中序线索化

53、算法这个过程实际上就是将已经建立好的二叉链表中的空指针改为指向前驱或者后继的线索。由于在二叉树的遍历过程中，我们可以得到结点的前驱或后继的信息，因此，线索化的过程即为在遍历过程中修改空指针的过程。为了能在遍历过程中记录访问结点的先后关系，我们附设一个全局变量指针pre始终指向刚刚访问过的结点。若指针指向当前访问的结点，则pre指向它的前驱，而当前访问的结点又是pre的后继。pre的初值为NULL。二叉树的中序线索化算法如下所示：StatusInOrderThreading(BiThrTree&T)/中序遍历二叉树T，并将其中序线索化，T指向树或子树的根结点。p=T;if(p)InOrderTh

54、reading(T-left);/左子树线索化if(!p-left)p-ltag=Thread;p-left=pre;/前驱线索标记if(pre&!pre-right)pre-rtag=Thread;pre-right=p;/pre为全局变量，初值为NULL；后继线索标记pre=p;/pre始终指向前驱InOrderThreading(T-right);/右子树线索化returnOK;/InOrderThreading算法4-13二叉树的中序线索化算法3、中序线索二叉树的遍历算法3、中序线索二叉树的遍历算法在线索二叉树上进行遍历，只需要从序列的第一个结点开始访问，然后通过依次寻找结点的后继进行

55、遍历，当后继为空时，遍历即可结束。当然，线索二叉树总是与某种遍历次序相关的，我们下面主要以中序遍历为主来考虑线索二叉树。以图4.12为例，树中所有叶子结点的左、右链是线索，此时，右链域直接指示了结点的后继，如结点g的后继为结点b。树中所有存在右孩子结点的右链均为指针，则无法直接得到该结点后继的信息。但是，根据中序遍历的规则，该结点的后继应是遍历其右子树时访问的第一个结点，即为该结点的右子树中最左下的结点。例如，找结点a的后继，首先应沿着其右指针，找到它的右孩子结点c，然后，顺着左指针一直往下，直到左标志为1时，意味着该结点无左子结点，即该结点为a的后继，在图中是结点e。根据如上所述，则遍历中序

56、线索二叉树的算法为：StatusInOrderTaverse_Thr(BiThrTreeT,Status(*visit)(ElemTypee)/T指向根结点，遍历中序线索二叉树p=T;/p指向根结点while(p!=NULL)/空树或遍历结束时，p=NULLwhile(p-ltag=Link)p=p-left;if(!visit(p-data)returnERROR;/访问其左子树为空的结点while(p-rtag=Thread&p-right!=NULL)p=p-right;visit(p-data);/访问后继结点p=p-right;returnOK;/InOrderTraverse_Th

57、r算法4-12中序线索二叉树的遍历算法由此算法可以看出，对于中序线索二叉树的遍历，虽然时间复杂度为O(n)，但是算法的实际频数要比二叉链表的递归遍历算法低，而且不需要设栈。因此，若在某程序中所使用的二叉树经常需要遍历或查找结点在遍历所得线性序列中的前驱和后继，则应采用线索链表作为存储结构。第四节树和森林为了便于树的操作，通常将树转化为二叉树。本节讨论树的表示及基本的遍历操作，并说明树、森林与二叉树的转化关系。1、一般树转化成二叉树的规则2、森林转化成二叉树的规则2、森林转化成二叉树的规则任何一棵树都能按照一定的方式表示成二叉树，这样对树的计算机表示和操作等，只要利用二叉树即可。一般树转化为二叉

58、树的规则为：（1）一般树的根对应二叉树的根；（2）对树中任意结点，转化为二叉树的结点后，该结点原最左边的孩子结点作为转化后它的左孩子结点，该结点原右边相邻的第一个兄弟结点作为转化后它的右孩子结点，并依此类推。例如，设它的孩子结点依次为Ts1,Ts2,，兄弟结点依次为TB1,TB2,，则对应二叉树时，该结点的左孩子为Ts1，右孩子为TB1，Ts1的右孩子结点为Ts2，TB1的右孩子结点为TB2。这样树中任一结点的子结点对应二叉树中结点的左子树根结点及沿着该子结点的右分支路径至末端的各结点，显然这样转化的二叉树根结点无右子树，这是根结点没有兄弟结点的必然结果。图4.16给出了一个具体的树转化成二叉

59、树的例子。如果把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟结点，则同样可推导出森林和二叉树的转化。森林转化成二叉树的规则是：（1）若森林为空，则对应的二叉树为空；（2）若森林非空，将森林中所有的树按照规则转化为二叉树；（3）设置一个虚拟根结点，该结点的子树从左到右依次为森林中从左到右的树，即将所有的二叉树连接到虚拟根结点上；（4）将这棵树按照规则转化为二叉树（实际仅需一层操作，即原各棵树的根结点按照兄弟结点的规则进行转化，在此过程中各根结点带上原子树一起移动）；（5）去掉虚拟根结点，则二叉树的根结点为原第一棵树的根结点。二叉树转化成森林的规则是：（1）若二叉树为空，则对应的森林为空；（

60、2）若二叉树非空，则对应的森林中第一棵树的根结点为二叉树的根结点，根结点的子树森林是由二叉树的左子树转化而成的森林；森林中除第一棵树之外其余树组成的森林是由二叉树的右子树转化而成的森林。3、森林的遍历策略3、森林的遍历策略有两种次序遍历树的方法：一种是先根(次序)遍历树，另一种是后根(次序)遍历树。前者先访问树的根结点，然后依次先根遍历根结点的每棵子树；后者则是先依次后根遍历每棵子树，然后再访问根结点。按照森林和树相互递归的定义，可以得到森林的两种遍历方法：1.先序遍历森林若森林非空，则可按下述规则对其进行遍历：（1）访问森林中第一棵树的根结点；（2）先序遍历第一棵树中根结点的子树森林；（3）