前言

部分内容摘自程杰的《大话数据结构》

1. 二叉树简介

1.1 二叉树的定义

现在我们来做个游戏，我在纸上已经写好了一个 100 以内的正整数数字，请大家想办法猜出我写的是哪一个？注意你们猜的数字不能超过 7 个，我的回答只会告诉你是 “大了” 或 “小了”。
这个游戏在一些电视节目中，猜测一些商品的定价时常会使用。我看到过有些人是一点一点的数字累加的，比如 5、10、 15、 20 这样猜，这样的猜数策略太低级了，显然是没有学过数据结构和算法的人才做得出的事。
其实这是一个很经典的折半查找算法。如果我们用下图（下三层省略）的办法，就一定能在 7 次以内，猜出结果来。

由于是 100 以内的正整数，所以我们先猜 50（100 的一半），被告之 “大了”，于是再猜 25（50的一半），被告之 “小了”，再猜 37（25 与 50 的中间数），小了，于是猜 43，大了，40，大了，38，小了，39，完全正确。过程如下表所示。

被猜数字	第一次	第二次	第三次	第四次	第五次	第六次	第七次
39	50	25	37	43	40	38	39
82	50	75	88	82	-	-	-
99	50	75	88	96	98	99	-
1	50	25	12	6	3	2	1

我们发现，如果用这种方式进行查找，效率高得不是一点点。对于折半查找的详细讲解，我们后面再说。不过对于这种在某个阶段都是两种结果的情形，比如开和关、0 和 1、真和假、上和下、对与错，正面与反面等，都适合用树状结构来建模，而这种树是一种很特殊的树状结构，叫做二叉树。

二叉树（Binary Tree）是n(n≥0)个结点的有限集合，该集合或者为空集（称为空二叉树）或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

下图就是一棵二叉树。

1.2 二叉树的特点

二叉树的特点有：

每个结点最多有两棵子树，所以二叉树中不存在度大于 2 的结点。注意不是只有两棵子树，而是最多有。没有子树或者有一棵子树都是可以的。
左子树和右子树是有顺序的，次序不能任意颠倒。就像人是双手、双脚，但显然左手、左脚和右手、右脚是不一样的，右手戴左手套、右脚穿左鞋都会极其别扭和难受。
即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。下图
中，树 1 和树 2 是同一棵树，但它们却是不同的二叉树。就好像你一不小
心，摔伤了手，伤的是左手还是右手，对你的生活影响度是完全不同的。

二叉树具有五种基本形态：

空二叉树。
只有一个根结点。
根结点只有左子树。
根结点只有右子树。
根结点既有左子树又有右子树。

应该说这五种形态还是比较好理解的，那我现在问大家，如果是有三个结点的树，有几种形态？如果是有三个结点的二叉树，考虑一下，又有几种形态？
若只从形态上考虑，三个结点的树只有两种情况，那就是下图中有两层的树 1 和有三层的后四种的任意一种，但对于二叉树来说，由于要区分左右，所以就演变成五种形态，树 2、树 3、树 4 和树 5 分别代表不同的二叉树。

1.2 特殊二叉树

我们再来介绍一些特殊的二叉树。这些树可能暂时你不能理解它有什么用处，但先了解一下，以后会提到它们的实际用途。
1. 斜树
顾名思义，斜树一定要是斜的，但是往哪斜还是有讲究。所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。上图中的树 2 就是左斜树，树 5 就是右斜树。斜树有很明显的特点，就是每一层都只有一个结点，结点的个数与二叉树的深度相同。
有人会想，这也能叫树呀，与我们的线性表结构不是一样吗。对的，其实线性表结构就可以理解为是树的-种极其特殊的表现形式。
2. 满二叉树
苏东坡曾有词云：“人有悲欢离合，月有阴晴圆缺，此事古难全”。意思就是完美是理想，不完美才是人生。我们通常举的例子也都是左高右低、参差不齐的二叉树。那是否存在完美的二叉树呢？
完美的二叉树是存在的。
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
下图就是一棵满二叉树，从样子上看就感觉它很完美。

单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有的叶子都在同一层上，这就做到了整棵树的平衡。因此，满二叉树的特点有：
(1) 叶子只能出现在最下一层。出现在其他层就不可能达成平衡。
(2) 非叶子结点的度一定是2。否则就是 “缺胳膊少腿” 了。
(3) 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
3. 完全二叉树
对一棵具有n个结点的二叉树按层序编号，如果编号为 i（1≤i≤n）的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树，如下图所示。

