一、树的定义

树是一种一对多的数据结构，其定义如下：

树(Tree)是n(n≥0)个结点的有限集。n=0时称为空树。在任意一棵非空树中:
(1)有且仅有一个特定的称为根(Root)的结点;
(2)当 n>1时，其余结点可分为m(m>0)个互不相交的有限集 T1、T2、……、Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree )。

树的定义是用递归的方式也就是在树的定义中还用了树的定义。

对于树的定义还需要强调两点：

n>0时根结点是唯一的，不可能存在多个根结点，别和现实中的大树混在一起，现实中的树有很多根须，那是真实的树，数据结构中的树是只能有一个根结点。
m>0 时，子树的个数没有限制，但它们一定是互不相交的。像下图中的两个结构就不符合树的定义，因为它们都有相交的子树。

1.1 结点分类

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶结点(Lcaf)或终端结点;度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

1.2 结点间的关系

结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。对于结点来说其父母同体，唯一的一个，所以只能把它称为双亲了。同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。

1.3 树的其他相关概念

结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第1层，则其子树的根就在第 1+1 层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度，当前树的深度为4。

如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
森林(Forest)是 m(m>0)棵互不相交的树的集合。

对比线性表意与树的结构他们有很大的不同。
线性结构：

第一个数据元素：无前驱
最后一个数据元素：无后继
中间元素：一个前驱一个后继
树结构：
根结点：无双亲，唯一
叶节点：无孩子，可以多个
中间节点：一个双亲多个孩子

二、树的抽象数据类型

ADT 树(tree)
Data
	树是由一个根结点和若干棵子树构成。树中结点具有相同数据类型及层次关系
operation
	InitTree(*):构造空树T。
	DestroyTree(*T):销毁树T。
	CreateTree(*T,definition):按 definition 中给出树的定义来构造树。
	ClearTree(*):若树T存在，则将树T清为空树。
	TreeEmpty(里);若为空树，返回true，否则返回 false。
	TreeDepth(T):返回T的深度。
	Root(T):返回工的根结点。
	Value(m,cur_e):cur_e是树T中一个结点，返回此结点的值。
	Assign(T,cur_e,value):给树T的结点cur_e赋值为value。
	Parent(r,cur_e):若cur_e是树里的非根结点，则返回它的双亲，否则返回空。
	Leftchild(r,cur_e):若cur_e是树T的非叶结点，则返回它的最左孩子，否则返回空。
	RightSibling(T,cur_e):若cur_e有右兄弟，则返回它的右兄弟，否则返回空。
	InsertChild(*T,*p,i,c):其中p指向树T的某个结点，i为所指结点p的度加上1,非空树C与T不相交，操作结果为插入c为树T中p指结点的第i棵子树。
	DeleteChild(*T,*p,i):其中p指向树T的某个结点，i为所指结点p的度，操作结果为删除T中p所指结点的第i棵子树。
endADT

三、树的存储结构

树的存储结构主要分为三种表示法：双亲表示法、孩子表示法、孩子兄弟表示法。

3.1 双亲表示法

对于树而言，除根结点外每个结点不一定有孩子结点，但一定有且仅有一个双亲节点。
我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。

其中 data 是数据域，存储结点的数据信息。而 parent 是指针域，存储该结点的双亲在数组中的下标。

/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType;    /*树结点的数据类型，目前暂定为整型*/
typedef struct PTNode    /*结点结构*/
{
	TElemType data;    /*结点数据*/
	int parent;    /*双亲位置*/
}PTNode;
typedef struct    /*树结构*/
{
	PTNode nodes[MAX_TREE_SIZE];    /*结点数组*/
	int r,n;    /* 根的位置和结点数 */
}PTree;

由于根结点是没有双亲的，我们约定根结点的位置域为-1，这也就意味着，我们所有的结点都存有它双亲的位置。

特点：寻找双亲结点 parent 时间复杂度为 O(1),找孩子结点需要遍历整个结构。

如何改进？
可以增加一个结点最左边孩子的域，不妨叫它长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1。

另一个问题场景，我们很关注个兄弟之间的关系，双亲表示法无法体现，可以增加一个有兄弟域来体现兄弟关系，每一个姐弟爱你如果存在右兄弟，则记录下右兄弟的下表，如果右兄弟不存在，则赋值为-1。

