这是一篇非常好的关于线索二叉树的文章，内容详细到位，叙述清晰。作者应该是很认真、细心的人，估计花了不少时间和精力，向作者致敬！
一、线索二叉树概念
具有n 个结点的二叉连结串列中，其二叉连结串列的n 个结点中共有2n 个指标域，在这2n 个指标域中，真正用于指向后件（左子结点或右子结点）的指标域只有n-1 个，而另外的n+1 个指标域都是空的。这样就利用二叉连结串列中的空指标域，存放指向结点在某种遍历次序下的前趋和后继结点的指标（这种附加的指标称为” 线索” ），这种加上了线索的二叉连结串列称为线索连结串列，相应的二叉树称为线索二叉树(ThreadedBinaryTree) 。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
二、线索连结串列的结点结构
线索连结串列中的结点结构为：
ltag 和 rtag 是增加的两个标志域，用来区分结点的左、右指标域是指向其左、右孩子的指标，还是指向其前趋或后继的线索。
三、二叉树的线索化
1 ．线索化和线索化实质
将二叉树变为线索二叉树的过程称为线索化 。按某种次序将二叉树线索化的实质是：按该次序遍历二叉树，在遍历过程中用线索取代空指标。
2 ．二叉树的中序线索化
（ 1 ）分析
演算法与中序遍历演算法类似，只需要将遍历演算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。
a). 若上次访问到的结点的右指标为空，则将当前访问到的结点序号填入，并置右标志域为 1 ；
b). 若当前访问到的结点的左指标为空，则将上次访问到的及诶单序号填入，并置左标志域为 1
（ 2 ）将二叉树按中序线索化的演算法
PROCEDURE INTHREAD(BT,h)
IF BT != 0 THEN
{
INTHREAD(L(BT),h)
IF (h != 0) and (R(h) = 0) THEN
{ R(h) = BT; Rflag(h) = 1; }
IF L(BT) = 0 THEN
{ L(BT) = h; Lflag(BT) = 1; }
h = BT
INTHREAD(R(BT),h)
}
RETURN （ 3 ）演算法分析
和中序遍历演算法一样，递回过程中对每结点仅做一次访问。因此对于 n 个结点的二叉树，演算法的时间复杂度亦为 O(n)。
3 ．二叉树的前序线索化和后序线索化
前序线索化和后序线索化演算法与二叉树的中序线索化类似。
四、线索二叉树的运算
1 ．在中序线索二叉树中，查询结点 *p 的中序后继结点
在中序线索二叉树中，查询结点 *p 的中序后继结点分两种情形：
a). 若 *p 的右子树空 ( 即 p->rtag 为 Thread) ，则 p->rchild 为右线索，直接指向 *p 的中序后继。
b). 若 *p 的右子树非空 ( 即 p->rtag 为 Link) ，则 *p 的中序后继必是其右子树中第一个中序遍历到的结点。也就是从*p 的右孩子开始，沿该孩子的左链往下查询，直至找到一个没有左孩子的结点为止，该结点是*p 的右子树中“ 最左下” 的结点，即*P 的中序后继结点。
具体演算法如下：
BinThrNode *Inorderpre(BinThrNode *p)
{ //在中序線索樹中找結點*p的中序前趨，設p非空
BinThrNode *q；
if (p->ltag==Thread) //*p的左子樹為空
return p->lchild； //返回左線索所指的中序前趨
else{
q=p->lchild； //從*p的左孩子開始查詢
while (q->rtag==Link)
q=q->rchild； //右子樹非空時，沿右鏈往下查詢
return q； //當q的右子樹為空時，它就是最右下結點
} //end if
} 该演算法的时间复杂度不超过树的高度 h ，即 O(h) 。
2 ．在中序线索二叉树中查询结点 *p 的中序前趋结点
中序是一种对称序，故在中序线索二叉树中查询结点 *p 的中序前趋结点与找中序后继结点的方法完全对称。具体情形如下：
a). 若 *p 的左子树为空，则 p->1child 为左线索，直接指向 *p 的中序前趋结点；
b). 若 *p 的左子树非空，则从 *p 的左孩子出发，沿右指标链往下查询，直到找到一个没有右孩子的结点为止。该结点是*p 的左子树中“ 最右下” 的结点，它是*p 的左子树中最后一箇中序遍历到的结点，即*p 的中序前趋结点。
具体演算法如下：
BinThrNode *Inorderpre(BinThrNode *p)
{ //在中序線索樹中找結點*p的中序前趨，設p非空
BinThrNode *q；
if (p->ltag==Thread) //*p的左子樹為空
return p->lchild； //返回左線索所指的中序前趨
else{
q=p->lchild； //從*p的左孩子開始查詢
while (q->rtag==Link)
q=q->rchild； //右子樹非空時，沿右鏈往下查詢
return q； //當q的右子樹為空時，它就是最右下結點
} //end if
} 由上述讨论可知：对于非线索二叉树，仅从*p 出发无法找到其中序前趋( 或中序后继) ，而必须从根结点开始中序遍历，才能找到*p 的中序前趋( 或中序后继) 。线索二叉树中的线索使得查询中序前趋和中序后继变得简单有效。
3 ．在后序线索二叉树中，查询指定结点 *p 的后序前趋结点
在后序线索二叉树中，查询指定结点 *p 的后序前趋结点的具体规律是：
a). 若 *p 的左子树为空，则 p->lchild 是前趋线索，指示其后序前趋结点。
b). 若 *p 的左子树非空，则 p->lchild 不是前趋线索。由于后序遍历时，根是在遍历其左右子树之后被访问的，故 *p的后序前趋必是两子树中最后一个遍历结点。
当 *p 的右子树非空时， *p 的右孩子必是其后序前趋
当 *p 无右子树时， *p 的后序前趋必是其左孩子
4 ．在后序线索二叉树中，查询指定结点 *p 的后序后继结点
具体的规律：
a). 若 *p 是根，则 *p 是该二叉树后序遍历过程中最后一个访问到的结点。*p 的后序后继为空；
b). 若 *p 是其双亲的右孩子，则 *p 的后序后继结点就是其双亲结点
c). 若 *p 是其双亲的左孩子，但 *P 无右兄弟， *p 的后序后继结点是其双亲结点；
d). 若*p 是其双亲的左孩子，但*p 有右兄弟，则*p 的后序后继是其双亲的右子树中第一个后序遍历到的结点，它是该子树中“ 最左下的叶结点” ；
由上述讨论中可知：在后序线索树中，仅从*p出发就能找到其后序前趋结点；要找*p的后序后继 结点，仅当*p的右子树为空时，才能直接由*p的右线索p->rchild得到。否则必须知道*p的双亲结点才能找到其后序后继。因此，如果线索二叉树中的结点没有指向其双亲结点的指标，就可能要从根开始进行后序遍历才能找到结点*P的后序后继。由此，线索对查询指定结点的后序后继并无多大帮助。
5 ．在前序线索二叉树中，查询指定结点 *p 的前序后继结点
6 ．在前序线索二叉树中，查询指定结点 *p 的前序前趋结点
在前序线索二叉树中，找某一点*p的前序后继也很简单，仅从*p出发就可以找到；但找其前序前趋 也必须知道*p的双亲结点。当树中结点未设双亲指标时，同样要进行从根开始的前序遍历才能找到结点*p的前序前趋。
五、遍历线索二叉树
遍历某种次序的线索二叉树，只要从该次序下的开始结点开发，反覆找到结点在该次序下的后继，直至终端结点。遍历中序线索二叉树演算法：
PROCEDURE INTHTRAV(BT)
IF BT = 0 THEN RETURN
h = BT
WHILE (Lflag(h) = 0) DO h = L(h)
OUTPUT V(h)
WHILE (R(h) != 0 DO
{
IF (Rflag(h) = 1) THEN h = R(h)
ELSE
{
h = R(h)
WHILE ((Lflag(h) = 0) and (L(h) != 0)) DO h = L(h)
}
OUTPUT V(h)
}
RETURN <span>
</span> 分析：
a). 中序序列的终端结点的右线索为空，所以 do 语句的终止条件是 p==NULL 。
b). 该演算法的时间复杂性为 O(n) 。因为是非递回演算法，常数因子上小于递回的遍历演算法。因此，若对一棵二叉树要经常遍历，或查询结点在指定次序下的前趋和后继，则应采用线索连结串列作为储存结构为宜。
c). 以上介绍的线索二叉树是一种全线索树（即左右线索均要建立）。许多应用中只要建立左右线索中的一种。
d). 若线上索连结串列中增加一个头结点，令头结点的左指标指向根，右指标指向其遍历序列的开始或终端结点会更方便。
六、验证前序线索及前序线索遍历和中序线索及中序线索遍历的程式
#include <iostream>
#include <sstream>
using namespace std;
template<class T>
struct tbtnode
{
T s_t;
bool lflag;
bool rflag;
tbtnode *lchild;
tbtnode *rchild;
};
template<class T>
tbtnode<T>* createtbt(tbtnode<T>* tbt, int k, ostream& out, istream& in)
{
tbtnode<T> *p, *t;
T tmp;
out << "Input key: " << endl;
in >> tmp;
out << '\t' << tmp << endl;
if ('0' != tmp)
{
p = new tbtnode<T>;
p->s_t = tmp;
p->lchild = NULL;
p->rchild = NULL;
p->lflag = 0;
p->rflag = 0;
if (0 == k) t = p;
if (1 == k) tbt->lchild = p;
if (2 == k) tbt->rchild = p;
createtbt(p, 1, out, in);
createtbt(p, 2, out, in);
}
return (t);
}
template<class T>
void pretraverse(tbtnode<T> *root)
{
if (NULL != root)
{
cout << root->s_t << " ";
pretraverse(root->lchild);
pretraverse(root->rchild);
}
}
template<class T>
void intraverse(tbtnode<T> *root)
{
if (NULL != root)
{
intraverse(root->lchild);
cout << root->s_t << " ";
intraverse(root->rchild);
}
}
template<class T>
void postraverse(tbtnode<T> *root)
{
if (NULL != root)
{
postraverse(root->lchild);
postraverse(root->rchild);
cout << root->s_t << " ";
}
}
template<class T>
void inthread(tbtnode<T> *tbt, tbtnode<T> **h)
{
if (NULL != tbt)
{
inthread(tbt->lchild, h);
if (tbt->lchild == NULL)
{
tbt->lchild = *h;
tbt->lflag = 1;
}
if ((*h != NULL) && ((*h)->rchild == NULL))
{
(*h)->rchild = tbt;
(*h)->rflag = 1;
}
*h = tbt;
inthread(tbt->rchild, h);
}
}
template<class T>
void prethread(tbtnode<T> *tbt, tbtnode<T> **h)
{
if (NULL != tbt)
{
if (tbt->lchild == NULL)
{
tbt->lchild = *h;
tbt->lflag = 1;
}
if ((*h != NULL) && ((*h)->rchild == NULL))
{
(*h)->rchild = tbt;
(*h)->rflag = 1;
}
*h = tbt;
//*h = tbt->lchild;
if (tbt->lflag == 0)
prethread(tbt->lchild, h);
if (tbt->rflag == 0)
prethread(tbt->rchild, h);
}
}
template<class T>
void posthread(tbtnode<T> *tbt, tbtnode<T> **h)
{
if (NULL != tbt)
{
posthread(tbt->lchild, h);
posthread(tbt->rchild, h);
if (tbt->lchild == NULL)
{
tbt->lchild = *h;
tbt->lflag = 1;
}
if ((*h != NULL) && ((*h)->rchild == NULL))
{
(*h)->rchild = tbt;
(*h)->rflag = 1;
}
*h = tbt;
}
}
template<class T>
void inthtraverse(tbtnode<T> *tbt)
{
tbtnode<T> *h;
if (tbt == NULL) return;
h = tbt;
while (h->lflag == 0) h = h->lchild;
cout << h->s_t << " ";
while (h->rchild != NULL)
{
if (h->rflag == 1)
h = h->rchild;
else
{
h = h->rchild;
while ((h->lflag == 0) && (h->lchild != NULL))
h = h->lchild;
}
cout << h->s_t << " ";
}
}
template<class T>
void prethtraverse(tbtnode<T> *tbt)
{
tbtnode<T> *h;
if (tbt == NULL) return;
h = tbt;
cout << tbt->s_t << " ";
while (h->rchild != NULL)
{
if ((h->lflag == 0) && (h->lchild != NULL))
{
h = h->lchild;
}
else
{
h = h->rchild;
}
cout << h->s_t << " ";
}
}
template<class T>
void posthtraverse(tbtnode<T> *tbt)
{
tbtnode<T> *h;
if (tbt == NULL) return;
h = tbt;
}
int main()
{
typedef tbtnode<char> tbtnode_char;
tbtnode_char *root;
//istringstream ssin(string("AB0DG000CE0H00F00"));
istringstream ssin(string("ABCD00E00FG00H00IJK00L00MN00O00"));
root = createtbt(root, 0, cout, ssin);
pretraverse(root);
cout << endl;
intraverse(root);
cout << endl;
postraverse(root);
cout << endl;
cout << "通過穿線二叉樹進行遍歷" << endl;
tbtnode_char *h = NULL;
//inthread(root, &h);
//inthtraverse(root);
prethread(root, &h);
prethtraverse(root);
cout << endl;
return 0;
}
转载请注明：XAMPP中文组官网 » 线索二叉树算法原理,建立和遍历运算方法