后序线索二叉树中，结点的后继：

　　如果结点的双亲有右孩子，则结点的后继为双亲的右子树中第一个被访问的结点

　　如果结点的双亲没有右孩子，则结点的后继为双亲

　　如果结点为双亲的右孩子，则结点的后继为双亲

因为找到后序遍历中，找到结点的后继需要知道节点的双亲，所以可以用三叉链表(trifurcate linked list)来存储结点

 

1.后序线索化二叉树（用三叉链表存储结构、有头结点）

void postThreading(TriTree p){
    if(p){
        postThreading(p->lChild);
        postThreading(p->rChild);
        if(!p->lChild){
            p->lTag=1;
            p->lChild=pre;
        }
        if(!pre->rChild){
            pre->rTag=1;
            pre->rChild=p;
        }
        pre=p;
    }
}

bool postThreadTree(TriTree T,TriTree &head){
    if(!(head=new TriTNode)) return false;
    head->lTag=0;
    head->rTag=1;
    head->parent=NULL;
    if(!T){head->lChild=head;head->rChild=head;}
    else{
        pre=head;
        head->lChild=T;
        head->rChild=T;
        T->parent=head;
        postThreading(T);
        if(!pre->rChild){
            pre->rTag=1;
            pre->rChild=head;
        }
    }
    return true;
}

 

2.遍历后序线索二叉树

void postTraverseTriTree(TriTree head){
    TriTree p=head->lChild;
    int tag=0;
    while(p->parent!=NULL){
        while(p->lTag==0&&tag==0){p=p->lChild;}
        if(p->rTag==1){//结点无右孩子，可以顺着线索访问后继 
            visit(p->data);
            while(p->rTag==1&&p->rChild->parent!=NULL){
                p=p->rChild;
                visit(p->data);
            }
        }else if(tag==0){//结点有右孩子且右孩子还没被访问过 
            p=p->rChild;
            continue;
        }else{//结点有右孩子且右孩子已经被访问过 
            visit(p->data);
        }
        //p已经访问掉了，继续找p的后继 
        if(p==p->parent->rChild){p=p->parent;tag=1;}
        else if(p->parent->rTag==0){p=p->parent->rChild;tag=0;}
        else{p=p->parent;tag=1;}
    }
}

 

3.删除后序线索二叉树的内存空间 在删除掉双亲的一个孩子时，将双亲对应的孩子指针置为NULL

void deleteTriTree(TriTree &head){
    TriTree p=head,q=NULL;
    while(p->parent!=NULL){
        while(p->lChild&&p->lTag==0){
            p=p->lChild;
        }
        q=p;
        while(p->rTag==1&&p->rChild->parent!=NULL){
            p=p->rChild;
            if(q->parent->lChild==q) q->parent->lChild=NULL;
            else q->parent->rChild=NULL;
            delete q;
            q=p;
        }
        if(p==p->parent->rChild){
            q=p;
            p=p->parent;
            delete q;
            p->rChild=NULL;
        }else if(p->parent->rChild){
            q=p;
            p=p->parent->rChild;
            q->parent->lChild=NULL;
            delete q;
        }else{
            q=p;
            p=p->parent;
            delete q;
            p->lChild=NULL;
        }
    }
    delete head;
    head=NULL;
}

 

测试代码： 用前序+中序构建二叉树

#include<iostream>
using namespace std;

typedef struct TriTNode{//trifurcate linked list tree node
    struct TriTNode *lChild,*rChild,*parent;
    int data,lTag,rTag;
}TriTNode,*TriTree;

TriTree pre=NULL;

void visit(int val){
    cout<<val<<" ";
}

bool preAndInCreateTriTree(TriTree &p,TriTree parent,int *preOrder,int *inOrder,int length){
    if(length>0){
        if(!(p=new TriTNode)) return false;
        p->data=preOrder[0];
        p->lTag=0;
        p->rTag=0;
        p->parent=parent;
        int i;
        for(i=0;i<length&&inOrder[i]!=preOrder[0];++i);
        preAndInCreateTriTree(p->lChild,p,preOrder+1,inOrder,i);
        preAndInCreateTriTree(p->rChild,p,preOrder+i+1,inOrder+i+1,length-i-1);    
    }else{
        p=NULL;
    }
    return true;
}

int main(){
    int n,*preOrder,*inOrder;
    
    cout<<"Input the number of nodes : ";
    cin>>n;
    
    preOrder=new int[n];
    inOrder=new int[n];
    cout<<"Input the pre-order sequence : "<<endl;
    for(int i=0;i<n;++i) cin>>preOrder[i];
    cout<<"Input the in-order sequence : "<<endl;
    for(int i=0;i<n;++i) cin>>inOrder[i];
    
    TriTree T;
    TriTree head;
    if(!preAndInCreateTriTree(T,NULL,preOrder,inOrder,n)){
        cout<<"Fail to construct this tree"<<endl;
    }else{
        postThreadTree(T,head);
        cout<<"\nPost-traverse:"<<endl;
        postTraverseTriTree(head);    
    }
    deleteTriTree(head);
    T=NULL;
}