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

第四章树和二叉树

内容概述

树是一种非线性数据结构。树结构经常用于描述和处理数据元素的层次关系，

尤其适用于大规模的信息处理任务，例如建立数据库管理系统时所用的层次模型

就是一种树型结构。本章主要以二叉树为例，讲述树结构及其应用，主要内容包

括：

(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(nNO)个结点的有限集合T,不含有任何结点(元素)的树称为

空树，否则它满足如下两个条件：有且仅有一个称为根(Root)的结点；其余所有

结点被分成m(m20)个互不相交的集合Ti,T2,T3,...,Tm,其中每个集合又构成一

棵树，称其为根结点的子树(SubTree)。树的根结点Root是每棵子树根结点的前

驱，每棵子树的根结点是根结点Root的后继。

例如，在图4.1中，(a)表示只有一个根结点的树；(b)表示有8个结点的树，

其中A是根结点，其余结点分成3个互不相交的子集：

TI={B,E,F,G},T2={C}ZT3={D,H}OT1、T2和丁3都是根结点A的子树,且本身也

是一棵树。如Ti的根结点为B,其余结点分为3个互不相交的子集：

Tii={E}zTi2={F}zTi3={G}oTil,Ti2和T13都是T1的根结点B的子树

2.树的非递归定义

树是n(nNO)个结点的有限集合T,不含有任何结点(元素)的树称为空树，

而在任一非空树中定义了一个关系，它满足：

(1)T中存在唯一的一个结点，它没有前驱，称为树的根；

(2)除根结点外，T中每一个结点都有且仅有一个前驱结点；

(3)除根结点外，T中每一个结点a,都存在一个从根结点到a的结点序列

ai...ak,使得ai为根结点,ak=a,而结点ai+i是ai的后继(l<i<k-l),这个结点

序列称为从根结点到结点a的路径。

例如，在图4.1(b)中，A为树的根结点。对于结点G,存在一个结点序列ABG,

使得A为根结点，B为A的后继，G为B的后继，这个序列就是从根结点A到结

点G的路径。

2、树的抽象数据类型

2、树的抽象数据类型

树的抽象数据类型定义如下：

ADTTree{

数据对象D：D={ai|ai据日emSet,i=l,2,...,n,n“}

数据关系R：若D为空集，则称为空树。

若D仅含一个数据元素，则R为空集，否则R={H},H满足关系：

(1)T中存在唯一的一个结点，它没有前驱，称为树的根，用root表示，在集合

D中用ai表不；

(2)若D中元素个数大于1,对于任意的数据元素aj£D且jN2,存在唯一的数据

元素ai£D,有<A,aj>£H；

(3)若D中元素个数大于1,对于任意的数据元素aj£D,存在k个(抡0)数据元

素agD且泛j,有<aj,ai>£H；

(4)对于任意的数据元素aj£D且a2,存在DjD,

Dj={|EEIemSet/k=l/2,...,m/m>0},有唯一的Pj={<,这

个集合?表示从根结点到结点访的一条路径。

基本操作P：

InitTree(&T);

操作结果：构造空树T。

CreateTree(&T,tree);

初始条件：tree给出T的表示形式。

操作结果：按tree构造T。

TreeEmpty(T);

初始条件：树T存在。

操作结果：若丁为空树，则返回TRUE,否则返回FALSE。

TreeDepth(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);

初始条件：树丁存在，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、Bo

结点的层数和树的深度

树既是一种递归结构，也是一种层次结构。结点的层数(Level)从根开始定

义起，根结点为第一层，它的子结点为第二层，以此类推。如果某个结点在第k

层，则其子树的根位于第k+1层。树中结点的最大层数称为树的深度(Depth)

或高度。如在图4.1(b)中，结点A为第一层，B、C、D为第二层，E、F、G、H

为第三层，树中结点的最大层数是3,故树的深度为3。

有序树和无序树

如果树中各结点的子树是按照一定的次序从左向右安排的，则称该树为有序

树，否则称之为无序树。在有序树中，最左边的子树的根称为第一个孩子，最右

边的子树的根称之为最后一个孩子。任何无序树都可以当作是任一次序的有序树

来处理，如一个单位的机构设置可用树来表示，若各层机构是按照一定的次序排

列的，则为一棵有序树，否则为无序树。

森林(Forest)是m(m>0)棵互不相交的树的集合。对于树中每个分支结点

来说，其子树的集合就是森林。如在图4.1(b)中，由结点A的子树所构成的森林

为仃1,T2尸3｝，由结点B的子树所构成的森林为｛T11,T12,T13｝。

4、树的性质

4、树的性质

性质1：树中的结点数等于所有结点的度数加1。

根据树的定义，在一个树中，除了根结点以外，其他每个结点都有且只有一

个前驱结点，即每个结点与指向它的一个分支一一对应，所以除了根结点以外的

结点数等于所有结点的分支数（即度数），因此可得出树中的结点数等于所有结

点的度数加lo

性质2：度为k的树中第i层上至多有Hi个结点（泛1）。

利用数学归纳法可以证明此性质。

对于第一层显然是成立的。因为树中的第一层上只有根结点，而i=l时，

寸1=|<。=1,同样也得到只有一个结点。假设对于第i-1层（i>l）命题成立，即

度为k的树中第i-1层上至多有k（£）T=ki-2个结点，则根据树的度的定义，度为k

的树中每个结点至多有k个孩子，所以第i层上的最大结点数为第i-1层上的最

大结点数的k倍，即k»2xk=k"个，故结论成立。

性质3：深度为h的k叉树至多有（H-l）/（k-1）个结点。

由性质2可知，当深度为h的k叉树（即度为k的树）上每一层都达到最多

结点数时，所有结点的总和为：，故深度为h的k叉树至多有个结点。

当一棵k叉树上的结点数等于时，即k叉树的结点数达到了最大值时，则称

该树为满k叉树。这种树的特点是每一层上的结点数都是最大结点数。

性质4：具有n个结点的k叉树的最小深度为。（其中符号表示对x进行向上取

整，如。）

假设具有n个结点的k叉树的深度为h,若在该树中前h-l层都是满的，即

第i层的结点数等于Hi个（lsiwh-1）,最后一层即第h层的结点数可能满也可

能不满，则该树具有最小的深度。根据性质3有：，即。以k为底取对数后得。

所以，。

因此得到具有n个结点的一般k叉树的最小深度是。

第二节二叉树

‘一二五树是使用最广泛的树型结构，这是因为一方面应用中有许多问题都可以

通过二叉树来解决，另一方面一般树的问题也可转化为二叉树的问题来简便处理。

那么，二叉树具有那些性质？如何存储表示和实现二叉树？

1、二叉树的抽象数据类型定义

1、二叉树的抽象数据类型定义

所谓二叉树，是指结点的一个有限集合，它或为空集，或为满足下列性质的非空

集合：有且只有一个根结点，其余结点分成左右两个互不相交的集合TL、TR,

且TL、TR均为二叉树。

直观上，二叉树就是一个最多有两个分支的树丁在二叉树中，每个结点的左子树

的根结点被称为该结点的左孩子（LeftChild）,右子树的根结点被称为该结点的

右孩子（Rightchild）。二叉树的左右子树次序不能任意颠倒。二叉树与一般树

的区别在于二叉树的子树有左右之分，以及二叉树定义中对树的度数的限制（即

二叉树中不存在度大于2的结点）。下面我们将重点介绍二叉树，这是因为一方

面应用中有许多问题都可以通过二叉树来解决，另一方面一般树的问题也可转化

为二叉树的问题来简便处理。

前面引入的有关树的术语也都适用于二叉树。

二叉树的抽象数据类型定义如下：

ADTBinaryTree{

数据对象D：D={ai|aiGEIemSet,i=l,2,...,n,n>0}

数据关系R：若D为空集，则称为空二叉树。

若D仅含一个数据元素，则R为空集，否则R={H},H满足关系：

(1)T中存在唯一的一个结点，它没有前驱，称为树的根，用root表示，在

集合D中用al表示；

(2)若D中元素个数大于1,对于任意的数据元素司WD且a2,存在唯一的

数据元素ai£D,有<AI,aj>£H；

(3)若D中元素个数大于1,对于任意的数据元素aieD,仅存在不多于2个

数据元素aj,ak£D且j,kzi,有<ai向>,<ai,ak>WH,其中，若j<K<span>,则

称aj为ai吊左孩子节最ak为ai的右孩子节点。

(4)对于任意的数据元素aj£D且上2,存在DjD,

Dj={|eElemSet,k=l/2,...,m,m>0},有唯一的Pj={<,这个

集合Pj表示从根结点到结点aj的一条路径。

基本操作P：

InitBiTree(&T);

操作结果：构造空二叉树T。

CreateBiTree(&T,tree);

初始条件：tree给出二叉树丁的表示形式。

操作结果：按tree构造二叉树T。

BiTreeEmpty(T);

初始条件：二叉树T存在。

操作结果：若T为空树，则返回TRUE否则返回FALSE。

BiTreeDepth(T);

初始条件：二叉树T存在。

操作结果：返回T的深度。

Root(T);

初始条件：二叉树T存在。

操作结果：返回T的根。

Value(T,e);

初始条件：二叉树T存在,e是需寻找的结点的值。

操作结果：若找到该结点,则函数返回TRUE,否则返回FALSEo

Assign(T,e,value);

初始条件：二叉树T存在,e是需寻找的结点的值。

操作结果：若找到该结点,结点e赋值为value,则函数返回TRUE,否则返回

FALSEo

Parent(T,e,P);

初始条件：二叉树T存在，e是需寻找的结点的值。

操作结果：若树中存在值为e的结点，则函数返回TRUE,否则返回FALSE；若

存在该结点，用P返回双亲结点的位置，若结点为根结点，则P返回空。

LeftChild(T,e,P);

初始条件：二叉树T存在，e是需寻找的结点的值。

操作结果：若树中存在值为e的结点，则函数返回TRUE,否则返回FALSE；若

存在该结点，用P返回左孩子结点的位置，若结点无左孩子结点，则P返回空。

RightChild(T,ezP);

初始条件：二叉树T存在，e是需寻找的结点的值。

操作结果：若树中存在值为e的结点，则函数返回TRUE,否则返回FALSE；若

存在该结点，用P返回右孩子结点的位置，若结点无右孩子结点，则P返回空。

DelBiTreeNode(&T,P);

初始条件：二叉树T存在，P指向该二叉树中的一个结点。

操作结果：删除P所指向的结点及其子树。

TraverseBiTree(T,visit());

初始条件：二叉树T存在，visit是对结点操作的应用函数。

操作结果：按某种次序对T的每个结点调用函数visit。一次且至多一次。一旦

visit。失败，则操作失败。

ClearBiTree(&T);

初始条件：二叉树T存在。

操作结果：将二叉树T清空。

}ADTBinaryTree

2、二叉树的性质

2、二叉树的性质

性质L二叉树的终端结点(叶子结点)数等于双分支结点数加1。

假设二叉树中终端结点数为nO,单分支结点数为nl,双分支结点数为n2,二叉

树中总结点数为n,因为二叉树中所有结点度数均小于或等于2,所以有：n=

n0+nl+n2；另一方面，二叉树中所有结点的分支数(即度数)应等于单分支

结点数加上两倍的双分支结点数，即nl+2xn2。由树的性质1,有：n=nl+2xn2

+lo根据以上两个式子，我们可以得出下面这个等式成立：n0+nl+n2=nl+

2xn2+l,所以n0=n2+l。

性质2：在二叉树的第i层上至多有2i-l个结点(法1)。

由树的性质2可知，度为k的树中第i层上至多有ki-1个结点。对于二叉树，树

的度为2,将k=2代入ki-1即可得此性质。

性质3：深度为h的二叉树至多有2h—l个结点(hNl)。

由树的性质3可知，深度为h的k叉树至多有(kh-1)/(k-1)个结点。对于二

叉树，树的度为2,将k=2代入(kh-1)/(k-1)即可得此性质。

性质4：具有n个(n>0)结点的完全二叉树的深度为。

由树的性质4可知，具有n个结点的k叉树的最小深度为。对于二叉树，树的度

为2,将k=2代入上式即可得此性质。

性质5：对有n个结点的完全二叉树中编号为i的结点(l<i<n,n>l),有：

(1)如果n为奇数，则树中每个分支结点都既有左孩子，又有右孩子；如果n

为偶数，则编号最大的分支结点即n/2只有左孩子，没有右孩子，其余分支结点

左、右孩子都有。

(2)如果i=l,则结点i无双亲，是二叉树的根；如果i>l,则其双亲是结点。

当i为偶数时，其双亲结点的编号为i/2,它是双亲结点的左孩子；当i为奇数时，

其双亲结点的编号为(i-l)/2,它是双亲结点的右孩子。其中一对符号表示对x进

行向下取整，如。

(3)如果2i>n,则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。

(4)如果2i+l>n,则结点i无右孩子；否则，其右孩子是结点2i+l。

3、满二叉树、完全二叉树

3、满二叉树、完全二叉树

下面介绍两种特殊形态的二叉树.：满二叉树和完全二叉树.。

在一棵二叉树中，当第i层的结点数为2i-l个时，则称此层的结点数是满的。当

树中每一层都满时，则称此二叉树为满二叉树。图4.2(a)为一棵深度为4的满二

叉树，其结点数为15。图中每个结点的值是用该结点的编号来表示的。这种树

的特点是每一层上的结点数都是最大结点数。由性质3可以得出，深度为h的满

二叉树共有2h-l个结点。可以对满二叉树的结点进行顺序编号。其规则是：树

中根结点的编号是1,然后按照层数从小到大、同一层内从左到右的顺序对树的

每一个结点进行编号。

若一棵深度为h的有n个结点的二叉树，当其每一个结点都与深度为h的顺序编

号的满二叉树中编号从1至n的结点一一对应时，称这样的二叉树为完全二叉树。

满二叉树是完全二叉树的特例。图4.2(b)为一棵完全二叉树，它与等深度的满二

叉树相比，在最后一层的右边缺少了4个结点。该树中每个结点的值也是用该结

点的编号来表示的。完全二叉树的特点是：除最后一层外，其余各层都是满的，

并且最后一层或者是满的，或者是在最右边缺少连续若干个结点。

4、二叉链表数据类型描述

4、二叉链表数据类型描述

二叉树的链式存储结构可以有多种形式，通常使用的形式为：在每个结点中设置

三个域，分别为数据域、左指针域和右指针域，其结点的结构如图4.5(a)所示。

其中data表示数据域，用于存储对应的数据元素，left和right分别表示左指针

域和右指针域，用来分别存储左孩子和右孩子结点的存储位置，这种结构称为二

叉链表。

有时，为了便于找到结点的双亲，还可在结点结构中增加一个指向其双亲结点的

指针域，如图4.5(b)所示，这种结构称为三叉链表。

例如图4.6(a)所示的二叉树，它的链式存储结构有两种表示方法，在图4.6(b)

中，用二叉链表表示，结点不带双亲指针，其中T1为指向根结点的指针，简称

为根指针；在图4.6(c)中，用三叉链表表示，结点带有双亲指针，其中T2为根

指针。

在图4.6(b)中，二叉树的6个结点中共有7个空链域，容易证得，在含有n个结

点的二叉链表中有n+1个空链域。在下一节中，我们将会看到可以利用这些空

链域存储其它有用信息，从而得到另一种链式存储结构——线索链表。

根据以上所述，二叉链表的结点类型可定义为：

typedefstructBiTreeNode{

ElemTypedata;

structBiTreeNode*left;

structBiTreeNode*right;

}BiTreeNode,*BiTreePtr;

在元素结点中，data用来存储数据元素，left和right分别用来存储左孩子和右

孩子结点的存储位置。

与线性表中的静态链表相似，我们还可以利用一组地址连续的内存空间来描述二

叉树，把数组元素作为存储结点，元素类型包含数值域data和游标指示器left

和right,游标定义为整型，left和right分别指示该结点的左孩子和右孩子结点

在数组中的相对位置，若left或right游标值为0,则该结点无左孩子或右孩子

结点。整个数组下标为零的元素被看成是空闲链表的头结点，该结点的left指向

树的根结点(一般设定树的根结点存放在下标为1的数组元素中，即根指针为1；

当然，树为空时可设置根指针为0),该结点的right指向空闲链表的头结点；

在空闲链表中，结点的right指针指向下一个空闲结点。

上述方式下存储结构的数据类型描述如下：

typedefstructSBiTreeNode{

ElemTypedata;

intleft,right;

}SBiTreeNode;

下面我们用一个例子来具体描述其存储结构，如图4.7所示。

该存储结构的优点是：建立好后可以把整个数组写入到文件中保存起来，当需要

时再从文件整体读入到数组进行处理，但也有一些缺点，例如要预先分配一个较

大的空间。

5、二叉树遍历策略

5、二叉树遍历策略

二叉树的遍历

二叉树的遍历是二叉树中最重要的运算，也是各种操作的基础。二叉树的遍历是

指按照某个搜索路径寻访树中的每个结点，使得每个结点均被访问一次，而且仅

被访问一次。在遍历的过程中，可以对结点进行各种操作，如：对于一棵已知树

可求结点的双亲，求结点的孩子结点，判定结点所在的层次等。

根据二叉树的递归定义，一棵非空二叉树由根结点、左子树和右子树组成，因此，

遍历一棵二叉树可以分解为三个问题：访问根结点、遍历左子树、遍历右子树。

若分别用D、L、R表示上述三个子问题，则可能有DLR、LDR、LRD、DRL、RDL、

RLD几种情况。若限定先左后右，则只有前3种情况：

(1)DLR,此时访问根结点的操作在遍历左、右子树之前，故称之为先序遍历

或先根遍历；

(2)LDR,此时访问根结点的操作在遍历左子树之后、右子树之前，故称之为

中序遍历或中根遍历；

(3)LRD,此时访问根结点的操作在遍历左、右子树之后，故称之为后序遍历

或后根遍历。

显然，遍历左、右子树的问题仍然是遍历二叉树的问题，当二叉树为空时递归结

束，所以，很容易给出这三种遍历的递归算法。而上述的后三种情况与前三种情

况的不同仅为前三种都是先遍历左子树，后遍历右子树，而后三种则相反。由于

二者对称故我们只讨论前三种遍历方案，熟悉了前三种，后三种也就不成问题了。

6、二叉树遍历递归算法

6、二叉树遍历递归算法(二叉树的先序遍历递归算法、二叉树的中序遍历递归

算法、二叉树的后序遍历递归算法)

(1)先序遍历算法

StatusPreOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)){

〃采用二叉链表存储结构，visit是对数据元素操作的应用函数

〃该算法采用递归的方式，对每个数据元素调用函数visit

if(T){

if(visit(T->data,visit))

if(PreOrderTraverse(T->left))

if(PreOrderTraverse(T->right,visit))returnOK;

returnERROR;

)

elsereturnOK;

}//PreOrderTraverse

算法4-1二叉树的先序遍历递归算法

(2)中序遍历算法

StatusInOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)){

〃采用二叉链表存储结构，visit是对数据元素操作的应用函数

〃该算法采用递归的方式，对每个数据元素调用函数visit

if(T){

if(InOrderTraverse(T->left,visit))

if(visit(T->data))

if(InOrderTraverse(T->right,visit))returnOK;

returnERROR;

)

elsereturnOK;

}//InOrderTraverse