这是一种有些理解难度的特殊二叉树。
首先从字面上要区分，“完全” 和 “满” 的差异，满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。
其次，完全二叉树的所有结点与同样深度的满二叉树，它们按层序编号相同的结点，是一一对应的。这里有个关键词是按层序编号，像下图中的树 1，因为 5 结点没有左子树，却有右子树，那就使得按层序编号的第 10 个编号空档了，它不是完全二叉树。同样道理，下图中的树 2，由于 3 结点没有子树，所以使得 6、7 编号的位置空档了，它也不是完全二叉树。下图中的树 3 又是因为 5 编号下没有子树造成第 10 和第 11 位置空档，同样不是完全二叉树。只有上图中的树，尽管它不是满二叉树，但是编号是连续的，所以它是完全二叉树。

从这里我们也可以得出一些完全二叉树的特点：
(1) 叶子结点只能出现在最下两层。
(2) 最下层的叶子一定集中在左部连续位置。
(3) 倒数二层，若有叶子结点，一定都在右部连续位置。
(4) 如果结点度为 1，则该结点只有左孩子，即不存在只有右子树的情况。
(5) 同样结点数的二叉树，完全二叉树的深度最小。
从上面的例子，也给了我们一个判断某二叉树是否是完全二叉树的办法，那就是看着树的示意图，心中默默给每个结点按照满二叉树的结构逐层顺序编号，如果编号出现空档，就说明不是完全二叉树，否则就是。

2. 二叉树的性质

二叉树有一些需要理解并记住的特性，以便于我们更好地使用它。

2.1 二叉树的性质1

性质1：在二叉树的第 i 层上至多有 2 ${^i}{^-}{^1}$ 个结点（i≥1）。
这个性质很好记忆，观察一下满二叉树。

第一层是根结点，只有一个，所以 2 ${^1}{^-}{^1}$ =2^0^=1。
第二层有两个，2 ${^2}{^-}{^1}$ =2^1^=2。
第三层有四个，2 ${^3}{^-}{^1}$ =2^2^=4。
第四层有八个，2 ${^4}{^-}{^1}$ =2^3^=8。
通过数据归纳法的论证，可以很容易得出在二叉树的第i层上至多有 2 ${^i}{^-}{^1}$ 个结点（i≥1）的结论。

2.2 二叉树的性质2

性质2：深度为k的二叉树至多有 2 ${^k}{^-}{^1}$ 个结点(k≥1)。
注意这里一定要看清楚，是2k后再减去 1，而不是 2 ${^k}{^-}{^1}$ 。以前很多人不能完全理解，这样去记忆，就容易把性质2与性质1给弄混淆了。
深度为k意思就是有k层的二叉树，我们先来看看简单的。
如果有一层，至多1=2^1^-1个结点。
如果有二层，至多1+2=3=2^2^-1个结点。
如果有三层，至多1+2+4=7=2^3^-1个结点。
如果有四层，至多1+2+4+8=15=2^4^-1个结点。
通过数据归纳法的论证，可以得出，如果有k层，此二叉树至多有 2 ${^k}{^-}{^1}$ 个结点。

2.3 二叉树的性质3

性质3：对任何-棵二叉树T,如果其终端结点数为Do,度为2的结点数为n2,则no=n2+1。
终端结点数其实就是叶子结点数，而一棵二叉树，除了叶子结点外，剩下的就是度为 1 或 2 的结点数了，我们设 n $_1$ 为度是 1 的结点数。则树T结点总数 n=n $_0$ +n $_1$ +n $_2$ 。
比如下图的例子，结点总数为 10，它是由 A、B、C、D 等度为 2 结点，F、G、H、I、J 等度为 0 的叶子结点和 E 这个度为 1 的结点组成。总和为 4+1+5=10。

我们换个角度，再数一数它的连接线数，由于根结点只有分支出去，没有分支进入，所以分支线总数为结点总数减去 1。上图就是 9 个分支。对于 A、B、C、D 结点来说，它们都有两个分支线出去，而 E 结点只有一个分支线出去。所以总分支线为 4×2+1×1=9。
用代数表达就是分支线总数=n-1=n $_1$ + 2n $_2$ 。因为刚才我们有等式 n=n $_0$ +n $_1$ +n $_2$ ，所以可推导出 n $_0$ +n $_1$ +n $_2$ =n $_1$ +2n $_2$ 。结论就是 n $_0$ =n $_2$ + 1。

