[二叉树算法]线索二叉树算法总结

//线索二叉树
//中序遍历线索二叉树 19
//tag为0 指示有孩子 tag为1说明有前驱或后继
BTNode *firstNode(BTNode *t){
    while(t->ltag==0){
        t=t->lchild;
    }
    return t;
}
BTNode* NextNode(BTNode *p){
    if(p->rtag==0)
        return firstNode(p->rchild);
    else{
        return p->rchild;
    }
}
void InOrder(BTNode *T){
    for(BTNode *p=firstNode(T);p!=null;p=NextNode(T)){
        visit(p);
    }
}

//中序逆向遍历中序线索二叉树
BTNode lastNode(BTNode *p){
    while(t->rtag==0){
        t=t->rchild;
    }
    return t;
}
BTNode PreNode(BTNode *p){
    if(p->ltag==0){
        return lastNode(p->lchild);
    }else{
        return p->lchild;
    }
}
void ReInOrder(BTNode *T){
    for(BTNode *p=lastNode(T);p!=null;p=PreNode(T)){
        visit(p);
    }
}

//中序线索二叉树 找指定结点在后序的前驱结点
//在后序序列中，若结点p有右孩子，则右子女是其前驱。
//若没有右子女有左孩子，则左孩子是其前驱。
//若都没有中序左线索指向某祖先f
//若f有左孩子，则左子女是结点p在后序的前驱
//若f无左孩子，则其前驱找双亲的双亲，一直找到有左子女的
//还有一种情况，p是中序的第一个结点，则p在中序和后序下都无前驱。
BTNode InPostPre(BTNode *T,BTNode *p){
    BTNode q;
    if(p->rtag==0){//有右孩子
        q=p->rchild;
    }else if(p->ltag==0){//有左孩子
        q=p->lchild;
    }else if(p->lchild==null){
        q=null;
    }else{
        while(p->ltag==1 && p->lchild!=null){
            p=p->lchild;
        }
        if(p->ltag==0){
            q=p->lchild;
        }else{
            q=null;
        }
    }
    return q;
}