算法4-2二叉树的中序遍历递归算法

(3)后序遍历算法

StatusPostOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)){

〃采用二叉链表存储结构，visit是对数据元素操作的应用函数

〃该算法采用递归的方式，对每个数据元素调用函数visit

if(T){

if(PostOrderTraverse(T->left,visit))

if(PostOrderTraverse(T->right,visit))

if(visit(T->data))returnOK;

returnERROR;

)

elsereturnOK;

}//PostOrderTraverse

算法4-3二叉树的后序遍历递归算法

以上的三种算法均为递归算法，在运行过程中，函数需要使用系统设立的''递归

工作栈”存储调用函数和被调用函数之间的链接及信息的交换。下面我们以中序

算法为例，结合图4.8(a)的二叉树，分析它的执行过程。

当开始调用中序遍历算法时(此次称为第0次递归调用)，需要以指向根结点a

的指针Ta作为实参，把它传递给形参T,递归栈中应包括形参T的值和返回地

址。现假定指向每个结点的指针用该结点的值作为T的后缀，如指向结点d的指

针就用Td表示，并且假定进行第0次递归调用后的返回地址为0,以及假设访

问函数为打印输出结点的值，则函数递归调用的过程中，递归工作栈的状态如图

4.9所示。

(1)StatusInOrderTraverse(BiTreePtrT,Status(*visit)(ElemTypee)){

②if(T){

③if(InOrderTraverse(T->left,visit))

④if(visit(T->data))

⑤if(InOrderTraverse(T->right,visit))

⑥

⑦returnOK;

⑧returnERROR;

⑨)

elsereturnOK;

s)