2.4 二叉树的性质4

性质4：具有n个结点的完全二叉树的深度为[log $_2$ n]+1（[x]表示不大于 x的最大整数）。
由满二叉树的定义我们可以知道，深度为k的满二叉树的结点数n一定是 2^k^-1。因为这是最多的结点个数。那么对于 n=2^k^-1 倒推得到满二叉树的度数为 k=log $_2$ (n+1)，比如结点数为 15 的满二叉树，深度为 4。
完全二叉树我们前面已经提到，它是一棵具有n个结点的二叉树，若按层序编号后其编号与同样深度的满二叉树中编号结点在二叉树中位置完全相同，那它就是完全二叉树。也就是说，它的叶子结点只会出现在最下面的两层。
它的结点数一定少于等于同样度数的满二叉树的结点数2^k^-1，但一定多于 2 ${^k}{^-}{^1}$ -1。即满足 2 ${^k}{^-}{^1}$ -1<n≤2^k^-1。由于结点数n是整数，n≤2^k^-1 意味着 n<2^k^，n>2 ${^k}{^-}{^1}$ -1，意味着 n≥2 ${^k}{^-}{^1}$ ，所以 2 ${^k}{^-}{^1}$ ≤n<2^k^，不等式两边取对数，得到k-1≤log $_2$ n<k，而k作为深度也是整数，因此 k=[log $_2$ n]+1。

2.5 二叉树的性质5

性质5：如果对一棵有n个结点的完全二叉树（其深度为[log $_2$ n]+1）的结点按层序编号（从第1层到第[log $_2$ n]+1层，每层从左到右），对任-结点 i (1<i≤n)有：

如果i=1，则结点 i 是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]。
如果2i>n，则结点 i 无左孩子（结点i为叶子结点）；否则其左孩子是结点 2i。
如果2i+1>n，则结点 i 无右孩子；否则其右孩子是结点 2i+1。

我们以下图为例，来理解这个性质。这是一个完全二叉树，度为 4，结点总数是 10。

对于第一条来说是很显然的，i=1时就是根结点。i>1时，比如结点 7，它的双亲就是 [7/2]=3，结点 9，它的双亲就是 [9/2]=4。
第二条，比如结点 6，因为 2×6=12 超过了结点总数 10，所以结点 6 无左孩子，它是叶子结点。同样，而结点 5，因为 2×5=10 正好是结点总数 10，所以它的左孩子是结点 10。
第三条，比如结点 5，因为 2×5+1=11，大于结点总数 10，所以它无右孩子。而结点 3，因为 2×3+1=7 小于 10，所以它的右孩子是结点 7。

3. 二叉树的存储结构

3.1 二叉树顺序存储结构

前面我们已经谈到了树的存储结构，并且谈到顺序存储对树这种一对多的关系结构实现起来是比较困难的。但是二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构也可以实现。
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。
先来看看完全二叉树的顺序存储，-一完全二叉树如下图所示。

将这棵二叉树存入到数组中，相应的下标对应其同样的位置，如下图所示。

这下看出完全二叉树的优越性来了吧。由于它定义的严格，所以用顺序结构也可以表现出二叉树的结构来。
当然对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是可以将其按完全二叉树编号，只不过，把不存在的结点设置为 “^” 而已。如下图，注意浅色结点表示不存在。

考虑种极端的情况，一棵深度为k的右斜树，它只有k个结点，却需要分配 2^k^-1 个存储单元空间，这显然是对存储空间的浪费，例如下图所示。所以，顺序存储结构一般只用于完全二叉树。

3.2 二叉链表

既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做叉链表。结点结构图如下表所示。

其中data是数据城，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。
以下是我们的二叉链表的结点结构定义代码。

/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode	/* 结点结构 */
{
	TElemType data;	/* 结点数据 */
	struct BiTNode *lchild,*rchild;	/* 左右孩子指针 */
}BiTNode,*BiTree;

结构示意图如下图所示。

就如同树的存储结构中讨论的一样，如果有需要，还可以再增加一个指向其双亲的指针域，那样就称之为三叉链表。由于与树的存储结构类似，这里就不详述了。

4. 遍历二叉树

4.1 二叉树的遍历原理

