线索二叉树

遍历二叉树以一定的规则将二叉树中的结点排列成一个线性序列，每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。
利用空链域存放指向其直接前驱或后继的指针。
若无左子树，令lchild指向其前驱结点；若无右子树，令rchild指向其后继结点。还需增加两个标志域表明当前指针域所指对象是指左（右）子结点还是直接前驱（后继）。

typedef struct ThreadNode
{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode, *ThreadTree;

对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

中序建立线索二叉树.PNG

pre标记的是刚刚访问过的结点

void InThread(ThreadTree &p, ThreadTree &pre)
{
    //注意这里传的是引用
    if(p!=NULL){
        InThread(p->Thread,pre);
        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){
        InThread(T, pre);
        pre->rchild=NULL;   //处理遍历的最后一个结点，因为递归传的是引用，
                            //最后退出上一句的时候pre指向指向最后一个元素
       pre->rtag=1;
    }
}

带头结点线索树.PNG

ThreadNode *Firstnode(ThreadNode *p){
    while(p->ltag==0) p=p->lchild;
    return p;
}

中序线索二叉树中结点p在中序序列下的后继结点

ThreadNode *Nextnode(ThreadNode *p){
    if(p->rtag==0)  return FirstNode(p);
    else return p->rchild;
}

不含头结点的中序线索二叉树的中序遍历

void InOrder(ThreadNode *T){
    for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
        visit(p);
}