第5章树和二叉树
树状结构是一种典型的非线性逻辑结构，常用的树状结构包括树和二叉树。树状结构中数据元素之间为一对多的关系，也可以表示成层状关系。树状结构在现实生活中的应用十分广泛，例如族谱、计算机中的文件组织、部门结构等。
树和二叉树同属于树状结构。二叉树的子树若不为空，则严格区分左右。二叉树的物理结构包括顺序存储结构、二叉链表、三叉链表。其中，二叉链表的使用最为广泛。二叉树的操作主要有初始化、销毁、前序遍历、中序遍历、后序遍历和层次遍历等。





5.1树的逻辑结构
5.1.1树的基本术语
1. 树的定义

在树中一般把数据元素称为结点(node)。
树(tree)是n(n≥0)个结点组成的有限集合。当n=0时，称为空树。当n>0时为非空树，需同时满足以下条件： 
（1） 有且仅有一个特定的称为根(root)的结点； 
（2） 当n>1时，除了根结点之外，其余的结点可以划分成m(m≥1)个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并且称为根结点的子树(subtree)。
树是采用递归方式定义的。如图51所示，图51(a)是一棵树，图51(b)不是树，因为除了根之外的其余结点不能划分成互不相交的集合。



图51树结构和非树结构示例


2. 基本术语
1） 结点的度、树的度
结点所具有的子树的棵数，称为结点的度(degree)。树中最大的结点的度称为树的度。例如图51(a)所示的树，结点B的度为2，结点A的度为3，树的度为3。

2） 叶子结点、分支结点
度为0的结点称为叶子结点(leaf node)，也称为终端结点； 度不为0的结点称为分支结点(branch node)，也称为非终端结点。图51(a)所示的树中，结点E、F、H、I、D为叶子结点，其他结点为分支结点。
3） 孩子结点、双亲结点
某结点子树的根结点称为该结点的孩子结点(children node)，该结点是孩子结点的双亲结点(parent node)。图51(a)所示的树中，结点B、C、D是结点A的孩子结点，结点A是结点B、C、D的双亲结点。
4） 兄弟结点、党兄弟结点
具有同一个双亲的结点互称为兄弟结点(brother node)，双亲互为兄弟的结点为堂兄弟结点。图51(a)所示的树中，结点B、C、D为兄弟结点，结点E和G为堂兄弟结点。
5） 路径、路径长度
如果树的结点序列a1,a2,…,an满足以下关系： 结点ai是结点ai+1的双亲(1≤i<n)，即序列中相邻的两个结点，前一个是后一个的双亲，则把序列a1,a2,…,an称为结点a1至结点an的路径(path)。路径上经过的分支数称为路径长度(path length)。树中任意两个结点之间如果存在路径，则路径是唯一的。图51(a)所示的树中，从结点A到结点I的路径是A、C、G、I，路径长度是3。
6) 祖先、子孙
如果从结点x到结点y存在路径，则结点x是结点y的祖先(ancestor)，结点y是结点x的子孙(descendant)。显然，一个结点的子树中所有的结点都是该结点的子孙，该结点是子树中所有结点的祖先。
7） 结点的层数、树的深度（高度）
根结点所在的层为第1层，对其余结点，若结点在第k层上，则其孩子在第k+1层上。树中所有结点的最大的层数为树的深度(depth)，也称为树的高度。图51(a)所示的树的深度为4。
8） 结点的层序编号
将树中的结点按照从上到下、从左到右的顺序从1开始采用连续的自然数编号，得到的编号称为结点的层序编号(level code)。图51(a)所示的树中，结点A的层序编号为1，结点E的层序编号为5。
9） 有序树、无序树



图52有序树和无序树示例

如果一棵树的子树从左到右没有顺序，交换子树的顺序，仍然是同一棵树，则称其为无序树(unordered tree)。如果一棵树的子树从左到右是有顺序的，交换子树的顺序，则和原树不再是同一棵树，则称其为有序树(ordered tree)。例如图52所示的两棵树，如果两棵树都是无序树，则两棵树是同一棵树。如果都是有序树，则不是同一棵树。“数据结构”课程中讨论的一般都是有序树。
10） 森林
m(m≥0)棵互不相交的树构成的集合称为森林(forest)。任何一棵非空树，根结点的子树可以看作一个森林。例如图51(a)所示的树中，根结点A的3棵子树可以看作一个森林。
5.1.2树的抽象数据类型定义
树的应用非常广泛，在不同的场合下的抽象数据类型不同，此处只给出最基本的操作。
树的抽象数据类型定义为： 
ADT Tree{
数据对象： 
D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系： 
结点之间具有一对多的关系，根结点无双亲，叶子结点无孩子，其他结点只有一个双亲和多个孩子； 
基本运算： 
InitTree： 初始化空树； 
DestroyTree： 销毁树； 
PreOrder： 先序遍历树； 
PostOrder： 后序遍历树； 
LevelOrder： 层序遍历树； 
};
5.1.3树的遍历
树的遍历指的是从根结点出发，将所有结点访问一次且仅访问一次。访问指的是对结点进行的某种抽象操作，此处简化为对结点数据的输出。树的遍历实际上是在非线性结构的基础上得到线性序列，因此访问次序尤其重要。按照访问次序，树的遍历分为前序遍历、后序遍历和层序遍历。
1. 前序遍历
树的前序遍历操作为： 
若树为空，则空操作返回，否则
（1） 访问根结点； 
（2） 按照从左到右的顺序前序遍历根结点的每一棵子树。
例如图51(a)所示的树，其前序遍历序列为A B E F C G H I D，前序遍历序列中根在最前面，任意一个结点肯定出现在其子树结点的前面。
2. 后序遍历
树的后序遍历操作为： 
若树为空，则空操作返回，否则
（1） 按照从左到右的顺序后序遍历根结点的每一棵子树； 
（2） 访问根结点。
例如图51(a)所示的树，其后序遍历序列为E F B H I G C D A，后序遍历序列中根在最后面，任意一个结点肯定出现在其子树结点的后面。
3. 层序遍历
树的层序遍历操作定义为按照结点从上到下、从左到右的次序访问结点，或者按照结点的层序编号访问结点。例如图51(a)所示的树，其层序遍历序列为A B C D E F G H I。





5.2树的存储结构
树的存储结构需要存储结点的信息以及结点之间的逻辑关系，即结点之间的双亲与孩子的逻辑关系。
5.2.1双亲表示法
树中的每个结点都有且仅有一个双亲结点，使用一维数组来表示树，数组的每一个元素是一个PNode，对应树的结点，PNode结点包括数据域data以及结点的双亲在一维数组中的下标parent。结点在一维数组中按层序编号排序。PNode定义如下。



图53树的双亲

表示法


template <class ElemType>

struct PNode{

ElemType data;

int parent;

};

例如图51(a)所示的树，其对应的双亲表示法如图53所示。
在树的双亲表示法中，求已知结点的双亲非常方便，但是求结点的孩子则需要遍历一维数组。
5.2.2孩子链表表示法
因为树中每个结点的孩子数目不确定，因此可以将每个结点所有的孩子使用单链表表示，将n个结点的孩子链表的头指针存储到一维数组中，n个结点的数据域也存储到一维数组中，此一维数组称为表头数组，表头数组的每个元素为表头



图54孩子链表表示法的结点结构

结点。则孩子结点和表头结点的结构如图54所示。
孩子结点和表头结点的结构定义如下。

struct CNode{

int child;/*孩子结点在表头数组中的下标*/

CNode *next; /*双亲的下一个孩子*/

};

template <class ElemType>

struct HNode{

ElemType data; /*数据域，存储结点的数据信息*/

CNode *firstChild; /*表头结点的第一个孩子*/

};

例如图51(a)所示的树，其孩子链表表示法如图55所示。



图55树的孩子链表表示法


5.2.3孩子兄弟表示法
树的孩子兄弟表示法又称为二叉链表表示法，链表中的每个结点除了数据域外，还包括两个指针域，分别指向结点的第一个孩子和右兄弟，链表的结点结构如图56所示。



图56孩子兄弟表示法的

结点结构

其中，data为数据域，用于存储该结点的数据信息； firstChild为指向第一个孩子结点的指针； rightSib为指向右兄弟的指针。结点定义如下。

template <class ElemType>

struct CSNode{

ElemType data;

CSNode<ElemType> *firstChild, *rightSib;

};

图51(a)所示的树的孩子兄弟表示法如图57所示。



图57树的孩子兄弟表示法







5.3二叉树的逻辑结构
二叉树(binary tree)是另一种重要的树状结构，因其结构相对简单，因此具有更广泛的应用。一般可以将树的问题转化成二叉树的问题进行处理。
5.3.1二叉树的定义
二叉树采用递归方式定义。二叉树是n(n≥0)个结点的有限集合。当n=0时为空二叉树。当n>0时，有且仅有一个称为根的结点； 除了根结点之外，其余的结点可以分为互不相交的两部分，这两部分又分别是一棵二叉树，并且称为根的左子树和右子树。
二叉树和树是两种不同的树状结构。二叉树的度最大为2，当二叉树中某个结点只有一棵子树时，须严格区分是左子树还是右子树。二叉树的基本形态有五种，如图58所示。



图58二叉树的基本形态


斜树、满二叉树、完全二叉树是几种特殊的二叉树。
1. 斜树
斜树(oblique tree)分为左斜树(left oblique tree)和右斜树(right oblique tree)。左斜树是所有的分支结点都只有左子树的二



图59斜树

叉树，右斜树是所有的分支结点都只有右子树的二叉树，例如，图59(a)为左斜树，图59(b)为右斜树。
斜树的每一层只有一个结点，因此斜树的结点个数与其深度相同。但是结点个数与其深度相同的二叉树不一定是斜树。
2. 满二叉树
如果一棵二叉树的所有分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，则此二叉树是满二叉树(full binary tree)。例如，图510(a)为满二叉树，图510(b)不是满二叉树，因为其叶子结点不在同一层上。



图510满二叉树和非满二叉树