但如果结点的孩子很多，超过了 2 个，我们又关注结点的双亲、又关注结点的孩子、还关注结点的兄弟。而且对时间遍历要求还较高，可以将此结构扩展为有双亲域、长子域、再有右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储结构设计的是否合理，取决于基于该存储结构的运算是否适合、是否方便、时间复杂度好不好等。注意也不是越多越好，有需要时再设计相应的结果。

3.2 孩子表示法

由于树种每个结点可能有多棵子树。可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，我们把这种方法叫做多重链表表示法。不过，树的每个结点的度，也就是它的孩子个数是不同的。所以可以设计两种方案来解决。
不过，树的每个结点的度，也就是它的孩子个数是不同，所以可以设计两种方案来解决：

方案一：
一种是指针域的个数就等于树的度，树的度是树各个结点度的最大值。

其中data 是数据域。child1 到 childd 是指针域，用来指向该结点的孩子结点。
树的度是 3，所以我们的指针域的个数 3。

这种方法对于树中各结点的度相差很大时，显然是很浪费空间的，因为有很多的结点，它的指针域都是空的。不过如果树的各结点度相差很小时，那就意味着开辟的空间被充分利用了，这时存储结构的缺点反而变成了优点。
既然很多指针域都可能为空，为什么不按需分配空间?

方案二：
第二种方案每个结点指针域的个数等于该姐弟爱你的度，我们专门取一个位置来存储结点指针域的个数。

其中data 为数据域，degree 为度域，也就是存储该结点的孩子结点的个数，child1 到 childd 为指针域，指向该结点的哥哥孩子的结点。

这种方法克服了浪费空间的缺点，对空间利用率是很高了，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。

能否有更好的方法，既可以减少空指针的浪费又能使结点结构相同。可以对每个及诶点的孩子建立一个单链表表示他们的关系。

孩子表示法：把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后 n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组
中。

为此，设计两种结点结构，一个是孩子链表的孩子结点。

其中 child 是数据域，用来存储某个及诶点在表头数组种的下表，next 是指针域，用来存储指向某节点的下一个孩子的指针。
另一个是表头数组的表头结点：

其中 data 是数据域，存储某结点的数据信息。firstchild 是头指针域，存储该结点的孩子链表的头指针。

孩子表示法的结构定义代码：

/*树的孩子表示法结构定义*/
#define MAX_TREE_SIZE 100
typedef struct CTNode  /* 孩子结点 */
{
	int child;
	struct CTNode *next;
} *ChildPtr;
typedef struct    /* 表头结构 */
{
	TElemType data;
	ChildPtr firstchild;
}CTBox;
typedef struct    /* 树结构 */
{
	CTBox nodes[MAX_TREE_SIZE];    /*结点数组*/
	int r,n;    /*根的位置和结点数*/
}CTree;

这样的结构对于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的，对头结点的数组循环即可。

但是这也存在着问题，如何知道某个几点的双亲是谁呢？比较麻烦，需要整棵树遍历才行，难道就不可以把双亲表示法和孩子表示法综合一下吗？可以。

我们把这种方法称为双亲孩子表示法，应该算是孩子表示法的改进。

3.3 孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

其中 data 是数据域，firstchild 为指针域，存储该结点的第一个孩子结点的存储地址，rightsib 是指针域，存储该结点的右兄弟结点的存储地址。
结构定义代码：

/*树的孩子兄弟表示法结构定义*/
typedef struct CSNode
{
	TElemType data;
	struct CSNode *firstchild,*rightsib;
} CSNode, *CSTress;

当然如果需要查找结点的双亲，可以增加一个 parent 指针域。
这个表示法的最大好处是它把一棵复杂的树变成了一棵二叉树。

四、二叉树的定义

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

4.1 二叉树特点

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

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

空二叉树。
只有一个根结点
根结点只有左子树
根结点只有右子树
根结点即有左子树又右子树
若只从形态上考虑，三个结点的树只有两种情况，那就是图中有两层的树 1和有三层的后四种的任意一种，但对于二叉树来说，由于要区分左右，所以就演变成五种形态，树 2、树 3、树 4 和树5 分别代表不同的二叉树。

4.2 特殊二叉树

