假期连载之十一
（树形结构—二叉树）
这是12号发布的第二篇连载，为了突出树形结构的重要性，以及方便对该部分内容的整理工作，故将本节内容分段进行发布。同时为了突出树的应用性，我们可能会在这两天进行一个关于前阵时间讨论过的迷宫问题扩展的研究，由于时间制约不一定会准时放出。
二叉树
二叉树Binary tree是一类特殊且重要的树形结构，其原因在于：
1、 二叉树是树形结构中相对最简单的一种结构；
2、 其它非二叉树结构的树均可以转化为二叉树进行处理；
3、 二叉树是最方便于计算机进行处理的树形结构。
一般地，二叉树是指满足下列两个条件的树形结构：
1、 每个结点的度都不大于2；
2、 每个结点的子女结点的次序不能任意颠倒。
由此可以看出，一个二叉树中的每个结点只能含有0、1、2个子结点，同时每个子结点有左右之分，且左右子结点的次序不能颠倒。
根据二叉树的定义，我们可以给出二叉树的五种基本形态，包括空二叉树、只有根结点的二叉树、只有做子树的二叉树、只有右子树的二叉树、左右子树均非空的二叉树。综上我们得出二叉树具有以下5种性质：
1、 在二叉树的第i层上至多有2^(i-1)个结点，其中i>=1；
2、 深度为k的二叉树至多有2^k-1个结点，其中k>=1；
3、 对于任意二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+1；
下面两条性质是针对某些特殊二叉树的，它们定义为：
满二叉树full binary tree，深度为k的满二叉树是有2^k-1个结点的二叉树，在每一层中其结点数都达到了最大个数。
完全二叉树complete binary tree，如果一棵具有n个结点的深度为k的二叉树，它的每一结点都与高度为k的满二叉树中编号为1～n的结点一一对应，则称这棵二叉树为完全二叉树。
完全二叉树所不同的是，1～n必须是连续对应的，但允许尾部并不完整，这说明满二叉树一定是完全二叉树，但完全二叉树并不一定是满二叉树。
4、 具有n个结点的完全二叉树的深度为log2(n)+1；
5、 对于具有n个结点的完全二叉树，如果按照从上至下、从左至右的顺序对二叉树中所有结点从1开始顺序编号，则对于任意序号为i的结点有：
a) 如i=1，则序号为i的结点是根结点；
b) 如果2*i>n，则序号为i的结点无左子结点；
c) 如果2*i+1>n，则序号为i的结点无右子结点。
二叉树的存储结构
二叉树同样可以分别用顺序存取结构和链式存储结构来表示，但其优缺点是非常明显的。
在顺序存储结构中，假设二叉树T为完全二叉树，则其结点编号对于满二叉树来说是连续的，因此可以依据其结点编号作为一维数组下标，这是一种既简单又节省空间的存储方式。
但大多数情况下T可能并不会处于上述特殊状态中，仅仅是一般定义上的二叉树结构。此时如果需要使用顺序存储结构，依然根据结点编号进行存储，但在缺少子结点或兄弟结点的地方必须按照完全二叉树进行处理，并将空缺的元素留空。这就造成了存储空间上的浪费，且无法进行有效的压缩存储。
这时链式存储就显示出了极大的优势。二叉树的结点包括了三个域：leftChild左子结点指针、data数据域、rightChild右子结点指针。同时为了能使二叉树进行逆序操作，还可以再添加一个parent父结点指针，这就是二叉树的三叉链表表示。
这里给出二叉链表的结点结构C语言描述：
typedef struct Node
{
DataType data;
struct Node *LChild;
struct Node *RChild;
//struct Node *Parent; 父结点指针要看实际需要或改变为三叉链表
}BiTNode,*BiTree;
二叉树的遍历与应用
二叉树的遍历是二叉树中进行查询、修改、增删等众多运算的基础，其实质上是将二叉树中结点按一定规律线性化的操作，目的在于将非线性化结构变为线性化的访问队列。
我们令L、R、V分别表示一个结点的左子树、右子树和访问该结点的操作，据此可以总结出六种遍历顺序：LRV、LVR、RLV、RVL、VRL、VLR，我们一般规定按照先左后右的顺序，以访问结点操作为标准得出以下三种基本规则：VLR先序遍历、LVR中序遍历、LRV后序遍历。
这里仅给出二叉树中序遍历算法的C++泛型应用：
template<class T>
void BinaryTree<T>::InOrder(BinTreeNode<T> *subTree,void(*visit)
(BinTreeNode<T> *p)){
if(subTree!=NULL)
{
InOrder(subTree->leftChild,visit);
visit(subTree);
InOrder(subTree->rightChild,visit);
}
};
可以看出，以上二叉树的遍历运算都是基于递归的方式来进行的，而其它两种运算和上面仅仅存在递归顺序的差异。
利用二叉树的递归遍历，我们可以进行很多相关基本运算。例如扩展先序遍历序列来创建二叉链表达到存储二叉树的目的：
void CreateBiTree(BiTree *bt)
{
char ch;
ch=getchar();
if(ch==’.’)
*bt=NULL;
else
{
*bt=(BiTree)malloc(sizeof(BiTNode));
(*bt)->data=ch;
CreateBiTree(&((*bt)->LChild));
CreateBiTree(&((*bt)->RChild));
}
}
现在我们以后序遍历举例，求二叉树深度的递归算法：
int PostTreeDepth(BiTree bt)
{
//需要注意根结点的高度算1，若二叉树为空则其高度为0
int hl,hr,max;
if(bt!=NULL)
{
hl=PostTreeDepth(bt->LChild);
hr=PostTreeDepth(bt->RChild);
max=hl>hr?hl:hr; //按定义深度为所有结点层次的最大值
return max+1;
}
else
return 0;
}
二叉树遍历的非递归算法
二叉树遍历要消除递归，则需采用工作栈的方式保持其回溯的能力。同时根据三种遍历顺序的不同，结点入栈的顺序也不尽相同。但参考连载五迷宫A中我们给出的递归消除方案，二叉树遍历的递归消除其实是较为简单的了。
这里给出中序遍历二叉树的非递归算法，这里使用了具有栈定义的简单SDK，其结点定义为BiTNode：
void InOrder(BiTree root)
{
BiTNode *p;
InitStack(&S);
p=root;
while(p!=NULL||IsEmpty(S))
{
if(p!=NULL)
{
Push(&S,p);
p=p->LChild;
}
else
{
Pop(&S,&p);
Visit(p->data);
p=p->Rchild;
}
}
}
这里需要额外注意，在使用后序遍历的非递归运算时，会发现由于根结点无论如何也是最后被访问，因而判断何种情况下访问栈顶根结点也会成为一道障碍。我们按照以下步骤进行操作：
从根结点开始若当前结点存在，且栈不为空，则重复以下操作：
1、 从当前结点开始，入栈并走左子树，直到左子树为空；
2、 如果栈顶结点的右子树为空，或者栈顶结点的右子结点为刚访问过的结点，则退栈并访问该结点，然后将当前结点指针置空；
3、 否则走右子树，并重复上述步骤。
线索二叉树
我们知道，对于二叉链表作为二叉树的存储结构，假设有n个结点的二叉链表中共有2n个链域，但有用的非空链域仅为n-1个，其它n+1个链域均为空，这些空间是被浪费的。
同时在遍历二叉链表时，我们如果要求一个结点的前驱和后继，就必须不断调用遍历函数，其效率上也存在一些问题。因而我们需要一种方案一次解决上述两种问题，事实证明这是可行且有效的。
除LChild、Rchild和data域之外，再给二叉链表结点添加两个整形标志域Ltag和Rtag，它们的具体用法如下：当结点有左子树，则LChild指向左子结点，且Ltag为0，当结点不含左子树，则LChild指向其前驱结点，此时Ltag为1；相对于结点的右子树有同样定义，不过Rchild会指向结点的后继结点。
具体的前驱/后继仍然会按照三种基本的遍历顺序进行区分，这就是线索二叉树。其中标志域为1时的LChild和Rchild指针被称为线索，该链表结构也被称为线索链表，对普通二叉树进行遍历并添加线索的过程称为线索化二叉树。线索化了的二叉树称为线索二叉树。
现在我们以二叉树中序线索化为例，说明二叉树线索化的一般算法：
void Inthread(BiTree root)
{ //pre始终保证指向刚访问过的结点，其初值为NULL
if(root!=NULL)
{
Inthread(root->LChild);
//以下为加线索操作
if(root->LChild==NULL)
{
root->Ltag=1;
root->LChild=pre;
}
if(pre!=NULL&&pre->Rchild==NULL)
{
pre->Rchild=root;
pre->Rtag=1;
}
pre=root;
Inthread(root->RChild);
}
}
线索二叉树非常有利于寻找指定结点p的前驱或后继结点，例如在中序线索树中，寻找前驱的一般方法是当Ltag==0，则返回左子树最后一个访问的结点。
同时对于线索树的遍历，也有不同于一般二叉树遍历算法的方法：首先须求出某种遍历次序下第一个被访问的结点，然后连续求出刚访问结点的后继结点，直至所有结点均被访问。我们以中序遍历中序线索树为例：
BitNode *InFirst(BiTree Bt)
{
//这是被调用的寻找中序遍历的第一个结点函数
BiTNode *p=Bt;
if(!p)
return NULL;
while(p->Ltag==0)
p=p->LChild;
return p;
}
遍历中序线索二叉树：
void TinOrder(BiTree Bt)
{
BiTNode *p;
p=InFirst(Bt);
while(p)
{
Visit(p);
p=InNext(p); //InNext()实质上是寻找中序线索树的结点后继的函数
}
}
现在我们讨论线索二叉树的最后一个问题，即当对线索树进行插入、删除操作时，可能会破坏原有树的线索，因此其难点就不言而明：如何在结点个数发生变化时保持正确的线索。
在插入结点运算中，有插入左子结点和插入右子结点的区别，但后者明显比前者复杂，因此我们仅提供后者插入运算的分析。
当执行插入线索二叉树某结点的右子结点时也分两种情况：
1、结点的右子结点本身为空，此时插入新结点的过程很简单，且对前驱后继的关系没有任何影响。
2、若其右子结点不为空，则插入后新结点为原右子结点的父结点，此时需要修改原来父结点右子树中最左下端结点的左指针值，使其指向新结点，从而满足前驱后继关系。
当进行删除操作时，其原理和插入结点是互逆的，例如在中序线索树中删除结点右子结点，则需将父结点右子树的最左下端结点的左指针重新指向父结点。
（未完待续）