满二叉树的特点包括： 
（1） 所有的叶子结点都在同一层； 
（2） 只有度为0和度为2的结点。
3. 完全二叉树
对具有n个结点的二叉树进行层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点的位置完全相同，则这棵二叉树为完全二叉树(complete binary tree)。例如，图511(a)为完全二叉树，图511(b)不是完全二叉树，因为6号结点的位置和满二叉树中的6号结点的位置不同。



图511完全二叉树和非完全二叉树


显然，满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。
完全二叉树的特点包括： 
（1） 叶子结点只能出现在最下两层，并且最后一层的叶子集中出现在左侧位置。
（2） 最多有一个度为1的结点，而且该结点只有左孩子，没有右孩子。
完全二叉树也可以看作在满二叉树的最后一层从右至左连续去掉若干个结点。
5.3.2二叉树的性质
性质1二叉树的第i(i>0)层上最多有2i-1个结点。
证明： 可以采用数学归纳法证明。
当i=1时，只有一个根结点，2i-1=20=1，结论成立。
假设当i=k时结论成立，即第k层上最多有2k-1个结点，当第k层的每个结点都有左右两个孩子时，第k+1层的结点数最多，即2k-1×2=2k，则当i=k+1时，结论也成立。因此，结论成立。
性质2深度为k(k>0)的二叉树中，最多有2k-1个结点，最少有k个结点。
证明： 由性质1可知，二叉树的第i层上最多有2i-1个结点，则深度为k的二叉树，只要每一层的结点数最多，则二叉树的结点总数最多。


∑ki=12i-1=2k-1



深度为k的二叉树每层至少有一个结点，因此最少有k个结点。
性质3在一棵非空的二叉树中，如果叶子结点的个数为n0，度为2的结点的个数为n2，则n0=n2+1。
证明： 假设二叉树的结点总数为n，度为1的结点总数为n1，因为二叉树中所有结点的度都小于等于2，因此


n=n0+n1+n2（51）



假设二叉树的分支总数为B，树状结构的分支总数等于各个结点的度数之和，因此


B=0×n0+n1×1+n2×2=n1+2n2（52）



又因为在非空的树状结构中，结点个数总是比分支个数多一个，即


n=B+1



由式（51）和式（52）可得： 


n0=n2+1



例51具有n个结点的满二叉树的叶子结点和度为2的结点各有多少个？
因为满二叉树中没有度为1的结点，因此n0+n2=n，根据二叉树的性质可知n0=n2+1，因此n0=n+12，n2=n-12。
性质4具有n个结点的完全二叉树的深度为
lbn
+1。



图512深度为k的完全二叉树的

结点数范围

证明： 假设具有n个结点的完全二叉树的深度为k，完全二叉树的最后一层的结点个数最少是1个，最多是满二叉树的状态，如图512所示。
由图512可知下式成立： 


2k-1≤n<2k



对不等式取对数： 


k-1≤lbn<k


即


lbn<k<lbn+1


由于k取正整数，所以k=
lbn
+1。
性质5对一棵具有n个结点的完全二叉树从1开始进行层序编号，则对于任意的编号为i(1≤i≤n)的结点（简称为结点i），有： 
（1） 如果i>1，则结点i的双亲的编号为
i/2
，否则i是根结点，无双亲。
（2） 如果2i≤n，则结点i的左孩子的编号为2i，否则结点i无左孩子。
（3） 如果2i+1≤n，则结点i的右孩子的编号为2i+1，否则结点i无右孩子。
证明： 此性质可使用数学归纳法证明，感兴趣的读者可自行完成。
5.3.3二叉树的抽象数据类型定义
相对于树来说，二叉树的应用更广泛，在不同的场合下的抽象数据类型定义不同，此处只给出二叉树最基本的操作。抽象数据类型定义为： 
ADT BiTree{
数据对象： 
D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系： 
结点之间具有一对多的关系，根结点无双亲，叶子结点无孩子，其他结点只有一个双亲，最多有左、右两个孩子； 
基本运算： 
InitBiTree： 初始化二叉树； 
DestroyBiTree： 销毁二叉树； 
PreOrder： 先序遍历二叉树； 
InOrder： 中序遍历二叉树； 
PostOrder： 后序遍历二叉树； 
LevelOrder： 层序遍历二叉树； 
};
5.3.4二叉树的遍历
遍历是二叉树最基本的操作。二叉树的遍历指的是从根结点出发，将所有的结点访问一次并且仅访问一次。一棵二叉树可以划分为根、左子树、右子树三个部分。根据访问次序的不同可以将二叉树的遍历分为前序遍历、中序遍历、后序遍历和层序遍历。
1. 前序遍历
前序遍历二叉树的操作定义为： 
若二叉树为空，则空操作返回； 否则



图513一棵二叉树

（1） 访问根结点。
（2） 前序访问根结点的左子树。
（3） 前序访问根结点的右子树。
显然，二叉树的前序遍历是一个递归的过程。例如图513所示的二叉树，其前序遍历序列为A B D G E C F。任何一棵非空的二叉树的前序遍历序列的第一个结点是根结点。
2. 中序遍历
中序遍历二叉树的操作定义为： 
若二叉树为空，则空操作返回； 否则
（1） 中序遍历根结点的左子树。
（2） 访问根结点。
（3） 中序遍历根结点的右子树。
图513所示的二叉树的中序遍历序列为D G B E A C F。
3. 后序遍历
后序遍历二叉树的操作定义为： 
若二叉树为空，则空操作返回； 否则
（1） 后序遍历根结点的左子树。
（2） 后序遍历根结点的右子树。
（3） 访问根结点。
图513所示的二叉树的后序遍历序列为G D E B F C A。任何一棵非空的二叉树的后序遍历序列的最后一个结点是根结点。
可见，在二叉树的前序、中序、后序遍历序列中叶子结点G、E、F的相对次序不变。
4. 层序遍历
层序遍历是从根结点开始，按照从上到下、从左到右的顺序遍历二叉树的结点，或者按照结点的层序编号遍历。图513所示的二叉树的层序遍历序列为A B C D E F G。





5.4二叉树的存储结构及实现
二叉树的存储结构同样需要存储两方面的内容，即二叉树的结点的数据信息以及各结点之间的逻辑关系。二叉树的存储结构包括顺序存储结构、二叉链表、三叉链表，其中二叉链表是最常用的存储结构，一般的二叉树的操作通常以二叉链表结构存储二叉树。
5.4.1顺序存储结构
顺序存储结构指的是使用一维数组存储二叉树的结点。由于完全二叉树的结点的层序编号可以反映结点之间的逻辑关系，因此可以使用和完全二叉树的结点编号相对应的数组下标来存储结点信息，例如图511(a)所示的完全二叉树可以使用图514所示的一维数组存储（数组的0号单元不使用）。



图514完全二叉树的顺序存储结构


对于一棵非完全二叉树，如果要使用顺序存储结构存储，则必须首先使用空结点将其补充成完全二叉树的形式，然后按照补充以后的结点的层序编号存储。例如图515所示的非完全二叉树补充成完全二叉树以后的形态，其对应的顺序存储结构如图516所示。




图515补充后的完全二叉树





图516二叉树的顺序存储结构



显然，补充的空结点会造成空间的浪费，浪费空间最严重的情况是右斜树。对于深度为k的右斜树，补充成完全二叉树的形态以后的结点数为2k-1个，因此其顺序存储结构中的空数据单元的个数为2k-1-k个。
5.4.2二叉链表
二叉树一般采用二叉链表存储。对于二叉树的每一个结点，都分配一个二叉链表结点，结点包括数据域data、左指针域lchild、右指针域rchild，其中，data用来保存结点的数据信息，lchild域指向结点的左孩子，rchild域指向结点的右孩子。结点结构如图517所示。
图513所示的二叉树的二叉链表存储结构如图518所示。




lchilddatarchild



图517二叉链表的结点结构





图518二叉链表存储结构



由图518可见，当二叉树的结点个数为n时，共分配2n个指针，被占用的指针为n-1个，还存在n+1个空指针。
使用C++语言描述二叉链表结点的结构定义如下。

template <class ElemType>

struct BiNode{

ElemType data;

BiNode<ElemType> *lchild, *rchild;

};

使用C++语言中的类模板描述二叉链表如下。

template <class ElemType>

class BiTree{

public:

/*构造函数，建立一棵二叉树*/

BiTree() {

root = Creat(root);

}

/*析构函数，释放各结点*/

~BiTree() {

Release(root);

}

/*前序遍历二叉树*/

void PreOrder() {

PreOrder(root);

}

/*中序遍历二叉树*/

void InOrder() {

InOrder(root);

} 

/*后序遍历二叉树*/

void PostOrder() {

PostOrder(root);

}

/*层序遍历二叉树*/

void LevelOrder() {

LevelOrder(root);

};                 

private:

BiNode<ElemType> *root;/*指向根结点的头指针*/

BiNode<ElemType> *Creat(BiNode<ElemType> *bt); /*构造函数调用*/

void Release(BiNode<ElemType> *bt); /*析构函数调用*/

void PreOrder(BiNode<ElemType> *bt); /*前序遍历函数调用*/

void InOrder(BiNode<ElemType> *bt); /*中序遍历函数调用*/

void PostOrder(BiNode<ElemType> *bt); /*后序遍历函数调用*/

void LevelOrder(BiNode<ElemType> *bt); /*层序遍历函数调用*/

};

以上BiTree类模板中，为了避免外部对象直接访问其私有成员root指针，在公有的无参数方法中又调用了私有的带参数方法。
1. 前序遍历
前序遍历算法使用C++语言描述如下。

template <class ElemType>

void BiTree<ElemType>::PreOrder(BiNode<ElemType> *bt) {

if(bt == NULL)/*递归调用的边界条件*/

return;

else {		

cout<<bt->data<<" "; /*访问根结点*/

PreOrder(bt->lchild); /*前序递归遍历左子树*/

PreOrder(bt->rchild); /*前序递归遍历右子树*/

}

}

2. 中序遍历
中序遍历算法使用C++语言描述如下。

template <class ElemType>

void BiTree<ElemType>::InOrder(BiNode<ElemType> *bt) {

if(bt == NULL)  

return; /*递归调用的边界条件*/	          

else {	

InOrder(bt->lchild); /*中序递归遍历左子树*/

cout<<bt->data<<" "; /*访问根结点*/

InOrder(bt->rchild); /*中序递归遍历右子树*/

}

}