斜树
所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。如上图树 2 就是左斜树，树 5 就是右斜树。斜树的特点，就是每一层都只有一个结点，姐弟爱你的个数与二叉树的深度相同。其实线性表结构就可以理解为是树的一种极特殊表现形式。
满二叉树
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树的特点：
- 叶子结点只能出现在最下一层。出现在其他层就不可能达成平衡了。
- 非叶子结点的度一定是 2。
- 在同样深度的二叉树中，满二叉树的结点个数最多、叶子数最多。
完全二叉树
对一棵具有 n 个结点的二叉树按层序编号，如果编号为i(1<i<n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树，如图所示。
- 满二叉树一定是一棵完全二叉树，但完全二叉树不一定满。
- 完全二叉树的所有结点与同样深度的满二叉树，它们按照层序编号相同的结点是一一对应的。如同种三棵树都不是完全二叉树。
  
  二叉树的特点：
- 叶子结点只能出现最下两层。
- 最下层的叶子一定集中在左部连续位置。
- 倒数二层，若有叶子结点，一定都在右部连续位置。
- 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
- 同样结点数的二叉树，完全二叉树的深度最小。

五、二叉树的性质

5.1 二叉树的性质1

性质 1：在二叉树的第 i 层上至多有 2^(i-1)个结点(i>=1)

5.2 二叉树性质2

性质 2：深度为 K 的二叉树至多有 2^k-1 个结点(k>=1)

5.3 二叉树性质3

性质 3：对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点树为 n2，则 n0=n2+1。（叶子结点的数量为度为 2 的结点数量加 1）
终端结点数其实就是叶子结点数，而一棵二叉树，除了叶子结点外，剩下的就是度为 1或2的结点数了，我们设m为度是1的结点数。则树 T 结点总数n=n0+n1+n2。

如图，结点总数为 10，它是由 A、B、C、D 等度为 2 结点，F、G、H、1、J等度为0的叶子结点和E 这个度为1的结点组成。总和为 4+1+5=10。
用代数表达就是分支数总数=n-1=n1+2n2。因为我们有等式 n=n0+n1+n2，可以推导出 n0+n1+n2-1=n1+2n2，所以结论就是 n0=n2+1。

5.4 二叉树性质4

性质 4：具有 n 个结点的完全二叉树的深度为⌊log2n⌋+1（⌊x⌋表示不大于 x 的最大整数）。
由满二叉树的定义我们可以知道，深度为k 的满二叉树的结点数 n 一定是 2^k-1。因为这是最多的结点个数。那么对于n=2^k-1倒推得到满二叉树的度数为k=log2(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≤log2n<k，而k作为度数也是整数，因此 k=⌊log2n⌋+1。

5.5 二叉树性质 5

性质 5:如果对一棵有n个结点的完全二叉树(其深度为⌊log2n⌋+1)的结点按层序编号(从第1 层到第⌊log2n⌋+1 层，每层从左到右)，对任一结点i(1≤i≤n)有:

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

六、二叉树的存储结构

6.1 二叉树顺序存储结构

虽然树的存储结构，并且谈到顺序存储对树这种一对多的关系结构实现起来比较困难，但二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构也可以实现。
二叉树的顺序存储结构就是用一维数组存储二叉树种的结点，并且结点的存储位置，也就是数组的下表要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。

将这棵二叉树存入到数组种，相应的下标对应其同样的位置：

对于一般二叉树，尽管层序编号不能反映逻辑关系，但可以将其按照完全二叉树编号，只不过把不存在的结点设置为“^”而已。

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

6.2 二叉链表

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。结点结构图如下所示。

其中 data 是数据域，lchild 和 rchild 都是指针域，分别存放指向左孩子和右孩子的指针。

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

七、遍历二叉树

7.1 二叉树遍历原理

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

7.2 二叉树遍历方法

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

总结：计算机只有循环、判断等方式来处理，也就是说只能处理限行序列，通过这四种遍历方法，其实都是在把树种的结点变成某种意义的线性序列。

7.3 前序遍历算法

二叉树的定义是递归定义的，所以遍历算法也可以采用递归。

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

如图，计算机会先从根结点 A 开始访问，打印输出结点数据，然后通过递归调用 PreOrderTraverse 算法进行左子树遍历，直至 H 没有左子树，返回 NULL，再访问右子树 K，然后一直返回到 B的右子树 E，然后又返回到 C，又开始访问左子树机右子树，直至整棵树被访问结束，顺序为：ABDHKECFIGJ。

7.4 中序遍历算法

同理，算法和前序类似，只是访问结点的顺序不同。

/* 二叉树的中序遍历递归算法 */
void InOrderTraverse(BiTree T)
{
	if(T == NULL)
		return;
	InOrderTraverse(T->lchild);  /* 再先序遍历左子树 */
	printf("%c", T->data);    /* 显示结点数据，可以更改为其他对结点操作 */
	InOrderTraverse(T->rchild);  /* 最后先需遍历右子树 */
}

可以从算法种得知，计算机会按照一直到左子树返回 NULL 开始访问结点，因此顺序为：HKDBEAIFCGJ

7.5 后序遍历

/* 二叉树的后序遍历递归算法 */
void PostOrderTraverse(BiTree T)
{
	if(T == NULL)
		return;
	PostOrderTraverse(T->lchild);  /* 再先序遍历左子树 */
	PostOrderTraverse(T->rchild);  /* 最后先需遍历右子树 */
	printf("%c", T->data);    /* 显示结点数据，可以更改为其他对结点操作 */
}

同理：访问顺序为先左子树再右子树最后才是根结点，因此顺序华为：KHDEBIFJGCA

7.6 推导遍历结果

通过两种二叉树遍历的结果，倒推树的结构，例如，已知一棵二叉树的前序遍历序列为 ABCDEF，中序遍历序列为：CBAEDF。

先找根结点，A，CB 为左子树的部分，EDF 为右子树的部分。
由于 D 再中序遍历的 EF 中间，因此为 EF 的根结点，先序遍历，B 比 C 先访问，因此要么 B 是 C 的根结点，要么 C 是 B 的左子树，要么 C 是 B 的右子树，又由于中序遍历 C 先访问，因此是第一种可能C 是 B 的左子树，因此最后的结构如图：

二叉树遍历的性质：

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
注意：已知前序和后序遍历，是不能确定一棵二叉树的

八、二叉树的建立

如果我们要在内存中建立一个如左图这样的树，为了能让每个结点确认是否有左右孩子，我们对它进行了扩展，变成右图的样子，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值，比如“#”。我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。比如图的前序遍历序列就为 AB#D##C##。

下面看下如何生成一颗二叉树。假设二叉树的结点均为一个字符，我们把刚才前序遍历序列AB#D##C##用键盘挨个输入。

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

其实建立二叉树，也是利用了递归的原理。只不过在原来应该是打印结点的地方，改成了生成结点、给结点赋值的操作而已。所以大家理解了前面的遍历的话，对于这段代码就不难理解了。
当然，你完全也可以用中序或后序遍历的方式实现二叉树的建立，只不过代码里生成结点和构造左右子树的代码顺序交换一下。另外，输入的字符也要做相应的更改。比如扩展二叉树的中序遍历字符串就应该为#B#D#A#C#，而后序字符串应该为###DB##CA。

九线索二叉树

9.1 线索二叉树的原理

为了节约空间，合理利用空指针域，一般对于一个有 n 结点的二叉链表，每个结点有指向左右孩子的两个指针域，所以一共是 2n 个指针域，而 n 个结点的二叉树一共有 n-1条分支线路，也就是说，其实是存在 2n-(n-1) = n+1 个空指针域。
另一方面我们再做遍历时，可以很清楚的知道任意一个结点的前驱和后继。
综合这两个寄到度，我们可以利用控制真，存放指向结点再某种遍历次序下的前驱和后继结点的地址。我们把这种指向前驱和后继的的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树(Threaded Binary Tree)。

请看图，我们把这棵二叉树进行中序遍历后，将所有的空指针域中的rchild，改为指向它的后继结点。于是我们就可以通过指针知道H的后继是 D(图中①),|的后继是 B(图中②),J 的后继是E(图中③)，E 的后继是A(图中④),F 的后继是 C(图中⑤)，G 的后继因为不存在而指向 NULL(图中⑥)。此时共有6个空指针域被利用。

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

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

我们决定指针域上指向的是孩子结点还是线索结点需要加一个区分标志位的，因此在每个结点再增加两个标志与 ltag 和 rtag，注意这两个域只存放 0、1 布尔值，其占用的内存空间远小于像 lchild 和 rchile 的指针遍历。指针结构如图：

ltag为0时指向该结点的左孩子，为1时指向该结点的前驱。
rtag为0时指向该结点的右孩子，为1时指向该结点的后继。
因此二叉链表图可以修改为图中的样子。

9.2 线索二叉树结构实现

/* 二叉树的二叉线索存储结构定义 */
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->lchild);  /*递归左子树线索化*/
		if(!p->lchild)  /* 没有左孩子*/
		{
			p->LTage=Thread;  /* 前驱线索*/
			p->lchild=pre;  /*左孩子指针指向前驱*/
		}
		if(!pre->rchild)  /* 前驱没有右孩子 */
		{
			pre->RTag=Thread;  /* 后继线索 */
			pre->rchild=p;  /* 前驱右孩子指针指向后继（当前结点 p） */
		}
		pre=p;  /*保持指向 p 的前驱*/
		InThreading(p->rchild); /*递归右子树线索化*/
	}
}

