)线索二叉树
按照某种遍历方式对二叉树进行遍历，可以吧二叉树中所有结点排序为一个线性序列。在改序列中，除第一个结点外每个结点有且仅有一个直接前驱结点；除最后一个结点外每一个结点有且仅有一个直接后继结点。这些指向直接前驱结点和指向直接后续结点的指针被称为线索（Thread），加了线索的二叉树称为线索二叉树。
当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。
我们可以证明：在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的二叉链表中含有个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有n+1个空指针。
因此可以利用这些空指针，存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(ThreadedBinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
例如图(a)是一棵中序线索二叉树，它的线索链表如图(b)所示。
线索二叉树(a)
线索二叉树(b)
图(b)中，在二叉树的线索链表上增加了一个头结点，其LeftChild指针指向二叉树的根结点，其RightChild指针指向中序遍历时的最后一个结点。另外，二叉树中依中序列表的第一个结点的LeftChild指针，和最后一个结点的RightChild指针都指向头结点。这就像为二叉树建立了一个双向线索链表，既可从第一个结点起，顺着后继进行遍历，也可从最后一个结点起顺着前驱进行遍历。
如何在线索二叉树中找结点的前驱和后继结点？以图13的中序线索二叉树为例。树中所有叶结点的右链是线索，因此叶结点的RightChild指向该结点的后继结点，如图13中结点"b"的后继为结点"*"。当一个内部结点右线索标志为0时，其RightChild指针指向其右儿子，因此无法由RightChild得到其后继结点。然而，由中序遍历的定义可知，该结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。例如在找结点"*"的后继时，首先沿右指针找到其右子树的根结点"-"，然后沿其LeftChild指针往下直至其左线索标志为1的结点，即为其后继结点(在图中是结点"c")。类似地，在中序线索树中找结点的前驱结点的规律是：若该结点的左线索标志为1，则LeftChild为线索，直接指向其前驱结点，否则遍历左子树时最后访问的那个结点，即左子树中最右下的结点为其前驱结点。由此可知，若线索二叉树的高度为h，则在最坏情况下，可在O(h)时间内找到一个结点的前驱或后继结点。在对中序线索二叉树进行遍历时，无须像非线索树的遍历那样，利用递归引入栈来保存待访问的子树信息。
对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。为了记下遍历过程中访问结点的先后次序，可附设一个指针pre始终指向刚刚访问过的结点。当指针p指向当前访问的结点时，pre指向它的前驱。由此也可推知pre所指结点的后继为p所指的当前结点。这样就可在遍历过程中将二叉树线索化。对于找前驱和后继结点这二种运算而言，线索树优于非线索树。但线索树也有其缺点。在进行插人和删除操作时，线索树比非线索树的时间开销大。原因在于在线索树中进行插人和删除时，除了修改相应的指针外，还要修改相应的线索。
建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一颗二叉树。在遍历过程中，访问结点的草所是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。
另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的跟结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。
BiThrNodeType *pre;
BiThrTree InOrderThr(BiThrTree T)
{ /*中序遍历二叉树T，并将其中序线索化，pre为全局变量*/
BiThrTree head;
head=(BitThrNodeType *)malloc（sizeof（BiThrType））;/*设申请头结点成功*/
head->ltag=0;head->rtag=1;/*建立头结点*/
head->rchild=head;/*右指针回指*/
if(！T)head->lchild=head;/*若二叉树为空，则左指针回指*/
else{head->lchild=T;pre=head;
InThreading(T);/*中序遍历进行中序线索化*/
pre->rchild=head;
pre->rtag=1;/*最后一个结点线索化*/
head->rchild=pre;
};
return head;
}
void InThreading(BiThrTree p)
{/*通过中序遍历进行中序线索化*/
if(p)
{InThreading(p->lchild);/*左子树线索化*/
if(p->lchild==NULL)/*前驱线索*/
{p->ltag=1;
p->lchild=pre;
}
if(p->lchild==NULL)/*后续线索*/
{p->rtag=1;
p->rchild=pre;
}
pre=p;
InThreading(p->rchild);/*右子树线索化*/
}
}
以中序为例，利用在中序线索二叉树上需找后续结点和前驱结点的算法，就可以遍历到二叉树的所有结点，即先找到按某序遍历的一个结点，然后再一次查询其后续；或先找到按某序遍历的最后一个结点，然后再一次查询其前驱。这样，既不用栈也不用递归就可以访问但二叉树的所有结点。
BiThrTree Search (BiThrTree head)
{/*head为头结点*/
BiThrNodeType *p;
p=head->lchild;/*指向跟结点*/
while(p->ltag==0&&p!=head)p=p->lchild;/*找中序遍历的第一个结点*/
while(p!=head)
{p=InPostNode(p);
Visit(p);
}
}