3. 后序遍历
后序遍历算法使用C++语言描述如下。

template <class ElemType>

void BiTree<ElemType>::PostOrder(BiNode<ElemType> *bt) {

if(bt == NULL)  

return; /*递归调用的边界条件*/

else {	

PostOrder(bt->lchild); /*后序递归遍历左子树*/

PostOrder(bt->rchild); /*后序递归遍历右子树*/

cout<<bt->data<<" "; /*访问根结点*/

}

}

可见，二叉树递归的前序、中序、后序遍历的算法非常类似，区别主要在于访问二叉树的根、左子树、右子树的顺序不同。
4. 层序遍历
对二叉树进行层序遍历时，需要使用队列来保存结点指针，以便于寻找其左右孩子结点。使用伪代码描述二叉树的层序遍历算法如下。

1. 顺序队列Q初始化； 

2. 如果二叉树不为空，则将根指针入队； 

3. 当顺序队列Q不为空时循环： 

2.1 q =队列Q的队头元素出队； 

2.2 访问q的数据域； 

2.3 若q存在左孩子，则将其左指针入队； 

2.4若q存在右孩子，则将其右指针入队； 



使用C++语言描述层序遍历算法如下。

template <class ElemType>

void BiTree<ElemType>::LevelOrder(BiNode<ElemType> *bt) {

const int MaxSize = 100;

/*采用顺序队列，假设不会发生溢出*/

int front = -1, rear = -1;  

BiNode<ElemType> *Q［MaxSize］, *q;

if(bt == NULL) 

return;

else {

Q［rear++］ = bt;/*bt入队*/

/*队列非空时循环*/

while(front != rear) {

q = Q［front++］; /*队头出队*/

cout<<q->data<<" "; /*访问队头*/	

if(q->lchild != NULL) /*如果队头有左孩子，则左孩子入队*/

Q［rear++］ = q->lchild;		

if(q->rchild != NULL) /*如果队头有右孩子，则右孩子入队*/

Q［rear++］ = q->rchild;

}

}

}

5. 构造函数
要对二叉树进行遍历，必须首先在内存中创建一棵由二叉链表存储的二叉树。二叉树的一个遍历序列不能唯一地确定二叉树，例如前序遍历序列、中序遍历序列或者后序遍历序列。由二叉树得到扩展的二叉树，再由扩展的二叉树的前序遍历序列则可



图519二叉树和扩展二叉树

以唯一地确定二叉树。所谓扩展的二叉树指的是在原二叉树的末端添加虚结点，使原二叉树的所有结点的度都变为2。扩展的结点的数据可使用不会出现在正常结点的数据表示，例如'#'。例如，图519(a)为原二叉树，图519(b)为扩展二叉树。扩展二叉树的前序遍历序列为A B # # C D # # #。
使用扩展的二叉树的前序序列创建二叉链表是递归的过程。假设二叉树的结点数据类型为char。首先输入根结点对应的字符，如果输入的是'#'，则二叉树为空二叉树，bt=NULL； 否则创建根结点，并为根结点的数据域赋值。然后递归地创建根结点的左子树和根结点的右子树。算法描述如下。

template <class ElemType>

BiNode<ElemType> *BiTree<ElemType>::Creat(BiNode<ElemType> *bt) {

char ch;

cout<<"请输入创建一棵二叉树的结点数据： "<<endl;

cin>>ch;

/*'#'代表空二叉树*/

if(ch == '#') 

return NULL;

else { 

bt = new BiNode<ElemType>;/*生成新结点*/

bt->data = ch;

bt->lchild = Creat(bt->lchild); /*递归创建左子树*/

bt->rchild = Creat(bt->rchild); /*递归创建右子树*/

} 

return bt;

}

6. 析构函数
可利用二叉树的后序遍历释放二叉链表的各结点。算法描述如下。

template <class ElemType>

void BiTree<ElemType>::Release(BiNode<ElemType> *bt) {

/*按照后序遍历的顺序释放二叉树*/




图520二叉链表实现的运行结果


if(bt != NULL) {                  

Release(bt->lchild);/*释放左子树*/

Release(bt->rchild); /*释放右子树*/

delete bt; /*删除根结点*/

}  

}

创建二叉链表及实现二叉树各种遍历的详细代码可参照ch05＼BiTree目录下的文件。当创建的二叉树为图519(a)时，扩展的前序遍历序列为AB##CD###时（此处序列中没有空格），运行结果如图520所示。
5.4.3三叉链表
在二叉链表中，可以从已知结点很方便地访问结点的左孩子或者右孩子，但是访问双亲结点不方便，需要通过二叉树的遍历完成。可在二叉链表结点的基础上再增加一个指向双亲结点的指针，即为三叉链表，三叉链表结点的结构定义描述如下。

template <class ElemType>

struct TriNode{

ElemType data;

TriNode<ElemType> *lchild, *rchild, *parent;

};

图513所示的二叉树的三叉链表存储结构如图521所示。



图521二叉树的三叉链表存储结构

5.5二叉树的应用
5.5.1非递归遍历二叉树

二叉树的递归遍历算法虽然简单，可读性好，但是递归的程序一般执行效率不高。因此，可采用非递归的方法遍历二叉树。
1. 前序非递归遍历算法
在非递归遍历算法中，关键的问题是当访问完当前结点，再访问完当前结点的左子树以后，如何再访问当前结点的右子树，因此，需要使用栈保存指向访问过的结点的指针。
假设当前指针为bt，则按照bt是否为空可分为两种情况。
（1） 当bt != NULL时，访问bt>data，bt入栈。
（2） 当bt == NULL时，需要判断栈的情况。如果栈为空，则遍历结束。如果栈不为空，说明当前栈顶指针的左子树为空或者栈顶指针的左子树已经访问完，栈顶出栈，继续访问其右子树。
例如图519(a)所示的二叉树的前序非递归遍历的执行过程如表51所示。



表51前序非递归遍历的执行过程





步骤指针bt访 问 结 点栈S说明

1空初始化空栈S
2AAA访问A，A入栈，找A的左子树
3BBA B访问B，B入栈，找B的左子树
4NULLAB出栈，找B的右子树
5NULL空A出栈，找A的右子树
6CCC访问C，C入栈，找C的左子树
7DDC D访问D，D入栈，找D的左子树
8NULLCD出栈，找D的右子树
9NULL空C出栈，找C的右子树
10NULL空bt=NULL且栈为空，遍历结束

使用伪代码描述前序非递归遍历算法如下。

1. 栈S初始化;

2. 在bt不为空或栈S不为空时循环： 

2.1当bt不为空时循环： 

2.1.1输出bt>data； 




2.1.2 bt入栈S； 

2.1.3继续遍历bt的左子树； 

2.2 如果栈S不为空： 

2.2.1栈S栈顶出栈并赋值给bt； 

2.2.2遍历bt的右子树； 



使用C++语言描述的前序遍历非递归算法如下。

void BiTree::PreOrder(BiNode *bt) {

SeqStack<BiNode *> S;

while(bt != NULL || S.Empty() != 1) {

while(bt != NULL) {

cout<<bt->data<<" ";

S.Push(bt);

bt = bt->lchild;

}

if(S.Empty() != 1) {

bt = S.Pop();

bt = bt->rchild;

}

}

}


此算法中使用了第3章的类模板SeqStack。
2. 中序非递归遍历算法
中序非递归遍历二叉树与前序非递归遍历二叉树非常类似，区别仅在于当bt不为空时，在前序非递归遍历中，先访问结点，然后再入栈； 而在中序非递归遍历算法中，当bt不为空时，先入栈，当栈顶的指针出栈时才进行访问，即： 
（1） 当bt != NULL时，bt入栈。
（2） 当bt == NULL时，如果栈为空，则遍历结束。如果栈不为空，则说明当前栈顶指针的左子树为空或者栈顶指针的左子树已经访问完，栈顶出栈，访问，并继续访问其右子树。
使用C++语言描述中序非递归遍历算法如下。

void BiTree::InOrder(BiNode *bt) {

SeqStack<BiNode *> S;

while(bt != NULL || S.Empty() != 1) {

while(bt != NULL) {

S.Push(bt);

bt = bt->lchild;

}

if(S.Empty() != 1) {

bt = S.Pop();

cout<<bt->data<<" ";

bt = bt->rchild;

}

}

}

3. 后序非递归遍历算法
后序非递归遍历算法和前序及中序非递归算法不同。在后序非递归遍历算法中，对于当前的非空指针bt，只有从bt的右子树返回以后，才能对bt进行访问。
对于非空栈里的栈顶指针ptr，在遍历的过程中会遇到两次当前指针bt=NULL。第一次bt=NULL时，表示栈顶指针ptr的左子树为空，或者栈顶指针ptr的左子树已经访问完，即从ptr的左子树返回。第二次bt=NULL时，表示栈顶指针ptr的右子树为空，或者栈顶指针ptr的右子树已经访问完，即从ptr的右子树返回。显然，只有当栈顶指针ptr第二次遇到空指针bt时，即从ptr的右子树返回时，才能使ptr出栈，并访问其数据域。
为了方便区分从左子树还是从右子树返回，需要对入栈的元素类型进行调整，除了BiNode类型的指针以外，另加标志域flag，定义如下。

template <class ElemType>

struct Element{

BiNode<ElemType> *ptr;

int flag;

};

对于当前指针bt，存在以下情况： 
（1） 若bt不为空，则bt及flag为1入栈，继续访问bt的左子树。
（2） 若bt为空，则判断栈的情况。若栈为空，则遍历结束； 若栈不空，则判断栈顶的flag，如果栈顶的flag为1，说明从栈顶的左子树返回，将栈顶的flag改为2，继续访问栈顶的右子树； 如果栈顶的flag为2，则说明从栈顶的右子树返回，栈顶出栈并访问。图519(a)所示的二叉树的后序非递归遍历的执行过程如表52所示，结点字符后的数字为其flag值。



表52后序非递归遍历的执行过程





步骤指针bt访 问 结 点栈S说明

