【数据结构】线索⼆叉树（构造与遍历）
主要内容
基本概念
遍历⼆叉树是对⾮线性结构结点的线性化过程，由此得到的遍历序列中，每个结点有且仅有⼀个前驱和后继（除了序列中的第⼀个和最后⼀个结点）。
原始⼆叉链表的结点结构仅包含数据元素信息和左右指针域，若在结点结构中增加前驱和后继的指针域，则该存储结构称为线索⼆叉树。
虽然可以直接增加两个指针域来实现这种结构，但这样会使结构的存储密度⼤⼤降低。（存储密度 = 数据元素本⾝占⽤的存储量 / 结点结构占⽤的存储量）
那我们应该怎么改善呢？
要想利⽤空指针域来存放前驱、后继的地址，还需要将前驱、后继和左、右⼦树根结点区分开。因此我们新增两个标志域：LTag和
RTag（整型），1表⽰有⼦树，0表⽰⽆⼦树。
1）当LTag = 0时，lchild域指⽰结点的左⼦树根结点；当LTag = 1时，lchild域指⽰结点在某个遍历序列中的前驱。
2）当RTag = 0时，rchild域指⽰结点的右⼦树根结点；当RTag = 1时，rchild域指⽰结点在某个遍历序列中的后继。
指向前驱、后继的指针称为线索。
typedef struct ThBinode
{
Elemtype data;
struct ThBinode *lchild, *rchild;
int LTag, RTag;
} ThBinode, *ThBiTree;
构造线索⼆叉树
构造线索⼆叉树实质上是将⼆叉链表中的空指针域改为前驱、后继指针域。
⼜因为前驱、后继的信息只有在遍历的时候才能得到，所以线索化的过程就是在遍历的时候修改空指针的过程。
为了记下遍历过程中访问结点的先后关系，附设⼀个指针pre指向刚刚访问过的结点（即序列中的前⼀个结点），⽽指针p指向当前访问的结点。
/*--------以结点p为根的⼦树的中序线索化--------*/
void InThreading(ThBiTree p)
{
if(p)
{
InThreading(p->lchild);  /*左⼦树递归线索化*/
if(!p->lchild)    /*如果没有左⼦树*/
{
p->LTag = 1;  /*设置前驱*/
p->lchild = pre;
}
else p->RTag = 0;  /*有左⼦树*/
if(!pre->rchild)  /*如果没有右⼦树*/
{
pre->RTag = 1;  /*设置后继*/
pre->rchild = p;
}
else pre->rchild = 0;
pre = p;
InThreading(p->rchild);  /*右⼦树递归线索化*/
}
}
/*---------带头结点的⼆叉树的中序线索化--------*/
void InOrderThreading(ThBiTree &tb, ThBiTree t)
{
tb = new ThBinode;  /*建⽴头结点*/
tb->LTag = 0;  /*头结点有左孩⼦，为根结点*/
tb->Rtag = 1;  /*头结点⽆右孩⼦，后继线索为中序遍历的最后⼀个结点*/
tb->rchild = tb;  /*初始化时后继为头结点本⾝*/
if(!t) tb->lchild = tb; /*若⼆叉树为空，左孩⼦也为头结点本⾝*/
else
{
tb->lchild = t; pre = tb; /*头结点的作⽤体现，统⼀根结点与其他结点的处理⽅式*/  InThreading(t);    /*对⼆叉树中序线索化*/
pre->RTag = 1;    /*线索化结束后，pre为⼆叉树的最右结点*/
pre->rchild = tb;  /*使其右线索指向头结点*/
tb->rchild = pre;  /*将头结点的后继从它本⾝改为最右结点*/
}
}
遍历线索⼆叉树
由于有了结点的前驱和后继信息，线索⼆叉树的遍历和指定次序下查结点的前驱和后继算法都变得简单。
线索⼆叉树的遍历不需要设栈，避免了频繁的进栈、出栈，因此在时间和空间上都较遍历⼆叉树节省。
因此，若需要经常查结点在所遍历线性序列中的前驱和后继，则采⽤线索链表作为存储结构。
1）中序线索⼆叉树
1. 查p的前驱：查左线索；若⽆左线索，结点的前驱是遍历左⼦树时访问的最后⼀个结点。
2. 查p的后继：查右线索；若⽆右线索，结点的后继是遍历右⼦树时访问的第⼀个结点。
2）先序线索⼆叉树
1. 查p的前驱：查左线索；若⽆左线索，结点的前驱是结点的双亲结点，或是先序遍历其双亲结点左⼦树时最后访问的结点。
2. 查p的后继：查右线索；若⽆右线索，结点的后继必为结点的左⼦树（若存在）或右⼦树根结点。
3）后序线索⼆叉树
1. 查p的前驱：查左线索；若⽆左线索，且⽆右线索时，结点的前驱是右⼦树根结点；若⽆左线索，但是有右线索时，结点的前驱是左⼦树根结点。
2. 查p的后继，这种查⽐较复杂，分4类情况讨论：
若p为⼆叉树的根结点，后继为空；
若p为右⼦树根结点，后继为双亲结点；
若p为左⼦树根结点，且⽆右兄弟，后继为双亲结点；
若p为左⼦树根结点，且有右兄弟，后继为后序遍历双亲结点右⼦树时访问的第⼀个结点。
由上述情况可知，在先序线索⼆叉树上前驱和在后序线索⼆叉树上后继都⽐较复杂。
遍历线索⼆叉树的时间复杂度为O(n)，与递归或⾮递归遍历⼆叉链表⼀样，但前者的空间复杂度为O(1)，⽽后者为O(n)，因为遍历线索⼆叉树不需要栈。
/*----------遍历中序线索⼆叉树----------*/
void InOrderTraverse(ThBiTree t)
{/*t指向线索⼆叉树的头结点，⽽头结点的左指针指向⼆叉树的根结点*/
ThBinode *p = t->lchild;  /*使p指向根结点*/
while(p != t)    /*若线索⼆叉树不为空或遍历未结束*/
先序中序后序遍历二叉树{
while(p->LTag == 0) p=p->lchild; /*沿左孩⼦往下，定位*/
cout<<p->data;      /*访问左⼦树为空的结点*/
while(p->RTag == 1 && p->rchild != t) /*若有右线索，且右线索不为头结点*/  {
p = r->rchild;
cout<<p->data;    /*沿右线索访问后继结点*/
}
p = p->rchild;    /*转向p的右⼦树*/
}
}