假设，我手头有 20 张 100 元的和 2000 张 1 元的奖券，同时洒向了空中，大家比赛看谁最终捡的最多。如果是你，你会怎么做？
相信所有同学都会说，一定先捡 100 元的。道理非常简单，因为捡一张 100 元等于 1 元的捡 100 张，效率好得不是一点点。所以可以得到这样的结论，同样是捡奖券，在有限时间内，要达到最高效率，次序非常重要。对于二叉树的遍历来讲，次序同样显得很重要。

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问次且仅被访问一次。

这里有两个关键词：访问和次序。
访问其实是要根据实际的需要来确定具体做什么，比如对每个结点进行相关计算，输出打印等，它算作是一个抽象操作。在这里我们可以简单地假定就是输出结点的数据信息。
二叉树的遍历次序不同于线性结构，最多也就是从头至尾、循环、双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系，在访向一个结点后，下一个被访问的结点面临着不同的选择。就像你人生的道路上，高考填志愿要面临哪个城市、哪所大学、具体专业等选择，由于选择方式的不同，遍历的次序就完全不同了。

4.2 二叉树的遍历方法

二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为四种：

前序遍历
规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如下图所示，遍历的顺序为：ABDGHCEIF。
中序遍历
规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。如下图所示，遍历的顺序为：GDHBAEICF。
后序遍历
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访向根结点。如下图所示，遍历的顺序为：GHDBIEFCA。
层序遍历
规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如下图所示，遍历的顺序为：ABCDEFGHI。

有同学会说，研究这么多遍历的方法干什么呢？
我们用图形的方式来表现树的结构，应该说是非常直观和容易理解，但是对于计算机来说，它只有循环、判断等方式来处理，也就是说，它只会处理线性序列，而我们刚才提到的四种遍历方法，其实都是在把树中的结点变成某种意义的线性序列，这就给程序的实现带来了好处。
另外不同的遍历提供了对结点依次处理的不同方式，可以在遍历过程中对结点进行各种处理。

4.3 前序遍历算法

二叉树的定义是用递归的方式，所以，实现遍历算法也可以采用递归，而且极其简洁明了。先来看看二叉树的前序遍历算法。代码如下：

/* 二叉树的前序遍历递归算法 */
/* 初始条件：二叉树T存在 */
/* 操作结果：前序递归遍历T */
void PreOrderTraverse(BiTree T)
{
	if(T==NULL)
		return;
	printf("%C",T->data);	/* 显示结点数据，可以更改为其他对结点操作 */
	PreOrderTraverse(T->lchild);	/* 先序遍历左子树 */
	PreOrderTraverse(T->rchild);	/* 先序遍历右子树*/
}

假设我们现在有如下图这样一棵二叉树T。这树已经用二叉链表结构存储在内存当中。

那么当调用PreOrderTraverse(T)函数时，我们来看看程序是如何运行的。

调用PreOrderTraverse(T)，T根结点不为null，所以执行printf，打印字母A，如所示。
调用PreOrderTraverse(T->lchild);访问了A结点的左孩子，不为null，执行printf显示字母B，如下图所示。
此时再次递归调用PreOrderTraverse(T->lchild);访问了B结点的左孩子，执行printf显示字母D，如下图所示。
再次递归调用PreOrderTraverse(T->lchild);访问了D结点的左孩子，执行printf显示字母H，如下图所示。
再次递归调用PreOrderTraverse(T->lchild);访问了H结点的左孩子，此时因为H结点无左孩子，所以T==null，返回此函数，此时递归调用PreOrderTraverse(T>rchild);访问了H结点的右孩子，printf显示字母K，如下图所示。
再次递归调用PreOrderTraverse(T->lchild);访向了K结点的左孩子，K结点无左孩子，返回，调用PreOrderTraverse(T->rchild);访问了K结点的右孩子，也是null，返回。于是此函数执行完毕，返回到上一级递归的函数（即打印H结点时的函数），也执行完毕，返回到打印结点D时的函数，调用PreOrderTraverse(T->rchild);访问了D结点的右孩子，不存在，返回到B结点，调用PreOrderTraverse(T->rchild);找到了结点E，打印字母E，如下图所示。
由于结点E没有左右孩子，返回打印结点B时的递归函数，递归执行完毕，返回到最初的PreOrderTraverse，调用PreOrderTraverse(T->rchid);访问结点A的右孩子，打印字母C，如下图所示。
之后类似前面的递归调用，依次继续打印 F、1、G、J，步骤略。