1空初始化空栈S
2AA1将A带标志1入栈，找A的左子树
3BA1B1将B带标志1入栈，找B的左子树
4NULLA1 B2将B的标志改为2，找B的右子树
5NULLBA1B出栈，访问B
6NULLA2将A的标志改为2，找A的右子树
7CA2 C1将C带标志1入栈，找C的左子树
8DA2 C1 D1 将D带标志1入栈，找D的左子树
9NULLA2 C1 D2将D的标志改为2，找D的右子树
10NULLDA2 C1D出栈，访问D
11NULLA2 C2将C的标志改为2，找C的右子树
12NULLCA2C出栈，访问C
13NULLA空A出栈，访问A

使用伪代码描述后序非递归遍历算法如下。

1. 栈S初始化;

2. 在bt不为空或栈S不为空时循环： 

2.1当bt不为空时循环： 

2.1.1 bt及flag=1入栈S； 

2.1.2继续遍历bt的左子树； 

2.2 在栈S不为空且栈顶的flag == 2时循环： 

2.2.1栈S栈顶出栈并赋值给bt； 

2.2.2访问bt； 

2.3若栈S不为空，则将栈顶的flag改为2，并继续访问其右子树； 



使用C++语言描述算法如下。

void BiTree::PostOrder(BiNode *bt) {

SeqStack<Element> S;

Element e;

/*bt不为空或者栈不为空*/

while(bt != NULL || S.Empty() == 0) {

while(bt != NULL) {

e.ptr = bt;

e.flag = 1;

S.Push(e);

bt = bt->lchild;

}

/*栈不为空并且栈顶的flag为2时，出栈并访问*/

while((S.Empty() == 0)&&(S.GetTop()).flag == 2) {

e = S.Pop();

cout<<e.ptr->data<<" ";

}

/*栈不为空，并且栈顶的flag为1时，将栈顶的flag更改为2，并访问其右孩子*/

if(S.Empty() == 0) {

e = S.Pop();

bt = e.ptr->rchild;

e.flag = 2;

S.Push(e);

}

}

}

二叉树非递归遍历的详细代码可参照ch05＼BiTreeNoReCur目录下的文件，二叉树为图519(a)所示的二叉树，非递归遍历的结果与递归遍历的结果相同。
5.5.2二叉树遍历的应用
二叉树的一些常见应用是以二叉树的遍历为基础的，例如求二叉树的深度、求二叉树的结点个数、求二叉树的叶子结点个数、输出二叉树的叶子结点等，此类应用一般使用递归算法解决。
1. 求二叉树的深度
当二叉树为空时，深度为0； 当二叉树不为空时，二叉树的深度为其根的左右子树的深度中较大的值再加1。算法描述如下。

template <class ElemType>

int BiTree<ElemType>::Depth(BiNode<ElemType> *bt) {

if(bt == NULL)

return 0;

else {

int dep1 = Depth(bt->lchild);

int dep2 = Depth(bt->rchild);

return (dep1 > dep2) ? (dep1 + 1) : (dep2 + 1);

}

}

2. 求二叉树的结点个数
求二叉树的结点个数时，可以利用二叉树的遍历，在遍历的过程中对结点进行计数。算法描述如下。

/*countNode为全局变量，初始化为0*/

template <class ElemType>

void BiTree<ElemType>::Count(BiNode<ElemType> *bt) {

if(bt != NULL) {

Count(bt->lchild);

countNode++;

Count(bt->rchild);

}

}

3. 求二叉树的叶子结点个数
求二叉树的叶子结点个数与求二叉树的结点总数类似，只有结点为叶子时才计数。算法描述如下。

/*countLeaf为全局变量，初始化为0*/

template <class ElemType>

void BiTree<ElemType>::CountLeaf(BiNode<ElemType> *bt) {

if(bt != NULL) {

if(bt->lchild == NULL && bt->rchild == NULL)

countLeaf++;

CountLeaf(bt->lchild);

CountLeaf(bt->rchild);

}

}

4. 输出二叉树的叶子结点
算法描述如下。

template <class ElemType>

void BiTree<ElemType>::PrintLeaf(BiNode<ElemType> *bt) {

if(bt != NULL) {

if(bt->lchild == NULL && bt->rchild == NULL) {

cout<<bt->data<<" ";

}




图522二叉树应用的运行结果


PrintLeaf(bt->lchild);

PrintLeaf(bt->rchild);

}

}

二叉树的常见应用的详细代码可参照ch05＼BiTreeApp目录下的文件，当构造如图513所示的二叉树时，二叉树的扩展前序序列为ABD#G##E##C#F##时，运行结果如图522所示。
5.5.3线索二叉树的构造和应用
在对二叉树进行各种操作时，有可能需要访问已知结点在某种遍历序列下的前驱结点或后继结点。含有n个结点的二叉树的二叉链表存储结构中仍然存在n+1个空指针，可以利用这些空指针为访问结点的前驱或后继提供便利。如果结点没有左孩子，则左指针可以指向前驱结点； 如果结点没有右孩子，则右指针可以指向后继结点。
指向前驱或后继的指针称为线索(thread)，将空指针更改为指向前驱或后继的过程称为线索化，加上线索的二叉树称为线索二叉树(thread binary tree)，加上线索的二叉链表称为线索链表(thread linked list)。
为了进一步区分指针是指向孩子还是指向前驱或后继，需要改造二叉链表的结点结构，在原有的基础上增加两个标志域ltag和rtag，结构如图523所示。




ltaglchilddatarchildrtag



图523线索链表的结点结构

其中，当ltag=0时，lchild指向左孩子； 当ltag=1时，lchild指向前驱。当rtag=0时，rchild指向右孩子； 当rtag=1时，rchild指向后继。线索链表中的结点使用C++语言描述如下。

template <class ElemType>

struct ThrBiNode{

ElemType data;

int ltag, rtag;

ThrNode<ElemType> *lchild, *rchild;	

};

由于二叉树的遍历序列有四种，因此线索链表也有四种，分别是前序线索二叉链表、中序线索二叉链表、后序线索二叉链表以及层序线索二叉链表。例如图513所示的二叉树，其中序线索二叉链表如图524所示。



图524中序线索二叉链表


使用C++的类模板描述中序线索二叉链表如下。

template <class ElemType>

class InThrBiTree{

public:	

InThrBiTree(); /*构造函数，建立一棵中序线索二叉树*/

ThrBiNode<ElemType> *Next(ThrBiNode<ElemType> *p); /*在中序线索二叉树上查找p的后继*/

void InOrder(); /*在中序线索二叉树上中序遍历*/

private:

ThrBiNode<ElemType> *root; /*指向根结点的头指针*/

ThrBiNode<ElemType> *pre; /*当前根结点的前驱结点*/

ThrBiNode<ElemType> *Creat(ThrBiNode<ElemType> *bt); /*构造函数调用*/

void ThrBiTree(ThrBiNode<ElemType> *bt);/*递归的中序线索化*/ 

};

因为在二叉链表线索化的过程中要访问当前结点的前驱结点，因此为线索二叉树添加私有属性pre指针。
1. 构造初始的线索二叉链表
构造初始的线索二叉链表与构造初始的二叉链表相似，区别主要在于结点的左右标志域ltag和rtag赋初值为0。算法描述如下。

template <class ElemType>

ThrBiNode<ElemType> *InThrBiTree<ElemType>::Creat(ThrBiNode<ElemType> *bt) {

char ch;

cout<<"请输入创建一棵二叉树的结点数据： "<<endl;

cin>>ch;

/*'#'代表空二叉树*/

if(ch == '#') 

return NULL;

else { 

bt = new ThrBiNode<ElemType>; /*生成新结点*/

bt->data = ch;

bt->ltag = 0; /*初始化标志域*/

bt->rtag = 0;

bt->lchild = Creat(bt->lchild); /*递归创建左子树*/

bt->rchild = Creat(bt->rchild); /*递归创建右子树*/

} 

return bt;

}

2. 中序线索化
中序线索化只能在遍历的过程中完成，因为只有在遍历的过程中，才能获取当前结点的前驱和后继信息。因为遍历是递归的过程，因此中序线索化也是递归的过程。对于当前的非空结点bt，需要进行以下操作： 
（1） 如果bt没有左孩子，则将其ltag改为1，将lchild改为指向其前驱结点； 
（2） 如果bt没有右孩子，则将其rtag改为1； 
（3） 如果结点pre的右标志为1，则将pre的rchild指向bt； 
（4） 将pre更新为当前结点bt。
使用伪代码描述中序线索化二叉链表的算法如下。

1. 如果二叉链表为空，则空操作返回； 

2. 对bt的左子树建立线索； 

2.1如果bt没有左孩子，则bt>ltag=1,bt>lchild=pre;

2.2如果bt没有右孩子，则bt>rtag=1;

2.3 如果pre>rtag=1，则pre>rchild=bt; 

2.4 pre=bt;

3. 对bt的右子树建立线索； 



使用C++语言描述算法如下。

template <class ElemType>

void InThrBiTree<ElemType>::ThrBiTree(ThrBiNode<ElemType> *bt) {

if(bt == NULL)

return;

ThrBiTree(bt->lchild); /*对左子树建立线索*/

if(bt->lchild == NULL) { /*设置bt的前驱线索*/

bt->ltag = 1;

bt->lchild = pre;

}

if(bt->rchild == NULL) { /*修改bt的右标志域*/

bt->rtag = 1;

}

if(pre != NULL && pre->rtag == 1) { /*设置pre的后继线索*/

pre->rchild = bt;

}

pre = bt; /*更新pre*/

ThrBiTree(bt->rchild); /*对右子树建立线索*/

}

3. 构造函数
类模板InThrBiTree的构造函数首先创建初始的线索二叉链表，因为遍历序列的第一个结点没有前驱，因此将pre初始化为NULL，然后调用中序线索化二叉树的方法。算法描述如下。

template <class ElemType>

InThrBiTree<ElemType>::InThrBiTree() {

/*创建未线索化的二叉树*/

root = Creat(root);

/*为pre赋初值*/

pre = NULL;

/*中序线索化二叉树*/

ThrBiTree(root);

}