递归层次、语

句

递归工作栈状态（返

址，指针值）

行号及执行结

果

0,Ta

一层1,2,3

4,Tb

二层1,2,3

0,Ta

4,Td

三层1,2,34,Tb

0,Ta

4,Td

4,Tb

四层1,2,9

OzTa

1A

4,Td

)三层4,5

输出d

4,Tb

O,Ta

4,Td

4,Tb

四层1,2,3

O,Ta

6,Tg

4zTd

4,Tb

五层1,2,9O,Ta

6,Tg

4,A

4zTd

4,Tb

；）四层4,5

输出g

O,Ta

6,Tg

4,Td

4,Tb

五层1,2,9O,Ta

6,Tg

6,A

4,Td

4,Tb

：10）四层6

O,Ta

6,Tg

4,Td

：11）三层64,Tb

OzTa

L2）二层4,54,Tb

输出b

O,Ta

6,A

3）三层1,2,94,Tb

O,Ta

4,Tb

：14）二层6

O,Ta

L5）一层4,5O,Ta

输出a

6,Tc

6）二层1,2,3

O,Ta

4,Te

7）三层1,2,36,Tc

OzTa

4,Te

8）四层1,2,96,Tc

O,Ta

4,A

4,Te

⑼三层4,5

6,Tc

