目的:加快查找结点的前驱和后继的速度
typedef struct Node{
int data;
struct Node *lchild,*rchild;
int ltag,rtag;
}Node,*ThreadTree;
通过中序遍历建立线索二叉树
void InThread(ThreadTree &p,ThreadTree &pre)
{
if(!p=NULL)
{
InThread(p->lchild); //递归,线索化左子树
if(p->lchild == NULL) // 当前结点左子树空
{
p->lchild = pre; //建立前驱线索
p->ltag=1;
}
if(pre!=NULL && pre->rchild == NULL)//前驱非空且右子树空
{
pre->rchild = p;//建立前驱结点的后继线索
pre->rtag=1;
}
pre = p;
InThread(p->rchild,pre);//递归,线索化右子树
}
}
//主过程
void CreateInThread(ThreadTree T)
{
ThreadTree pre = NULL;
if(T != NULL)//非空二叉树
{
InThead(T,pre);//线索化
pre->rchild = NULL; //处理遍历的最后一个结点
pre->rtag=1;
}
}