4. 在中序线索二叉链表上求已知结点的后继
如果已经创建好中序线索二叉链表，则在其上求中序遍历的后继相对容易。对于已知结点p，如果p>rtag=1，则说明p没有右孩子，p>rchild即为其后继。如果p>rtag=0，则说明p存在右孩子，p>rchild为其右孩子，p的中序遍历的后继应为中序遍历p的右子树的第一个结点，即p的右子树最左下的结点。算法描述如下。

template <class ElemType>

ThrBiNode<ElemType> *InThrBiTree<ElemType>::Next(ThrBiNode<ElemType> *p) {

ThrBiNode<ElemType> *q;

if(p->rtag == 1) /*p无右孩子，rchild为线索，指向p的后继*/

q = p->rchild;

else { /*p有右孩子，后继为p的右子树最左下的结点*/

q = p->rchild;

while(q->ltag == 0)

q = q->lchild;

}

return q;

}

5. 在中序线索二叉链表上中序遍历
在非空的中序线索二叉链表上进行中序遍历只需要找到第一个结点，然后在当前结点存在后继时，循环寻找下一个结点即可。中序遍历的第一个结点为二叉链表的最左下的结点。算法描述如下。

template <class ElemType>

void InThrBiTree<ElemType>::InOrder() {

ThrBiNode<ElemType> *p;

if(root == NULL) 

return;

p = root;

while(p->ltag == 0) /*查找最左下结点*/

p = p->lchild;

cout<<p->data<<" ";

while(p->rchild != NULL) { /*查找下一个结点*/

p = Next(p);




图525线索二叉链表的运行结果


cout<<p->data<<" ";

}

cout<<endl;

}

实现线索二叉链表的详细代码可参照ch05＼InThrBiTree目录下的文件，当构造如图513所示的二叉树时，二叉树的扩展前序序列为ABD#G##E##C#F##时，运行结果如图525所示。





5.5.4赫夫曼树和赫夫曼编码
1. 赫夫曼树的定义

赫夫曼树(Huffman tree)也称为最优二叉树，应用非常广泛。
（1） 叶子结点的权值： 为二叉树的叶子赋予一个有意义的数值量。
（2） 二叉树的带权路径长度(weighted path length，WPL)： 假设二叉树具有n个带有权值的叶子结点，第i(1≤i≤n)个叶子结点的权值为wi，从根结点到第i个叶子结点的路径长度为li，则二叉树的带权路径长度为： 


WPL=∑ni=1wili





图526带权二叉树


例如图526所示的二叉树，其WPL=8×2+2×3+5×3+12×1=49。
（3） 赫夫曼树： 给定一组具有确定权值的叶子结点，构造出各种不同的二叉树中带权路径长度最短的二叉树称为赫夫曼树。
赫夫曼树中只有度为0和度为2的结点。另外，在赫夫曼树中通常权值越大的叶子结点离根越近，权值越小的叶子结点离根越远。
2. 赫夫曼树的构造
给定一组权值构造赫夫曼树的算法称为赫夫曼算法，其基本思想为： 
（1） 初始化： 由给定的n个权值{w1,w2,…,wn}构造n棵只包含一个根结点的二叉树，记为F={T1,T2,…,Tn}，第i棵二叉树根结点的权值为wi。
（2） 筛选与合并： 在F中选择两棵根结点权值最小的二叉树，分别作为左、右子树构造一棵新的二叉树，新二叉树的根结点的权值为左、右子树根结点权值的和。
（3） 删除与加入： 在F中删除作为左、右子树的二叉树，加入新构造的二叉树。
（4） 重复（2）和（3），直到F中只剩下一棵二叉树时，这棵二叉树即为赫夫曼树。
例52给定权值W={2,5,8,12}，图527给出了构造赫夫曼树的过程。



图527赫夫曼树的构造过程


由于合并二叉树时没有规定左子树或右子树，另外，有可能存在重复的权值，因此赫夫曼树是不唯一的。但是一旦确定了权值，赫夫曼树的带权路径长度是唯一的。由赫夫曼树的构造过程可知，总是由左、右子树确定根结点，因此使用三叉链表的静态链表的形式存储二叉树以实现赫夫曼算法。定义结点结构如下。

struct Element{

int weight; /*结点的权值*/

int lchild, rchild, parent; /*结点的左孩子、右孩子、双亲在一维数组中的下标*/

}

给定权值数组w［］及数组长度n，构造赫夫曼树的算法描述如下。

void HuffmanTree(element huffTree［］, int w［］, int n) {

int i, j, k;

int m1, m2;

/*结点初始化*/

for(i = 0; i < 2 * n - 1; i++) {

huffTree［i］.parent = -1;

huffTree［i］.lchild = -1;

huffTree［i］.rchild = -1;

}

/*构造初始的n棵二叉树*/

for(i = 0; i < n; i++) {

huffTree［i］.weight = w［i］;

}

for(k = n; k < 2 * n - 1; k++) {

/*取两棵根结点权值最小的赫夫曼树*/

/*m1确定初值*/

for(j = 0; j < k; j++) {

if(huffTree［j］.parent == -1) {

m1 = j;

break;

}

}

/*m2确定初值*/

for(j = 0; j < k; j++) {

if(huffTree［j］.parent == -1 && j != m1) {

m2 = j;

break;

}

}

if(huffTree［m2］.weight < huffTree［m1］.weight) {

int temp = m1;

m1 = m2;

m2 = temp;

}

/*确定根结点权值最小的两棵二叉树的下标*/

for(j = 0; j < k; j++) {

if(huffTree［j］.parent == -1 && j != m1 && j != m2) {

if(huffTree［j］.weight < huffTree［m1］.weight) {

m2 = m1;

m1 = j;

}

else if(huffTree［j］.weight < huffTree［m2］.weight) {

m1 = j;

}

}

}

/*将选中的两棵二叉树合并，并将根结点信息存于下标k处*/

huffTree［m1］.parent = k;

huffTree［m2］.parent = k;

huffTree［k］.lchild = m1;

huffTree［k］.rchild = m2;

huffTree［k］.weight = huffTree［m1］.weight + huffTree［m2］.weight;

}

}




图528构造赫夫曼树的运行结果

构造赫夫曼树的详细代码可参照ch05＼Huffman目录下的文件，当叶子结点的权值为2、5、8、12时，运行结果如图528所示。
3. 赫夫曼编码
如果一组编码中任意一个编码都不是其他编码的前缀，则称这组编码为前缀编码(prefix code)。前缀编码保证了解码的唯一性。等长编码指的是一组编码的长度都相等，不等长编码指的是一组编码的长度不完全相等。为了使编码总长度最短，对于不等长编码，应该使出现频次高的编码长度尽可能短，而出现频次低的编码长度可以适当加长。赫夫曼编码(Huffman code)是最经济的前缀编码。利用字符出现的频次作为叶子结点的权值构造赫夫曼树，赫夫曼树中规定左分支为0，右分支为1，从根结点到叶子的路径组成的0和1序列即为叶子结点对应字符的赫夫曼编码。
例53假设对于一组字符{A,B,C,D,E,F}，使用的频次分别是{45,13,12,16,9,5}，则构造的一棵赫夫曼树如图529(a)所示，其对应的赫夫曼编码如图529(b)所示。



图529赫夫曼树和赫夫曼编码


因为赫夫曼树不唯一，所以赫夫曼编码也不唯一。
5.5.5求二叉树的最小深度
二叉树的最小深度指的是从根结点到最近的叶子结点的距离。当二叉树为空时，返回0； 当二叉树的左子树为空时，返回右子树的最小深度加1； 当二叉树的右子树为空时，返回左子树的最小深度加1； 当二叉树的左右子树都不为空时，返回左右子树最小深度较小的值加1。使用C++语言描述算法如下。

template <class ElemType>

int BiTree<ElemType>::SmallestDepth(BiNode<ElemType> *bt) {

if(bt == NULL)   

return 0;  

if(bt->lchild == NULL)   

return SmallestDepth(bt->rchild) + 1;  

if(bt->rchild == NULL)  

return SmallestDepth(bt->lchild) + 1; 




图530求二叉树最小深度的

运行结果


int m = SmallestDepth(bt->lchild) + 1;

int n = SmallestDepth(bt->rchild) + 1;

return m < n ? m : n; 

}

求二叉树最小深度的详细代码可参照ch05＼ BiTreeSmallestDepth目录下的文件。当构造如图513所示的二叉树时，二叉树的扩展前序序列为ABD#G##E##C#F##时，运行结果如图530所示。
5.5.6判断二叉树是否是完全二叉树
要判断一棵二叉树是否是满二叉树，可以求二叉树的深度L，再求二叉树的叶子结点的个数N，如果满足条件N=2L-1，则二叉树是满二叉树，否则不是满二叉树。判断满二叉树的详细代码可参照ch05＼JudgeFullBiTree目录下的文件。
任意一棵二叉树都可以扩充成一棵满二叉树，如果用'#'表示扩充以后的空结点，在层序遍历一棵非完全二叉树时，非空结点之前会出现空结点； 而层序遍历一棵完全二叉树时，在非空结点之前不会再出现空结点，即一旦层序遍历中出现空结点，则之后再不会出现非空结点。如果在遍历二叉树时遇到空结点，整棵二叉树的遍历已经完成，则二叉树是完全二叉树； 如果遇到空结点时，整棵二叉树的遍历还没有结束，即又遇到了非空结点，则二叉树不是完全二叉树。判断完全二叉树的算法使用伪代码描述如下。

1. 初始化空顺序队列Q； 

2. 如果bt == NULL，返回1； 

3. bt入队； 

4. 当队列出队的指针p不为NULL时循环： 

4.1 p>lchild入队； 

4.2 p>rchild入队； 

5. 当队列不为空时循环： 

5.1 p =出队的指针； 

5.2 如果p不为空，则返回0

6. 返回1； 



使用C++语言描述算法如下。

template <class ElemType>