输出e

O,Ta

4,Te

6,Tc

。）四层1,2,9

O,Ta

6,A

4,Te

：21)三层66,Tc

O,Ta

6,Tc

?2)二层4,5

输出c

O,Ta

6,Tf

3)三层1,2,3

6,Tc

O,Ta

6zTf

6,Tc

4)四层1,2,9

O,Ta

4,人

6,Tf

?5)三层4,5

6,Tc

输出f

O,Ta

6,Tf

6,Tc

6)四层1,2,9

OzTa

6,A

6,Tf

27)三层6

6,Tc

O,Ta

6zTc

：28)二层6

O,Ta

：29)一层6O,Ta

(30)0层0栈空________

图4.9二叉树中序遍历调用的过程中，递归工作栈的状态

上述分析的中序遍历的算法，最终打印出的结点序列为：dgbaecf

若按照前序遍历算法和后序遍历算法遍历图4.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->data))returnERROR;

p=p->right;

}//else

}//while

returnOK;

}//InOrderTraverse

算法4-4二叉树的中序遍历非递归算法

对于二叉树进行遍历操作的路径除了上述的按先序、中序或后序外，还可以从上

到下、从左到右按层次进行。

在二叉树的遍历算法中，访问每个结点的每一个域，并且每个结点的每一个域仅