综上，前序遍历这棵二叉树的节点顺序是：ABDHKECFIGJ。

4.4 中序遍历算法

二叉树的中序遍历算法是如何呢？它和前序遍历算法仅仅只是代码的顺序上的差异。

/* 二叉树的中序遍历递归算法 */
/* 初始条件：二叉树T存在 */
/* 操作结果：中序递归遍历T */
void InOrderTraverse(BiTree T)
{
	if(T==NULL)
		return;
	InOrderTraverse(T->lchild);	/* 中序遍历左子树 */
	printf("%C",T->data);	/* 显示结点数据，可以更改为其他对结点操作 */
	InOrderTraverse(T->rchild);	/* 中序遍历右子树*/
}

换句话说，它等于是把调用左孩子的递归函数提前了，就这么简单。我们来看看当调用InOrderTraverse(T)函数时，程序是如何运行的。

调用InOrderTraverse (T)，T的根结点不为null，于是调用InOrderTraverse(T->lchild);访问结点B。当前指针不为null，继续调用InOrderTraverse (T->lchild);访问结点D。不为null, 继续调用InOrderTraverse(T->child);访问结点H。继续调用InOrderTraverse (T->lchild);访问结点H的左孩子，发现当前指针为null，于是返回。打印当前结点H，如下图所示。
然后调用InOrderTraverse(T->rchild);访问结点H的右孩子K，因结点K无左孩子，所以打印K，如下图所示。
因为结点K没有右孩子，所以返回。打印结点H函数执行完毕，返回。打印字母D，如下图所示。
结点D无右孩子，此函数执行完毕，返回。打印字母B，如下图所示。
调用InOrderTraverse(T->rchild);访问结点B的右孩子E，因结点E无左孩
子，所以打印E，如下图所示。
结点E无右孩子，返回。结点B的递归函数执行完毕，返回到了最初我们调用InOrderTraverse的地方，打印字母A，如下图所示。
再调用InOrderTraverse(T->rchild);访向结点A的右孩子C，再递归访问结点C的左孩子F，结点F的左孩子I。因为I无左孩子，打印I，之后分别打印 F、C、G、J。步骤省略。

综上，中序遍历这棵二叉树的节点顺序是：HKDBEAIFCGJ。

4.5 后序遍历法

那么同样的，后序遍历也就很容易想到应该如何写代码了。

/* 二叉树的后序遍历递归算法 */
/* 初始条件：二叉树T存在 */
/* 操作结果：中序递归遍历T */
void PostorderTraverse (BiTree T)
{
	if(T==NULL)
		return;
	PostorderTraverse (T->lchild);	/* 后序遍历左子树 */
	PostorderTraverse (T->rchild);	/* 后序遍历右子树*/
	printf("%C",T->data);	/* 显示结点数据，可以更改为其他对结点操作 */
}

如下图所示，后序遍历是先递归左子树，由根结点A→B→D→H，结点H无左孩子，再查看结点H的右孩子K，因为结点K无左右孩子，所以打印K，返回。

4.6 推导遍历结果

有一种题目为了考查你对二叉树遍历的掌握程度，是这样出题的。已知一棵二叉树的前序遍历序列为 ABCDEF，中序遍历序列为 CBAEDF，请问这棵二叉树的后序遍历结果是多少？
对于这样的题目，如果真的完全理解了前中后序的原理，是不难的。
三种遍历都是从根结点开始，前序遍历是先打印再递归左和右。所以前序遍历序列为 ABCDEF，第一个字母是A被打印出来，就说明A是根结点的数据。再由中序遍历序列是 CBAEDF，可以知道C和B是A的左子树的结点，E、D、F 是A的右子树的结点，如下图所示。

然后我们看前序中的C和B，它的顺序是 ABCDEF，是先打印B后打印C，所以B应该是A的左孩子，而C就只能是B的孩子，此时是左孩子还是右孩子还不确定。再看中序序列是CBAEDF，C是在B的前面打印，这就说明C是B的左孩子，否则就是右孩子了，如下图所示。

再看前序中的 E、D、F，它的顺序是 ABCDEF，那就意味着D是A结点的右孩子，E和F是D的子孙，注意，它们中有一个不一定是孩子，还有可能是孙子。再来看中序序列是 CBAEDF，由于E在D的左侧，而F在右侧，所以可以确定E是D的左孩子，F是D的右孩子。因此最终得到的二叉树如下图所示。