int BiTree<ElemType>::IsCompleteBiTree(BiNode<ElemType> *bt) {

CirQueue<BiNode<ElemType> *> Q;

BiNode<ElemType> *p;

if(bt == NULL) return 1; /*空二叉树*/

Q.EnQueue(bt);

/*当出队的队头指针不为空时，将其左、右指针入队*/ 

while((p = Q.DeQueue()) != NULL) {

Q.EnQueue(p->lchild);

Q.EnQueue(p->rchild);	

}

/*当遇到空指针时，判断队列中是否有非空指针*/

/*如果有，则不是完全二叉树*/

/*没有，则为完全二叉树*/

while(!Q.Empty()) {

p = Q.DeQueue();

if(p != NULL)

return 0;

}

return 1;

}




图531判断完全二叉树的

运行结果1

判断完全二叉树的详细代码可参照ch05＼JudgeCompleteBiTree目录下的文件，当构造的二叉树如图519(a)所示，输入扩展的前序遍历序列为AB##CD###时，运行结果如图531所示。
当构造的二叉树如图532所示时，输入的扩展的前序遍历序列为ABD##E##C##时，运行结果如图533所示。




图532一棵完全二叉树示意图





图533判断完全二叉树的运行结果2



5.5.7判断二叉树的结构是否对称
二叉树结构性对称指的是不考虑结点的数据值，对于二叉树中任意一个非空的结点，左、右孩子都不存在，或者左、右孩子都存在； 如果结点存在子树，则左、右子树的结构也分别是结构对称的。图534所示的二叉树结构不对称，图535所示的二叉树结构对称。




图534结构不对称的二叉树





图535结构对称的二叉树



如果二叉树为空，则是结构对称的。如果二叉树不为空，则判断其左、右子树是否是结构对称的。判断一棵非空的二叉树的左、右子树是否结构对称的算法描述如下。

template <class ElemType>

int BiTree<ElemType>::IsCheck(BiNode<ElemType> *lchild, BiNode<ElemType> *rchild) {

if(lchild == NULL && rchild == NULL)

return 1;

if(lchild == NULL || rchild == NULL)

return 0;

return IsCheck(lchild->lchild, rchild->rchild) && IsCheck(lchild->rchild, rchild->lchild);

}

判断一棵二叉树是否结构对称的算法描述如下。

template <class ElemType>

int BiTree<ElemType>::IsStructureSymmetric(BiNode<ElemType> *bt) {

if(bt == NULL)

return 1;

return IsCheck(bt->lchild, bt->rchild);

}

详细代码可参照ch05＼JudgeStructureSymmetirc目录下的文件，当二叉树如图534所示，输入的扩展先序序列为AB##CD##E##时，运行结果如图536所示； 当二叉树如图535所示，输入的扩展先序序列为ABD##E##CF##G##时，运行结果如图537所示。




图536判断二叉树结构性对称

运行结果1





图537判断二叉树结构性对称

运行结果2



5.5.8判断二叉树是否对称
判断二叉树是否关于中轴线对称指的是在考虑结点值的情况下，二叉树的任意一个非空结点，如果结点存在左、右孩子，则左、右孩子的值相同。并且左、右子树也都是关于中轴线对称的。判断二叉树是否对称的算法与判断二叉树是否结构性对称的算法非常类似，区别之处在于结构性对称不需要考虑结点的值，而对称需要考虑结点的值。例如，图538所示的二叉树不是对称的，因为结点A的左、右子树不对称。图539所示的二叉树是对称的。




图538不对称的二叉树





图539对称的二叉树



判断一棵非空二叉树的左右子树是否对称的算法描述如下。

template <class ElemType>

int BiTree<ElemType>::IsCheck(BiNode<ElemType> *lchild, BiNode<ElemType> *rchild) 

{

if(lchild == NULL && rchild == NULL)

return 1;

if(lchild == NULL || rchild == NULL)

return 0;

/*此处与判断结构性对称不同*/ 

if(lchild->data != rchild->data)

return 0;

return IsCheck(lchild->lchild,rchild->rchild) && IsCheck(lchild->rchild,rchild->lchild);

}

判断一棵二叉树是否对称的算法描述如下。

template <class ElemType>

int BiTree<ElemType>::IsSymmetric(BiNode<ElemType> *bt) {

if(bt == NULL)

return 1;

return IsCheck(bt->lchild, bt->rchild);

}

详细代码可参照ch05＼ JudgeSymmetric目录下的文件，当二叉树如图538所示，扩展的先序遍历序列为ABD##D##B##时，运行结果如图540所示。当二叉树如图539所示，扩展的先序遍历序列为AB##B##时，运行结果如图541所示。




图540判断二叉树对称性的运行结果1





图541判断二叉树对称性的运行结果2



5.5.9求二叉树第k层的结点个数和叶子结点个数
求二叉树的第k层的结点个数可以采用递归的方法。
假设指向根结点的指针为bt，算法描述如下。

1. 如果bt为空，或者层数k<1，则为空二叉树或者参数不合要求，返回0； 

2. 如果bt不为空，并且此时层数k=1，则返回1； 

3. 如果bt不为空，并且此时层数k > 1，则返回bt左子树第k-1层的结点数和bt右子树第k-1层结点数的和； 



使用C++语言描述算法如下。

template <class ElemType>

int BiTree<ElemType>::GetNodesNumberOfKthLevel(BiNode<ElemType> *bt, int k) {

if(bt == NULL || k < 1)

return 0;

if(k == 1)

return 1;

return GetNodesNumberOfKthLevel(bt->lchild, k - 1) + GetNodesNumberOfKthLevel(bt->rchild, k - 1);

}

类似地，求二叉树的第k层的叶子结点个数也可以采用递归的方法。
假设指向根结点的指针为bt，算法描述如下。

1. 如果bt为空，或者层数k<1，则为空二叉树或者参数不合要求，返回0； 

2. 如果bt不为空，并且此时层数k =1，则需要判断bt是否为叶子结点： 

2.1如果bt的左右子树均为空，则返回1； 

2.2如果bt的左右子树之一不为空，则返回0； 

3. 如果bt不为空，并且此时层数k > 1，则返回bt左子树第k-1层的叶子结点数和bt右子树第k-1层叶子结点数的和； 



使用C++语言描述算法如下。

template <class ElemType>

int BiTree<ElemType>::GetLeafNodesNumberOfKthLevel(BiNode<ElemType> *bt, int k) {

if(bt == NULL || k < 1)

return 0;

if(bt != NULL) {

/*判断bt是否是叶子*/ 

if(k == 1) {

if(bt->lchild == NULL && bt->rchild == NULL)

return 1;

else 

return 0;

}

/*递归求左、右子树中的叶子数的和*/

if(k > 1) {

return GetLeafNodesNumberOfKthLevel(bt->lchild, k - 1) + 

GetLeafNodesNumberOfKthLevel(bt->rchild, k - 1);




图542求二叉树第k层结点个数和

叶子结点个数的运行结果


}

}

}

求二叉树第k层结点数以及叶子结点数的详细代码可参照ch05＼ GetNodesNumberOfKthLevel目录下的文件，当二叉树如图513所示，扩展的先序序列为ABD#G##E##C#F##，k=3时，运行结果如图542所示。
5.5.10打印二叉树第k层的结点和叶子结点
打印二叉树第k层的结点和叶子结点与求二叉树第k层的结点个数和叶子结点个数类似。假设指向根结点的指针为bt，打印第k层的结点的算法使用伪代码描述如下。

1. 如果bt为空，或者层数k<1，则为空二叉树或者参数不合要求，空操作返回； 

2. 如果bt不为空，并且此时层数k=1，则输出bt的数据域； 

3. 如果bt不为空，并且此时层数k > 1，则： 

3.1打印bt左子树第k-1层的结点； 

3.2打印bt右子树第k-1层的结点； 



使用C++语言描述算法如下。

template <class ElemType>

void BiTree<ElemType>::PrintNodesOfKthLevel(BiNode<ElemType> *bt, int k) {

if(bt == NULL || k < 1)

return;

if(k == 1)

cout<<bt->data<<" ";

PrintNodesOfKthLevel(bt->lchild, k-1);

PrintNodesOfKthLevel(bt->rchild, k-1);

}

打印第k层的叶子结点的算法使用伪代码描述如下。

1. 如果bt为空，或者层数k<1，则为空二叉树或者参数不合要求，空操作返回； 

2. 如果bt不为空，并且此时层数k=1，则判断bt是否为叶子结点： 

2.1如果bt的左右子树均为空，则输出bt的数据域； 

3. 如果bt不为空，并且此时层数k > 1，则： 

3.1打印bt左子树第k-1层的叶子结点； 

3.2打印bt右子树第k-1层的叶子结点； 



使用C++语言描述算法如下。

template <class ElemType>

void BiTree<ElemType>::PrintLeafNodesOfKthLevel(BiNode<ElemType> *bt, int k) {

if(bt == NULL || k < 1)

return;

if(bt != NULL) {

/*判断bt是否是叶子*/ 

if(k == 1) {

if(bt->lchild == NULL && bt->rchild == NULL)

cout<<bt->data<<" ";

}		

else if(k > 1) {

/*递归打印左子树第k-1层的叶子结点*/

PrintLeafNodesOfKthLevel(bt->lchild, k - 1); 

/*递归打印右子树第k-1层的叶子结点*/

PrintLeafNodesOfKthLevel(bt->rchild, k - 1); 




图543打印二叉树第k层结点个数和

叶子结点个数的运行结果


}

}

}

打印二叉树第k层结点以及叶子结点的详细代码可参照ch05＼PrintLeafNodesOfKthLevel目录下的文件，当二叉树如图513所示，扩展的先序序列为ABD#G##E##C#F##，k=3时，运行结果如图543所示。
5.5.11求二叉树最大的结点距离
如果把二叉树看成图，父子结点之间的连线看作是双向的，则两个结点之间的距离定义为两个结点之间的边的条数。二叉树中结点之间的最大距离也称为二叉树的最长路径。图544所示的二叉树结点H和I的距离为6，此距离是二叉树结点的最大的距离，也是二叉树中最长路径的长度。
在图545中，二叉树的最远的两个结点D和C之间的距离是3。在图546中，二叉树的最远的两个结点E和H之间的距离是5。不同之处在于图545中，二叉树的最长路径经过根结点，而图546中的二叉树的最长路径不经过根结点。




图544二叉树中相距最远的

两个结点A和B





图545最长路径经过

根结点