被访问一次，所以算法的时间复杂度为。(n)。

7、二叉树中序遍历非递归算法

7、二叉树中序遍历非递归算法

StatusInOrderTaverse(BiTreePtrT,Status(*visit)(ElemTypee)){

〃中序遍历二叉树丁的非递归算法，对每个数据元素调用函数visit。

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

}//while

returnOK;

}//InOrderTraverse

算法4-4二叉树的中序遍历非递归算法

8、二叉树的其他运算

8、二叉树的其他运算(二叉树生成算法、二叉树的深度求解算法、删除二叉树

中指定结点的算法、清空二叉树的算法)

生成二叉树

建立二叉树的过程中，既可以使用逐个输入结点的方式，也可以一次性输入

树的所有结点。本算法采用后者的方式建立树，对于这种方式，我们可使用广义

表一次性输入所有结点。二叉树广义表表示的规定如下：

1)每棵树的根结点作为由子树构成的表的名字而放在表的前面；

2)每个结点的左子树和右子树用逗号隔开，若只有右子树，则逗号不能省略。

例如，对于图4.10所示的二叉树，其广义表表示为：

a(b(,e(h)),c(f(,i)))

通过二叉树的广义表建立二叉树的链式存储结构的基本思路是：

从保存二叉树广义表的字符串tree中读取每个字符，