为了避免推导中的失误，你最好在心中递归遍历，检查一下这棵树的前序和中序遍历序列是否与题目中的相同。
已经复原了二叉树，要获得它的后序遍历结果就是易如反掌，结果是 CBEFDA。
但其实，如果同学们足够熟练，不用画这棵二叉树，也可以得到后序的结果，因为刚才判断了A结点是根结点，那么它在后序序列中，一定是最后一个。刚才推导出C是B的左孩子，而B是A的左孩子，那就意味着后序序列的前两位一定是CB。同样的办法也可以得到EFD这样的后序顺序，最终就自然的得到 CBEFDA 这样的序列，不用在草稿上画树状图了。
反过来，如果我们的题目是这样：二叉树的中序序列是 ABCDEFG，后序序列是 BDCAFGE，求前序序列。
这次简单点，由后序的 BDCAFGE，得到E是根结点，因此前序首字母是E。
于是根据中序序列分为两棵树 ABCD 和 FG，由后序序列的 BDCAFGE，知道A是E的左孩子，前序序列目前分析为EA。
再由中序序列的 ABCDEFG，知道 BCD 是A结点的右子孙，再由后序序列的 BDCAFGE 知道C结点是A结点的右孩子，前序序列目前分析得到 EAC。
中序序列 ABCDEFG，得到B是C的左孩子，D是C的右孩子，所以前序序列目前分析结果为 EACBD。
由后序序列 BDCAFGE，得到G是E的右孩子，于是F就是G的孩子。如果你是在考试时做这道题目，时间就是分数、名次、学历，那么你根本不需关心F是G的左还是右孩子，前序遍历序列的最终结果就是 EACBDGF。
不过细细分析，根据中序序列 ABCDEEG，是可以得出F是G的左孩子。
从这里我们也得到两个二叉树遍历的性质。

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

但要注意了，已知前序和后序遍历，是不能确定一棵二叉树的，原因也很简单，比如前序序列是 ABC，后序序列是 CBA。我们可以确定A一定是根结点，但接下来，我们无法知道，哪个结点是左子树，哪个是右子树。这棵树可能有如下图所示的四种可能。

5. 二叉树的建立

说了半天，我们如何在内存中生成一棵二叉链表的二叉树呢？树都没有，哪来遍历。所以我们还得来谈谈关于二叉树建立的问题。
如果我们要在内存中建立一个如下图中左图这样的树，为了能让每个结点确认是否有左右孩子，我们对它进行了扩展，变成下图中右图的样子，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值，比如 “#”。我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。比如下图的前序遍历序列就为 AB#D##C##。

有了这样的准备，我们就可以来看看如何生成一棵二叉树了。假设二叉树的结点均为一个字符，我们把刚才前序遍历序列 AB#D##C# 用键盘挨个输入。实现的算法如下：

/* 按前序输入二又树中结点的值(一个字符) */
/* #表示空树，构造二叉链表表示二叉树T。*/
void CreateBiTree(BiTree *T)
{
	TElemType ch;
	
	scanf("%C",&ch);
	ch=str[index++];
	
	if (ch=='#')
		*T=NULL;
	else
	{
		*T=(BiTree)malloc(sizeof(BiTNode));
		if(!*T)
			exit(OVERFLOW);
		(*T)->data=ch;	/* 生成根结点 */
		CreateBiTree(&(*T)->lchi1d);	/* 构造左子树 */
		CreateBiTree(&(*T)->rchild);	/* 构造右子树 */
	}
}

其实建立二叉树，也是利用了递归的原理。只不过在原来应该是打印结点的地方，改成了生成结点、给结点赋值的操作而已。所以大家理解了前面的遍历的话，对于这段代码就不难理解了。

6. 线索二叉树

6.1 线索二叉树的原理

我们现在提倡节约型社会，一切都应该节约为本。对待我们的程序当然也不例外，能不浪费的时间或空间，都应该考虑节省。我们再来观察下图，会发现指针域并不是都充分的利用了，有许许多多的 “^”，也就是空指针域的存在，这实在不是好现象，应该要想办法利用起来。