图546二叉树的最长路径不

结过根结点的情况



从以上例子中可以看出，相距最远的两个结点，或者是两个叶子结点，或者是一个叶子结点到根结点。如果最长路径经过根结点，则距离最远的结点都是左、右子树中距离根结点最远的叶子结点，如图544和图545所示。如果路径不经过根结点，则肯定是根的左子树中的最大的结点距离或者是根的右子树的最大的结点距离，如图546所示，结点E和结点H之间的路径不经过根结点，同时也是根结点右子树中最大的结点距离。
可以采用递归的方法求解二叉树中最大的结点距离。由于需要记录任意一个非空结点的左子树和右子树的最大结点距离，因此将二叉链表存储的结点信息再扩充两个信息域，即maxLeft和maxRight，其中maxLeft表示左子树的最大结点距离，maxRight表示右子树的最大结点距离。扩展以后的二叉链表结点结构描述如下。

template <class ElemType>

struct BiNode{

ElemType data; 

BiNode<ElemType> *lchild, *rchild;

int maxLeft; /*左子树最大的结点距离*/

int maxRight; /*右子树最大的结点距离*/

};

求二叉树结点的最大距离的算法描述如下。

/*全局变量，记录二叉树的最大的结点距离*/ 

int maxLen = 0;

template <class ElemType>

void BiTree<ElemType>::GetMaxPathLength(BiNode<ElemType> *bt) {

/*二叉树为空，空操作返回*/

if(bt == NULL) {

return;

}

/*二叉树左子树为空，则左子树的最大结点距离为0*/

if(bt->lchild == NULL) {

bt->maxLeft = 0;

} 

/*二叉树右子树为空，则右子树的最大结点距离为0*/ 

if(bt->rchild == NULL) {

bt->maxRight = 0;

}

/*如果左子树不为空，则递归寻找左子树的最大结点距离*/

if(bt->lchild != NULL) {

GetMaxPathLength(bt->lchild);

}

/*如果右子树不为空，则递归寻找右子树的最大结点距离*/

if(bt->rchild != NULL) {

GetMaxPathLength(bt->rchild);

}

/*计算左子树最大结点距离*/

if(bt->lchild != NULL) {

int temp = 0;

int ll = bt->lchild->maxLeft;

int lr = bt->lchild->maxRight;

temp = ll > lr ? ll : lr;

bt->maxLeft = temp + 1;

} 

/*计算右子树最大结点距离*/ 

if(bt->rchild != NULL) {

int temp = 0;

int rl = bt->rchild->maxLeft;

int rr = bt->rchild->maxRight;

temp = rl > rr ? rl : rr;

bt->maxRight = temp + 1;

} 

/*更新最大结点距离*/

if(bt->maxLeft + bt->maxRight > maxLen) {

maxLen = bt->maxLeft + bt->maxRight;

}

}




图547求二叉树最大结点距离的

运行结果1

详细代码可参照ch05＼GetMaxPathLength目录下的文件，当输入的扩展的二叉树的前序序列为ABDH###E##CF#I##G##时，对应的二叉树如图544所示，运行结果如图547所示。
当输入的扩展的二叉树的前序序列为ABD###C##时，对应的二叉树如图545所示，运行结果如图548所示。
当输入的扩展的二叉树的前序序列为A#BCE###DF#H##G##时，对应的二叉树如图546所示，运行结果如图549所示。




图548求二叉树最大结点距离的运行结果2





图549求二叉树最大结点距离的运行结果3



5.5.12由前序序列和中序序列构造二叉树
任何一棵非空二叉树的某种遍历序列都是唯一的，那么反过来呢？二叉树的一种普通的遍历序列可以唯一地确定二叉树吗？显然不能。由前文的内容可知，扩展的前序序列可以唯一地确定二叉树，但是普通的前序遍历序列不能唯一地确定二叉树。同理，普通的中序遍历序列、后序遍历序列、层序遍历序列都不能唯一地确定二叉树。



图550两棵二叉树

那么两种序列可以唯一地确定二叉树吗？例如前序序列为A B C，后序序列为C B A时，如图550所示的两棵二叉树都满足以上条件，因此由二叉树的前序序列和后序序列也不能唯一地确定二叉树。
由二叉树的前序序列和中序序列可以唯一地确定二叉树，方法如下。
（1） 前序序列的第一个结点为根； 
（2） 在中序序列中找到根的位置，根把中序序列分为左、右两个部分，根之前的序列为左子树的中序序列，根之后的序列为右子树的中序序列； 
（3） 在前序序列中寻找左子树的前序序列以及右子树的前序序列； 
（4） 由左子树的前序序列和中序序列确定左子树； 
（5） 由右子树的前序序列和中序序列确定右子树。
例54二叉树的前序序列为A B D C E F，中序序列为D B A E C F，确定二叉树。
前序序列的第一个结点为A，即为二叉树的根。中序序列中A之前的D B为左子树的中序序列，A之后的E C F为右子树的中序序列。前序序列中B D为左子树的前序序列，C E F为右子树的前序序列。



图551一棵二叉树

示意图


使用左子树的前序序列（B D）和中序序列（D B）确定左子树，使用右子树的前序序列（C E F）和中序序列（E C F）确定右子树。最后确定的二叉树的结构如图551所示。
利用前序序列和中序序列构造二叉树的算法使用C++语言描述如下。

template <class ElemType>

BiNode<ElemType>* BiTree<ElemType>::Rebuild(ElemType *preOrder, ElemType *inOrder, int n) {

if(n == 0) 

return NULL;

/*获得前序遍历的第一个结点*/ 

ElemType c = preOrder［0］;

/*创建根结点*/

BiNode<ElemType> *node = new BiNode<ElemType>;

node->data = c;

node->lchild = NULL;

node->rchild = NULL;

int i;

/*在中序遍历序列中寻找根结点的位置*/

for(i = 0; i < n && inOrder［i］ != c; i++)

;

/*左子树结点个数*/ 

int lenLeft = i;

/*右子树结点个数*/

int lenRight = n - i - 1;

/*左子树不为空，递归重建左子树*/ 

if(lenLeft > 0)

node->lchild = Rebuild(&preOrder［1］, &inOrder［0］, lenLeft);

/*右子树不为空，递归重建右子树*/

if(lenRight > 0)

node->rchild = Rebuild(&preOrder［lenLeft+1］, &inOrder［lenLeft+1］, lenRight);




图552利用前序序列和中序序列重建

二叉树的运行结果


return node;

}


详细代码可参照ch05＼ RebuildBiTreeFromPreIn目录下的文件，当遍历序列如例53所示时，重建的二叉树如图551所示。为了验证结果，对二叉树进行了各种遍历，运行结果如图552所示。
5.5.13由后序序列和中序序列构造二叉树
利用二叉树的后序序列和中序序列也可以唯一地确定二叉树，方法与利用前序序列和中序序列确定二叉树类似。二叉树的后序序列的最后一个结点为根结点。使用C++语言描述算法如下。

template <class ElemType>

BiNode<ElemType>* BiTree<ElemType>::Rebuild(ElemType *postOrder, ElemType *inOrder, int n) {

if(n == 0) 

return NULL;

/*获得后序遍历的最后一个结点*/ 

ElemType c = postOrder［n-1］;

/*创建根结点*/

BiNode<ElemType> *node = new BiNode<ElemType>;

node->data = c;

node->lchild = NULL;

node->rchild = NULL;

int i;

/*在中序遍历序列中寻找根结点的位置*/

for(i = 0; i < n && inOrder［i］ != c; i++)

;

/*左子树结点个数*/ 

int lenLeft = i;

/*右子树结点个数*/

int lenRight = n - i - 1;

/*左子树不为空，重建左子树*/ 

if(lenLeft > 0)

node->lchild = Rebuild(&postOrder［0］, &inOrder［0］, lenLeft);

/*右子树不为空，重建右子树*/

if(lenRight > 0)

node->rchild = Rebuild(&postOrder［lenLeft］, &inOrder［lenLeft+1］, lenRight);




图553利用后序序列和中序序列重建

二叉树的运行结果


return node;

}

详细代码可参照ch05＼ RebuildBiTreeFromPostIn目录下的文件，当遍历序列如例53所示时，重建的二叉树如图551所示。为了验证结果，对二叉树进行了遍历，运行结果如图553所示。
5.5.14求二叉树的镜像
将一棵二叉树的所有结点的左、右子树调换位置，就成了二叉树的镜像。图554所示的两棵二叉树互为镜像。
可以利用递归的方法求二叉树的镜像，使用C++语言描述算法如下。

void BiTree<ElemType>::GetMirror(BiNode<ElemType> *bt) {

/*二叉树为空，空操作返回*/

if(bt == NULL)

return;

/*二叉树的左、右子树都为空，空操作返回*/

if(bt->lchild == NULL && bt->rchild == NULL)

return;

/*交换左、右子树*/

BiNode<ElemType> *tmp;

tmp = bt->lchild;

bt->lchild = bt->rchild;

bt->rchild = tmp;

/*递归处理左子树*/

GetMirror(bt->lchild);

/*递归处理右子树*/

GetMirror(bt->rchild); 

}

求二叉树镜像的详细代码可参照ch05＼GetBiTreeMirror目录下的文件，当原二叉树如图554(a)所示，其对应的扩展的先序遍历序列为AB#D##C##时，运行结果如图555所示。




图554互为镜像的二叉树





图555求二叉树镜像的运行结果



5.5.15判断两棵二叉树是否等价
如果两棵二叉树结构相同并且相同位置上的结点的数据域也分别相同，则称两棵二叉树等价。图556所示的两棵二叉树为等价二叉树，图557所示的二叉树不是等价二叉树。




图556等价的两棵二叉树





图557不等价的两棵二叉树



判断两棵二叉树是否等价的算法使用伪代码描述如下。

1. 如果两棵二叉树都为空，则返回true； 

2. 如果两棵二叉树一棵为空，另一棵非空，则返回false； 

3. 如果两棵二叉树都不为空，但根结点的数据域不相等，则返回false； 

4. 否则，递归判断两棵二叉树的左右子树是否等价。



使用C++语言描述算法如下。

template <class ElemType> 