有了线索二叉树后，我们对它进行遍历时发现，其实就等于是操作一个双向链表结构。
和双向链表结构一样，在二叉树线索键表上添加一个头结点，如图所示，并令其 lchild 域的指针指向二叉树的根结点,(图中的①)，其 rchild 域的指针指向中序遍历时访问的最后一个结点(图中的②)。反之，令二叉树的中序序列中的第一个结点中，Ichild 域指针和最后一个结点的 rchild域指针均指向头结点(图中的③和④)。这样定义的好处就是我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

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

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

十、树、森林与二叉树的转换

在讲树的存储结构时，我们提到了树的孩子兄弟法可以将一棵树用二叉链表进行存储，所以借助二叉链表，树和二叉树可以相互进行转换。从物理结构来看，它们的二叉链表也是相同的，只是解释不太一样而已。因此，只要我们设定一定的规则，用二叉树来表示树，甚至表示森林都是可以的，森林与二叉树也可以互相进行转换。

10.1 树转换为二叉树

将树转为二叉树的步骤如下：

加线。在所有兄弟节点之间加一条线。
去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之中间的连线。
层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

例如图中，一棵树经过三个步骤转换为一棵二叉树。初学者容易犯的错误就是在层次调整时，弄错了左右孩子的关系。比如图中 F、G 本都是树结点 B 的孩子，是结点 E的兄弟，因此转换后，F就是二叉树结点E的右孩子，G 是二叉树结点F的右孩子。

