【版权声明：转载请保留出处：blog.csdn.net/algorithm_only。邮箱：liuy0711@foxmail.com】
前面说到二叉树的二叉链表表示实现，当以二叉树作为存储结构时，只能找到节点的左右孩子信息，不能直接得到结点在任一序列中的前驱和后继信息，只有在遍历过程中才能得到这种信息。我们知道，在n个结点的二叉链表栈必定存在n+1个空链域，因此，可以利用这些空链域来存放这些结点信息。所以作如下规定：若结点右左子树，则其lchild域指向其左孩子，否则令lchild域指向其前驱；若结点有右子树，其rchild域指向其右孩子，否则指向其后继。以这种结构构成的二叉链表叫做线索链表。
- 线索链表的存储结构
typedef enum {link, thread} pointer_tag;
typedef struct tnode {
elemtype data;
struct tnode *lchild, *rchild;
pointer_tag ltag, rtag;
}bithrnode, *bithrtree;
- 二叉树的线索化（中序线索化）
int inorder_threading(bithrtree *thrt, bithrtree bt)
{
*thrt = (bithrtree) malloc (sizeof(bithrnode));
if (!*thrt)
exit(OVERFLOW);
/* 将头结点线索化 */
(*thrt)->ltag = link;
(*thrt)->rtag = thread;
(*thrt)->rchild = (*thrt);
if (!bt) /* 若二叉树为空，则将lchild指向自己 */
(*thrt)->lchild = (*thrt);
else {
(*thrt)->lchild = bt; /* 头结点左指针指向根结点 */
pre = (*thrt);
in_threading(bt); /* 中序遍历进行中序线索化 */
pre->rchild = *thrt;
pre->rtag = thread;
(*thrt)->rchild = pre;
}
return OK;
}
void in_threading(bithrtree t)
{
if (t) {
in_threading(t->lchild);
if (!t->lchild) {
t->ltag = thread;
t->lchild = pre;
}
if (!pre->rchild) {
pre->rtag = thread;
pre->rchild = t;
}
pre = t;
in_threading(t->rchild);
}
}
线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，前驱和后继的信息是在遍历过程中才能得到，故线索化的过程即为在遍历过程中修改空指针的过程。
- 线索二叉树的遍历（中序）
int inorder_traverse_thr(bithrtree thrt, int (*visit)(bithrtree t))
{
bithrtree p;
p = thrt->lchild;
while (p != thrt) {
while (p->ltag == link)
p = p->lchild;
visit(p);
while (p->rtag == thread && p->rchild != thrt) {
p = p->rchild;
visit(p);
}
p = p->rchild;
}
return OK;
}
- 总结
在中序线索二叉树上遍历二叉树，虽然时间复杂度任然为O(n)，但相比上节所讲遍历算法，不需要栈和队列等辅助空间。