i.若遇到空格则不进行任何操作；

ii.若遇到左括号，则表明子表开始，应首先用栈存储指向它前面的字母所在结

点的指针，以便括号内的孩子结点向双亲结点链接，然后由于左括号后面紧跟的

字母(若存在)必为刚进栈结点的左孩子，设定变量k=l,表示将进行左孩子结

点链接(k=2表示将进行右孩子结点链接)；

iii.若遇到的是字母(假设以字母作为结点的值)，应为它建立一个新结点，并把

该结点(若它不是根结点)作为左孩子(若k=l)或右孩子(若k=2)链接到其

双亲结点上，即当前栈顶元素所指向的结点；

iv.若遇到逗号，则表明应开始处理右孩子结点向其双亲结点的链接，使k=2;

v.若遇到右括号，则表明该子表结束，应退栈。

按照如上所述方式处理每个字符，直到字符串读完为止。具体算法如下：

voidCreatBiTreel(BiTreePtr&T,char*tree){

〃通过保存二叉树广义表的字符串tree建立链式存储结构

BiTreePtrp,e;//p为指向二叉树结点的指针

intk；〃用k作为链接结点的左子树和右子树的标记

〃k=l表示左子树，k=2表示右子树

inti=0;〃用i扫描字符串tree

InitStack(S);〃建立链栈，栈元素为二叉树结点的指针

T=NULL;〃树初始化为空

while(tree[i]){

〃每循环一次处理一个字符，直到扫描到字符串结束符为止

switch(tree[i]){

case”:〃对空格不作任何处理

break;

case'。：

Push(S,p);

k=l;

break;

case')':

if(StackEmpty(S)){

print。'存储二叉树广义表的字符串有错误)

exit(l);

)

Pop(S,e);

break;

case',':

k=2;

break;

default:

p=(BiTreePtr)malloc(sizeof(BiTreeNode));

p->data=tree[i];p->left=p->right=NULL;

if(T==NULL)T=p;

else{GetTop(S,e);

if(k==l)e->left=p;

elsee->right=p;

)

}//switch

i++；〃扫描下一个字符

}//while

)