10.2 森林转换为二叉树

森林是由若干树组成的，所以完全可以理解为，森林中的每一颗树都是兄弟，可以按照兄弟的处理办法来操作。步骤如下：

把每个树转换为二叉树。
第一棵二叉树不动，从第二棵二叉树开始，一次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

10.3 二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程，也就是反过来做而已。如图所示。步骤如下:

加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点……哈，反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。
去线。删除原二又树中所有结点与其右孩子结点的连线。
层次调整。使之结构层次分明。

10.4 二叉树转换为森林

判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。那么如果是转换成森林，步骤如下:

从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有右孩子连线都删除为止，得到分离的二叉树。
再将每棵分离后的二叉树转换为树即可。

10.5 树与森林的遍历

树的遍历分为两种方式：

一种是先根遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树。
另一种是后根遍历，即先依次后根遍历每棵子树，然后再访问根结点。

森林的遍历也分为两种方式：

前序遍历:先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。比如上图右侧三棵树的森林，前序遍历序列的结果就是 ABCDEFGHJI。
后序遍历:是先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。比如图右侧三棵树的森林，后续遍历序列的结果就是 BCDAFEJHIG。

这也就告诉我们，当以二叉链表作树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。

十一、赫夫曼树及其应用

最基本的压缩编码方式——赫夫曼编码。
在介绍赫夫曼编码前，我们必须得介绍赫夫曼树，而介绍赫夫曼树，我们不得不提这样一个人，美国数学家赫夫曼(Daid Huffman)，也有的翻译为哈夫曼。他在1952 年发明了赫夫曼编码，为了纪念他成就，于是就把他在编码中用到的特殊的二叉树称之为赫夫曼树，他的编码方法称为赫夫曼编码。也就是说，我们现在介绍的知识全都来自于近 60年前这位伟大科学家的研究成果，而我们平时所用的压缩和解压缩技术也都是基于赫夫曼的研究之上发展而来，我们应该要记住他。

11.1 赫夫曼树定义与原理

我们先把这两棵二叉树简化成叶子结点带权的二叉树，如图所示。其中 A表示不及格、B 表示及格、C 表示中等、D 表示良好、E 表示优秀。每个叶子的分支线上的数字就是所占比例数。