首先我们要来看看这空指针有多少个呢？对于一个有n个结点的二叉链表，每个结点有指向左右孩子的两个指针域，所以一共是2n个指针域。而n个结点的二叉树一共有n-1条分支线数，也就是说，其实是存在2n-(n-1)=n+1个空指针域。比如上图有 10 个结点，而带有 “^" 空指针城为 11。这些空间不存储任何事物，白白的浪费着内存的资源。
另一方面，我们在做遍历时，比如对上图做中序遍历时，得到了 HDIBJEAFCG 这样的字符序列，遍历过后，我们可以知道，结点 1 的前驱是D，后继是B，结点F的前驱是A，后继是C。也就是说，我们可以很清楚的知道任意一个结点，它的前驱和后继是哪一个。
可是这是建立在已经遍历过的基础之上的。在二叉链表上，我们只能知道每个结点指向其左右孩子结点的地址，而不知道某个结点的前驱是谁，后继是谁。要想知道，必须遍历一次。以后每次需要知道时，都必须先遍历一次。为什么不考虑在创建时就记住这些前驱和后继呢，那将是多大的时间上的节省。
综合刚才两个角度的分析后，我们可以考虑利用那些空地址，存放指向结点在某种遍历次序下的前驱和后继结点的地址。就好像 GPS 导航仪一样，我们开车的时候，哪怕我们对具体目的地的位置一无所知，但它每次都可以告诉我从当前位置的下一步应该走向哪里。这就是我们现在要研究的问题。我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。
请看下图，我们把这棵二叉树进行中序遍历后，将所有的空指针域中的rchild，改为指向它的后继结点。于是我们就可以通过指针知道H的后继是D（图中①），I的后继是B（图中②），J的后继是E（图中③），E的后继是A （图中④），F的后继是C （图中⑤），G的后继因为不存在而指向NULL（图中⑥）。此时共有 6 个空指针域被利用。

再看下图，我们将这棵二叉树的所有空指针域中的lchild，改为指向当前结点的前驱。因此H的前驱是NULL（图中①），I的前驱是D（图中②），J的前驱是B（图中③），F的前驱是A（图中④），G的前驱是C（图中⑤）。一共 5 个空指针域被利用，正好和上面的后继加起来是 11 个。

通过下图（空心箭头实线为前驱，虚线黑箭头为后继），就更容易看出，其实线索二叉树，等于是把一棵二叉树转变成了一个双向链表，这样对我们的插入删除结点、查找某个结点都带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。

不过好事总是多磨的，问题并没有彻底解决。我们如何知道某一结点的lchild是指向它的左孩子还是指向前驱？rchild是指向右孩子还是指向后继？比如E结点的lchild是指向它的左孩子J，而rchild却是指向它的后继A。显然我们在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继上是需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是存放 0 或 1 数字的布尔型变量，其占用的内存空间要小于像lchild和rchild的指针变量。结点结构如下表所示。

其中：

ltag为 0 时指向该结点的左孩子，为 1 时指向该结点的前驱。
rtag为 0 时指向该结点的右孩子，为 1 时指向该结点的后继。

因此对于本章节第一张图的二叉链表图可以修改为下图的样子。

6.2 线索二叉树结构实现

由此二叉树的线案存储结构定义代码如下：

/* 二叉树的二叉线索存储结构定义 */
typedef char TElemType;
typedef enum{Link,Thread} PointerTag;	/* Link=0表示指向左右孩子指针, */
										/* Thread=1表示指向前驱或后继的线索 */
typedef struct BiThrNode	/* 二叉线索存储结点结构 */
{
	TElemType data;	/* 结点数据 */
	struct BiThrNode *lchild, *rchild;	/* 左右孩子指针 */
	PointerTag LTag;
	PointerTag RTag;	/* 左右标志 */
}BiThrNode, *BiThrTree;

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。
中序遍历线索化的递归函数代码如下：

BiThrTree pre;	/* 全局变量，始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree p)
{
	if(p)
	{
		InThreading(p->lchi1d);	/* 递归左子树线索化 */
		if(!p->1child)	/* ★★★没有左孩子 */
		{
			p->LTag=Thread;	/* ★★★前驱线索 */
			p->lchi1d=pre;	/* ★★★左孩子指针指向前驱 */
		}
		if(!pre->rchild)	/* ★★★前驱没有右孩子 */
		{
			pre->RTag=Thread;	/* ★★★后继线索 */
			pre->rchild=p;	/* ★★★前驱右孩子指针指向后继(当前结点p) */
		}
		pre=p;	/* ★★★保持pre指向p的前驱 */
		InThreading(p->rchild);	/* 递归右子树线索化 */
	}
}