算法4-6二叉链表的生成算法

在上述算法中，我们使用栈存储指向二叉树结点的指针，那么，我们能否不

通过定义栈直接按照上述算法中的思想完成树的建立呢？在栈的遍历中，我们看

到递归思想的应用，下面给出的改写算法，也是通过递归的方式完成上述操作，

本算法具体思想由读者去进一步思考。

StatusCreatBiTree2(BiTreePtr&T){

staticchartree[100];

staticintx=O;

if(x==O)scanf("%s",tree);

switch(tree[x]){

casebreak;〃读入空格后继续读取

case

X++；

CreatBiTree2(T->left));〃开始递归处理该结点的左子树

if(tree[x]==','){x++;CreatBiTree2(T->right));}

〃对于逗号，退出到该层递归后处理结点右子树

if(tree[x]==')'){x++;CreatBiTree2(T);}

〃对于右括号，退出到该层递归后处理新结点

break;

case'"break;〃对于右括号不作任何处理，退出一层递归

case',':break;〃对于逗号，退出一层递归后处理结点右子树

caseNULL:break;〃数组tree尾部

default:

if(!(T=(BiTreeNode*)malloc(sizeof(BiTreeNode))))

exit(OVERFLOW);

T->data=tree[x];T->left=T->right=NULL;x++;

CreatBiTree2(T);

)

returnOK;

)

算法4-7二叉链表的递归生成算法

求二叉树的深度

该算法采用递归的思想：若一棵二叉树为空，则它的深度为0,否则它的深

度等于左子树和右子树中的最大深度加1。设加pthL为左子树的深度，d叩thR

为右子树的深度，则二叉树的深度为：

max(depthL,depthR)+1

其中max函数表示取参数中的较大者。该算法具体描述如下：

IntBiTreeDepth(BiTreePtrT){

if(T==NULL)

returnO;〃对于空树，返回0并结束递归

else{

intdepthL=BiTreeDepth(T->left);〃计算左子树的深度

intdepthR=BiTreeDepth(T->right);〃计算右子树的深度

return(depthL>depthR)?depthL+l:depthR+l;〃返回树的深度

)

)

算法4-8二叉树的深度求解算法

删除二叉树中指定结点