赫夫曼说，从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。图的二叉树a中，根结点到结点 D的路径长度就为 4，二叉树b中根结点到结点 D的路径长度为 2。树的路径长度就是从树根到每一结点的路径长度之和。二叉树a的树路径长度就为1+1+2+2+3+3+4+4=20。二叉树b的树路径长度就为 1+2+3+3+2+1+2+2=16。
如果考虑到带权的结点，结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。假设有 n个权值{w1,w2…,wn}，构造一棵有n个叶子结点的二叉树，每个叶子结点带权 wk，每个叶子的路径长度为 lk，其中带权路径长度 WPL 最小的为最优二叉树称做赫夫曼树。
有了赫夫曼对带权路径长度的定义，我们来计算一下图这两棵树的 WPL值。
二叉树a的 WPL=5x1+15x2+40x3+30x4+10x4=315
注意:这里5 是 A结点的权，1是A结点的路径长度，其他同理。二叉树b的WPL=5x3+15x3+40x2+30x2+10x2=220。

怎样的二叉树算是最优的赫夫曼树呢？

先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列，即:A5，E10，B15，D30，C40.
取头两个最小权值的结点作为一个新节点 N1的两个子结点，注意相对较小的是左孩子，这里就是 A 为N1的左孩子，E 为 N1的右孩子，如图所示。新结点的权值为两个叶子权值的和 5+10=15。
将 N1替换 A 与E，插入有序序列中，保持从小到大排列。即:N1 15，B 15,D 30，C 40。
重复步骤 2。将 N1与 B 作为一个新节点 N2的两个子结点。如图所示。N2的权值=15+15=30。
将 N3替换 N1与B，插入有序序列中，保持从小到大排列。即:N2 30，D 30,C 40。
重复步骤 2。将 N2 与 D 作为一个新节点 N3 的两个子结点。如图所示。N3的权值=30+30=60。
将 N3替换 N2与 D，插入有序序列中，保持从小到大排列。即:C 40，N3 60。
重复步骤 2。将C与 N3作为一个新节点T的两个子结点，如图所示。由于T 即是根结点，完成赫夫曼树的构造。

此时的二叉树的带权路径长度 WPL=40x1+30x2+15x3+10x4+5x4=205。与一开始的二叉树b的 WPL 值 220 相比，还少了 15。显然此时构造出来的二叉树才是最优的赫夫曼树。

通过刚才的步骤，我们可以得出构造赫夫曼树的赫夫曼算法描述。

根据给定的 n 个杈值{ W1,W2,…,Wn}构成n棵二叉树的集合 F={ T1,T2…Tn},其中每棵二叉树Ti中只有一个带权为 Wi 根结点，其左右子树均为空。
在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
在F 中删除这两棵树，同时将新得到的二叉树加入F中。
重复2 和3 步骤，直到F只含一棵树为止。这棵树便是赫夫曼树。

11.2 赫夫曼编码

当然，赫夫曼研究这种最优树的目的是为了解决当年远距离通信(主要是电报)的数据传输的最优化问题。
假设六个字母的频率为A 27，B 8，C 15，D 15，E 30，F 5，合起来正好是100%。那就意味着，我们完全可以重新按照赫夫曼树来规划它们。

左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为 0右分支改为1后的赫夫曼树。
此时，我们对这六个字母用其从树根到叶子所经过路径的0或1来编码，可以得到如表所示这样的定义。

我们将文字内容为“BADCADFEED”再次编码，对比可以看到结果串变小了。
原编码二进制:001000011010000011101100100011
(共 30 个字符 )
新编码二进制串:1001010010101001000111100
(共 25 个字符)
也就是说，我们的数据被压缩了，节约了大约17%的存储或传输成本。随着字符的增加和多字符权重的不同，这种压缩会更加显出其优势。
当我们接收到 1001010010101001000111100这样压缩过的新编码时，我们应该如何把它解码出来呢?
编码中非 0即 1，长短不等的话其实是很容易混淆的，所以若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。
你仔细观察就会发现，表中自编码就不存在容易与 1001、1000 混淆的“10”和“100”编码。
可仅仅是这样不足以让我们去方便地样码的，因此在解码时，还是要用到赫夫曼树，即发送方和接收方必须要约定好同样的赫夫曼编码规则。
当我们接收到 1001010010101001000111100 时，由约定好的赫夫曼树可知，1001 得到第一个字母是 B，接下来 01 意味着第二个字符是 A，如图 6-12-10 所示，其余的也相应的可以得到，从而成功解码。

一般地，设需要编码的字符集为{d1,d2,…,dn}，各个字符在电文中出现的次数或频率集合为{ w1,w2,…,wn}，以 d1,d2,…,dn作为叶子结点，以 w1,w2,…,wn作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1,则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是赫夫曼编码。

【Data Structure】数据结构解构其六：树及其应用