你会发现，这代码除加★★★以外，和二叉树中序遍历的递归代码几乎完全一样。只不过将本是打印结点的功能改成了线索化的功能。
中间加粗部分代码是做了这样的一些事：
if(p->lchild)表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过，赋值给了pre，所以可以将pre赋值给p->lchild，并修改p->LTag=Thread（也就是定义为 1）以完成前驱结点的线索化。
后继就要稍稍麻烦一些。因为此时p结点的后继还没有访问到，因此只能对它的前驱结点pre的右指针rchild做判断，if(!pre->rchild)表示如果为空，则p就是pre的后继，于是pre->rchild=p，并且设置pre->RTag=Thread，完成后继结点的线索化。
完成前驱和后继的判断后，别忘记将当前的结点p赋值给pre，以便于下一次使用。
有了线索二叉树后，我们对它进行遍历时发现，其实就等于是操作一个双向链表结构。
和双向链表结构一样，在二叉树线索链表上添加一个头结点，如下图所示，并令其lchild域的指针指向二叉树的根结点（图中的①），其rchid域的指针指向中序遍历时访问的最后一个结点（图中的②）。反之，令二叉树的中序序列中的第一个结点中，lchild域指针和最后一个结点的rchild 域指针均指向头结点（图中的③和④）。这样定义的好处就是我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

遍历的代码如下：

/* T指向头结点， 头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的 */
/* 最后一个结点。中序遍历二叉线索链表表示的二叉树T */
Status InOrderTraverse_Thr(BiThrTree T)
{
	BiThrTree p;
	p=T->1child;	/* p指向根结点 */
	while(p!=T)	/* 空树或遍历结束时，p==T */
	{
		while(p->LTag==Link)	/* 当LTag--O时循环到中序序列第一个结点 */
			p=p->lchi1d;
		printf ("%c",p->data);	/* 显示结点数据，可以更改为其他对结点操作 */
		while(p->RTag==Thread && p->rchild!=T)
		{
			p=p->rchild;
			printf("%c",p->data);	/* 访问后继节点 */
		}
		p=p->rchi1d;	/* p进至其右子树根 */
	}
	return OK;
}

代码中，第 6 行，p=T>lchild;意思就是上图中的①，让p指向根结点开始遍历。
第 7~18 行，while(p!=T)其实意思就是循环直到图中的④的出现，此时意味着p指向了头结点，于是与T相等（T是指向头结点的指针），结束循环，否则一直循环下去进行遍历操作。
第 9~10 行，whild(p->LTag==Link)这个循环，就是由 A→B→D→H，此时H结点的LTag不是Link（就是不等于0），所以结束此循环。
第 11 行，打印H。
第 12~16 行，while(p->RTag==Thread && p->rchid!=T)，由于结点H的RTag==Thread（就是等于 1），且不是指向头结点。因此打印H的后继D，之后因为D的RTag是Link，因此退出循环。
第17行，p=p->rchil;意味着p指向了结点D的右孩子I。
······就这样不断循环遍历，路径参照下图，直到打印出 HDIBJEAFCG，结束遍历操作。

从这段代码也可以看出，它等于是一个链表的扫描，所以时间复杂度为O(n)。
由于它充分利用了空指针域的空间（这等于节省了空间），又保证了创建时的一次遍历就可以终生受用前驱后继的信息（这意味着节省了时间）。所以在实际问题中，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

7. 总结

二叉树每个结点最多两棵子树，有左右之分。本章提到了斜树，满二叉树、完全二叉树等特殊二叉树的概念。
我们接着谈到它的各种性质，这些性质给我们研究二叉树带来了方便。
二叉树的存储结构由于其特殊性使得既可以用顺序存储结构又可以用链式存储结构表示。
遍历是二叉树最重要的一门学问，前序、中序、后序以及层序遍历都是需要熟练掌握的知识。要让自己要学会用计算机的运行思维去模拟递归的实现，可以加深我们对递归的理解。不过，并非二叉树遍历就一定要用到递归，只不过递归的实现比较优雅而已。这点需要明确。
二叉树的建立自然也是可以通过递归来实现。
研究中也发现，二叉链表有很多浪费的空指针可以利用，查找某个结点的前驱和后继为什么非要每次遍历才可以得到，这就引出了如何构造一棵线索二叉树的问题。线索二叉树给二叉树的结点查找和遍历带来了高效率。
下一章再讲，树、森林与二叉树之间的转换。