要删除指定结点及其左右子树，需分三种情况讨论：

i.被删除结点无前驱，即树的根结点，则先清空根结点的左子树，再清空

右子树，最后删除(即释放)根结点，并把根指针置空。

ii.被删除结点无后继，即叶子结点，则释放该结点，并且将其双亲结点指

向该结点的指针置空。

iii.被删除结点有后继和前驱，则清空该结点左右子树，然后释放该结点，且

将其双亲结点指向该结点的指针置空。

以上三种情况可归结为，判断该结点是否有后继，若有，则以递归的方式清

空左右子树，若无则不操作；判断该结点是否有双亲结点，若有则将其指向该结

点的指针置空，若无则不操作；释放该结点空间。具体算法描述如下：

StatusDelBiTreeNode(BiTreePtr&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!=NULL){

ClearBiTree(T->left);〃删除左子树

ClearBiTree(T->right);〃删除左子树

free(T);〃释放根结点

T=NULL;〃根指针置空

)

)

算法4-11清空二叉树的算法

第三节线索二叉树

遍历二叉3实现了树型非线性结构的线性化，形成了二叉树结点的线性序列。为

了便于查找某个结点在线性序列中的前驱和后继信息，需要将二叉树线索化。

1、线索链表的数据类型

1、线索链表的数据类型

作为二叉树基本的操作，遍历二叉树是以一定规则将二叉树中的结点排成一个线

性序列，这可看成是对树这种非线性结构进行线性化的操作，它使得每个结点(除

第一个和最后一个外)在这个线性序列中都有唯一的直接前驱和直接后继。当以

二叉链表作为存储结构时，只能较为方便地找到结点的左右孩子的信息，而不能

直接得到在结点的线性序列中的前驱与后继信息，这种信息只有在遍历的动态过

程中才能得到。为了能方便获得和利用某种遍历过程中的前驱与后继结点的信息,

可以在每个结点中设置两个指针分别保存它们，但我们注意到在二叉链表中有大

量的空指针(n个结点的二叉链表中有n+1个空链域)，我们可以充分利用这些

空链域来存放结点的前驱和后继的信息。具体来说，每个结点有左(右)子结点

时，其左(右)指针指向该子结点，或无左(右)子结点，则其左(右)指针指

向其前驱(后继)结点。当然为了区分这些指针是指向其子结点还是指向其前驱

或后继结点，需要在结点的数据类型中增加两个标志域Itag、rtag,如图4.11

所示。以这种结点类型构成的二叉链表作为二叉树的存储结构，叫做线索链表，

其中指向结点前驱或后继的指针称为线索，加上线索的二叉树称为线索二叉树。

其中：

所以，线索二叉树结点的存储结构为：

指针，线索

typedefenum{LinkzThread}PTag;//Link==0：Thread==l：

typedefstructBiThrNode{

ElemTypedata;

structBiThrNode*left,*right;〃左右孩子指针

PTagltag,rtag;〃左右标志

}BiThrNode,*BiThrTree;

2、二叉树的中序线索化算法

2、二叉树的中序线索化算法

这个过程实际上就是将已经建立好的二叉链表中的空指针改为指向前驱或者后

继的线索。由于在二叉树的遍历过程中，我们可以得到结点的前驱或后继的信息,

因此，线索化的过程即为在遍历过程中修改空指针的过程。为了能在遍历过程中

记录访问结点的先后关系，我们附设一个全局变量指针pre始终指向刚刚访问过

的结点。若指针指向当前访问的结点，则pre指向它的前驱，而当前访问的结点

又是pre的后继。pre的初值为NULL。二叉树的中序线索化算法如下所示：

StatusInOrderThreading(BiThrTree&T){

〃中序遍历二叉树T,并将其中序线索化，T指向树或子树的根结点。

p=T;

if(P){

InOrderThreading(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、中序线索二叉树的遍历算法

在线索二叉树上进行遍历，只需要从序列的第一个结点开始访问，然后通过依次

寻找结点的后继进行遍历，当后继为空时，遍历即可结束。当然，线索二叉树总

是与某种遍历次序相关的，我们下面主要以中序遍历为主来考虑线索二叉树。

以图4.12为例，树中所有叶子结点的左、右链是线索，此时，右链域直接指示

了结点的后继，如结点g的