线索二叉树

按照某种遍历方式对二叉树进行遍历时，可以把该二叉树中所有节点排列为一个线性序列。

在该序列中，除第一个结点外，每个结点有且仅有一个直接前驱；除最后一个节点外，每个结点都有且仅有一个直接后继。

但是，当以二叉链表作为存储结构时，只能得到结点的左右孩子的信息，而不能直接得到节点在某种遍历序列中的前驱和后继结点，这种信息只有在对二叉树遍历的动态过程中才能得到。

typedef struct ThBiNode{char data;ThBiNode *lchild,*rchild;int ltag,rtag;}ThBiNode,*ThBiTree;线索二叉树的基本操作下面以中序线索二叉树为例。

1.建立中序线索二叉树这也是对二叉树进行线索化的过程，即在遍历过程中，判断当前顶点的左右指针是否为空。

若为空，则改为相应的前驱或者后继的线索。

基本思路：设指针pre始终指向刚刚访问过的结点，即pre是当前访问结点的前驱。

线索化过程中，访问p所指向的结点时，应作如下处理：1）建立p的前驱线索。

若p->lchild为空，则将其左标志域置为1，并令p->lchild指向其中序前驱pre。

2）建立pre的后继线索。

若pre->rchild为空，则将其右标志域置为1，并令pre->rchild指向p。

3）将pre指向p刚刚访问过的结点，即pre=p。

这样，在p访问一个新结点时，pre为其前驱结点。

算法代码如下：void InThreading(ThBiNode *p){if(p){InThreading(p->lchild);if(!p->lchild){p->lchild=pre;p->ltag=1;}if(!pre->rchild){pre->rchild=p;pre->rtag=1;}pre=p;InThreading(p->rchild);}}2.在中序线索二叉树中查找任意结点的前驱结点有两种情况：1）如果该节点的左标志为1，那么其左指针所指向的就是它的前驱结点。

2）如果该节点的左标志为0，即其左指针指向的是它的左孩子，此时它的前驱结点应该是遍历其左子树时最后访问的一个节点，即左子树中最右下的结点，从该节点的左子树出发沿右指针往下查找，当某节点的右标志为1时，它就是要找的前驱结点。

ThBiNode* FindPre(ThBiNode *p){if(p->ltag==1)return p->lchild;else{p=p->lchild;while(p&&!p->rtag)p=p->rchild;return p;}}3.在中序线索二叉树中查找任意结点的后继结点。

两种情况：1）如果该节点的右标志为1，那么其右指针域所指向的结点便是它的后继结点。

2）若果该节点的右标志为0，即其右指针指向它的右孩子，则它的后继结点是遍历其右子树时访问的第一个节点，也就是其右子树最左下结点。

从该节点的右孩子开始，沿着左指针往下查找，当某节点的左标志为1，该节点即为目标节点。

ThBiNode* FindPost(ThBiNode *p){if(p->rtag==1)return p->rchild;else{p=p->rchild;while(p&&!p->ltag)p=p->lchild;return p;}}4.线索二叉树的遍历。

在线索二叉树上进行遍历，只要找到序列中的第一个结点，然后依次找结点后继，直至其后继为空时为止。

若中序遍历线索二叉树，首先应该从根结点出发，沿左指针链不断往下查找，直到左指针为空，到达“最左下”结点，即中序遍历序列的第一个结点，然后反复找结点的中序后继即可。

其实就等于是操作一个双向链表结构。

和双向链表结构一样，在二叉树线索链表上添加一个头结点，并令其lchild域的指针指向二叉线索树的根节点，其rchild域的指针指向中序遍历时访问的最后一个节点。

反之，令二叉线索树的中序序列中的第一个结点的lchild域指针和最后一个节点的rchild域指针均指向头结点。

这样定义的好处是我们既可以从第一个节点起顺后继进行遍历，也可以从最后一个节点起顺前驱进行遍历。

#include<stdio.h>#include<stdlib.h>typedef struct ThBiNode{char data;struct ThBiNode *lchild,*rchild;int ltag,rtag;}ThBiNode,*ThBiTree;void CreateThBiTree(ThBiTree&T){char ch;scanf("%c",&ch);if(ch=='#')T=NULL;else{T=(ThBiTree)malloc(sizeof(ThBiNode)); T->data=ch;T->ltag=0;T->rtag=0;CreateThBiTree(T->lchild);CreateThBiTree(T->rchild);}}//中序建立线索算法ThBiTree pre;void InThreading(ThBiNode *p){if(p){InThreading(p->lchild);if(!p->lchild){p->ltag=1;p->lchild=pre;}if(!pre->rchild){pre->rtag=1;pre->rchild=p;}pre=p;InThreading(p->rchild); }}void InOrderThreading(ThBiTree&Thrt,ThBiTree T){//T为指向二叉树的根结点的指针，由此二叉链表建立二叉树的中序线索链表，Thrt指向线索链表中的头结点Thrt=(ThBiTree)malloc(sizeof(ThBiNode));if(!Thrt) //存储分配失败exit(0);Thrt->ltag=0;Thrt->rtag=1; //建头结点Thrt->rchild=Thrt; //右指针回指if(!T) //若二叉树为空，则左指针回指Thrt->lchild=Thrt;else{Thrt->lchild=T;pre=Thrt;InThreading(T); //中序遍历线索化pre->rchild=Thrt;pre->rtag=1;//对最后一个节点进行线索化Thrt->rchild=pre; //建非空二叉树的头结点的右线索 }}ThBiNode* FindPre(ThBiNode *p){if(p->ltag==1)return p->lchild;else{p=p->lchild;while(p&&!p->rtag)p=p->rchild;return p;}}ThBiNode* FindPost(ThBiNode *p){if(p->rtag==1)return p->rchild;else{p=p->rchild;while(p&&!p->ltag)p=p->lchild;return p;}}/*Thrt指向头结点，头结点左链lchild指向根结点，头结点右链rchild 指向中序遍历的最后一个节点*/void InOrderTraverse(ThBiTreeThrt){ThBiTree p;p=Thrt->lchild;while(p!=Thrt){while(p->ltag==0)p=p->lchild;printf("%3c",p->data);while(p->rtag==1&&p->rchild!=Thrt){p=p->rchild;printf("%3c",p->data);}p=p->rchild;}}int main(){ThBiTreeT,H,p;printf("请按前序输入二叉树如：ABDH##I##EJ###CF##G##\n"); CreateThBiTree(T);InOrderThreading(H,T);printf("中序遍历输出线索二叉树：\n");InOrderTraverse(H);printf("\n");printf("%3c\n",FindPost(T)->data);return0;}。