int IsEqualBiTrees(BiNode<ElemType> *T1, BiNode<ElemType> *T2) {

/*两棵二叉树都为空，返回1 */

if(T1 == NULL && T2 == NULL)

return 1;

/*两棵二叉树一棵为空，一棵不为空，返回0 */

if(T1 == NULL || T2 == NULL)

return 0;

/*两棵二叉树都不为空，并且根结点数据域不相等，返回0 */

if(T1->data != T2->data)

return 0;

/*递归判断左子树和右子树是否等价*/ 

return IsEqualBiTrees(T1->lchild, T2->lchild) && IsEqualBiTrees(T1->rchild, T2->rchild); 

}

详细代码可参照ch05＼JudgeEqualBiTrees目录下的文件，当两棵二叉树如图556所示时，运行结果如图558所示。当两棵二叉树如图557所示时，运行结果如图559所示。




图558判断两棵二叉树是否等价的

运行结果1





图559判断两棵二叉树是否等价的

运行结果2








5.6树、森林与二叉树的转换
树的孩子兄弟表示法和二叉树的二叉链表表示法类似，即树的孩子兄弟表示法和二叉树的二叉链表表示法在物理结构上是相同的。如图560所示，图560(a)中树的存储结构（见图560(b)）和图560（c）中二叉树的存储结构（见图560(d)）在内存中对应同一种状态。即给定一棵树，存在一棵唯一的二叉树与之对应。



图560树与二叉树的对应关系


1. 树转换成二叉树
将一棵树转换成二叉的方法为： 
（1） 加线： 树中所有相邻的兄弟结点之间加一条连线； 
（2） 去线： 只保留双亲结点和第一个孩子之间的连线，删去它去其他孩子之间的连线； 
（3） 调整： 以根结点为轴心，将水平方向的连线顺时针旋转一定的角度，使之层次分明。
例如，图561给出了一棵树转换成二叉树的过程。



图561树转换成二叉树的过程

由树转换而来的二叉树，其根结点的右子树一定为空。因为二叉树的结点的右孩子在树中对应着其右兄弟，而树中根结点无右兄弟，因此二叉树的根结点的右子树一定为空。
根据树与二叉树的转换以及树和二叉树的遍历可知： 
树的前序遍历等价于二叉树的前序遍历； 
树的后序遍历等价于二叉树的中序遍历。
2. 森林转换成二叉树
森林转换成二叉树的方法为： 
（1） 将森林中的每一棵树分别转换成二叉树； 
（2） 将二叉树的根结点之间连线； 
（3） 以根结点为轴心，将水平方向的连线顺时针旋转一定的角度，使之层次分明。
例如，图562给出了森林转换成二叉树的过程。



图562森林转化成二叉树的过程


3. 二叉树转换成森林或树
二叉树也可以转换成森林或树。如果二叉树的根结点无右子树，则二叉树转换成树。如果二叉树的根结点有右子树，则二叉树转换成森林。转换方法为： 
（1） 加线： 若结点x是其双亲结点y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点x用线相连； 
（2） 去线： 删除原二叉树中所有双亲结点与其右孩子的连线； 
（3） 调整： 调整使树或森林层次分明。
例如，图563为二叉树转换成森林的过程。



图563二叉树转换成森林的过程


4. 森林的遍历
森林的遍历包括前序遍历和后序遍历。
前序遍历森林为前序遍历森林中的每一棵树，例如对图563(d)所示的森林进行前序遍历，前序序列为A B C D E F G H I。

后序遍历森林为后序遍历森林中的每一棵树，例如对图563(d)所示的森林进行后序遍历，后序序列为B A D E C G H I F。
5.7小结
 树状结构是应用非常广泛的非线性结构。其中，二叉树是最常用的树状结构。二叉树最常用的操作是各种遍历，包括前序遍历、中序遍历、后序遍历、层序遍历。
 可以使用递归的算法或者非递归的算法进行遍历。除此之外，还可以在遍历的基础上进行例如求结点个数、求叶子结点个数、求二叉树的深度等操作。
 为了充分地利用二叉链表中的空指针，可以将二叉链表进行线索化。可以方便地实现遍历中序线索二叉树。
 判断各种特殊的二叉树也是一类重要的操作，例如完全二叉树的判断、满二叉树的判断等。
 构造赫夫曼树是二叉树的重要应用。
 可以根据二叉树前序遍历序列和中序遍历序列构造二叉树，也可以根据后序遍历序列和中序遍历序列构造二叉树。
 一些扩展的操作也比较常见，例如求二叉树的最小深度、求二叉树的最大结点距离、求二叉树第k层的结点和叶子结点、判断两棵二叉树是否等价等操作。
习题
1. 选择题
（1） 假设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中的叶子结点的个数为（）。

A. 5B. 6C. 7D. 8
（2） 若一棵二叉树中具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（）。
A. 9B. 11C. 15D. 无法确定
（3） 已知一棵二叉树的前序遍历序列为A B C D E F，中序遍历序列为C B A E D F，则后序遍历序列为（）。
A. C B E F D AB. F E D C B A
C. C B E D F AD. 没有正确答案
（4） 二叉树的前序序列和后序列序列正好相反，则该二叉树一定是（）的二叉树。
A. 空或只有一个结点B. 深度等于其结点数
C. 任一结点无左孩子D. 任一结点无右孩子
（5） 深度为h的满m叉树的第k层有（）个结点。
A. mk-1B. mk-1C. mh-1D. mh-1
（6） 深度为k的完全二叉树最多有（）个结点。
A. 2k-2+1B. 2k-1C. 2k-1D. 2k-1-1
（7） 在二叉树的先序遍历序列、中序遍历序列和后序遍历序列中，所有叶子结点的相对顺序（）。
A. 都不相同B. 完全相同 
C. 先序和中序相同，而与后序不同D. 中序和后序相同，而与先序不同
（8） 设给定权值的总数有n个，其赫夫曼树的结点总数为（）。
A. 不确定B. 2nC. 2n+1D. 2n-1
（9） 一棵具有124个叶子结点的完全二叉树，最多有（）个结点。
A. 247B. 248C. 249D. 250
（10） 一个具有1025个结点的二叉树的深度为（）。

A. 11B. 10C. 11~1025D. 10~1024
（11） 一棵二叉树的深度为h，所有结点的度为0或2，则这棵二叉树至少有（）个结点。
A. 2hB. 2h-1C. 2h+1D. h+1
（12） 下列存储形式中，（）不是树的存储结构。
A. 双亲表示法B. 孩子链表表示法
C. 孩子兄弟表示法D. 顺序存储表示法
（13） 引入线索二叉树的目的是（）。
A. 加快查找结点的前驱或后继的速度
B. 能在二叉树中方便地进行插入或删除
C. 方便地找到双亲
D. 使二叉树的遍历结果唯一
（14） 一棵赫夫曼树共有215个结点，对其进行赫夫曼编码，共能得到（）个不同的码字。
A. 107B. 108C. 214D. 215
（15） 以下编码中，（）不是前缀编码。
A. 00,01,10,11B. 0,1,00,11
C. 0,10,110,111D. 1,01,000,001
（16） 为5个使用频率不等的字符设计赫夫曼编码，不可能的方案是（）。
A. 000,001,010,011,1B. 0000,0001,001,01,1
C. 000,001,01,10,11D. 00,100,101,110,111
2. 填空题
（1） 具有n个结点的二叉树，采用二叉链表存储时共有（）个空指针。
（2） 利用树的孩子兄弟表示法，可以将树转换成（）。
（3） 具有n个结点的满二叉树，其叶子结点个数为（）。
（4） 具有n个结点的完全二叉树的深度为（）。
（5） 深度为k的二叉树中，所含叶子的个数最多为（）。
（6） 结点数为101的完全二叉树中，叶子结点的个数为（）。
（7） 设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B，已知T1、T2、T3的结点数分别为n1、n2和n3，则二叉树B的右子树中有（）个结点。
（8） 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（）个叶子结点。
（9） 在二叉链表中，指针p所指的结点为叶子的条件是（）。
（10） 已知一棵二叉树的后序序列是F E G H D C B，中序序列是F E B G C H D，则它的前序序列是（）。
（11） 树的先序遍历等价于二叉树的（）遍历，树的后序遍历等价于二叉树的（）遍历。
3. 判断题
（1） 二叉树的遍历实际上是将非线性结构线性化的过程。（）
（2） 完全二叉树一定存在度为1的结点。（）
（3） 二叉树是树的特例。（）
（4） 完全二叉树中的结点若没有左孩子，则它必为叶子。（）
（5） 二叉树是度为2的树。（）
（6） 线索二叉树中不存在空指针。（）
（7） 可以根据前序遍历序列和后序遍历序列唯一地确定二叉树。（）
（8） 树状结构中的数据元素之间存在一对多的逻辑关系。（）
（9） 树和二叉树是两种不同的树状结构。（）
（10） 顺序存储结构只适合于存储完全二叉树。（）
4. 问答题
（1） 已知一棵满m叉树，设根在第1层，并从1开始自上向下分层给各个结点编号，试回答以下问题。
① 第i层有多少结点？
② 深度为h的满m叉树有多少个结点？
③ 编号为k的结点的双亲结点的编号是多少？
④ 编号为k的结点的第1个孩子的结点编号是多少？
⑤ 编号为k的结点在第几层？
（2） 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，求树中共有多少个叶子结点？
（3） 已知一棵二叉树的前序遍历序列为A B E C D F G H I J，中序遍历序列为E B C D A F H I G J，画出这棵二叉树并写出它的后序遍历序列。
（4） 已知某系统在通信联络中只可能出现8种字符： a、b、c、d、e、f、g、h，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试构造赫夫曼树并求其WPL，并完成8种字符的赫夫曼编码。
（5） 给定权值{8,12,4,5,26,16,9}，构造赫夫曼树，并计算其带权路径长度。
5. 算法设计题
（1） 设计算法求以root为根指针的二叉树的最大元素的值。
（2） 假设二叉树采用二叉链表存储，结点类型为char，'#'为无效字符，设计算法求前序遍历的第k个结点的值。
（3） 假设二叉树采用二叉链表存储，设计算法求指定结点p的双亲结点。