데이터 구조 - 후 순서 단서 화 이 진 트 리

#include 
using namespace std;
typedef enum PointerTag {Link,Thread};    //Link==0,Thread==1;  
typedef struct treenode
{
    struct treenode *left;
    char            data;
    struct treenode *right;
    PointerTag        Ltag,Rtag;    //    
}Treenode,* Treep;
Treep pre;                   /*    ，         */ 
//      
void init_tree(Treep &root)
{
    root=NULL;
    cout<data=ch;
        rt->Ltag=Link;
        rt->Rtag=Link;
        creat_tree(rt->left);        //     
        creat_tree(rt->right);    //         
    }
}
//       
void pre_order(Treep &rt)
{
    if(rt!=NULL)
    {
        cout<data<left);
        pre_order(rt->right);
    }
}

//        
void backThreading(Treep &p)
{
    if(p)
    {
        backThreading(p->left);
        backThreading(p->right);
        
        if(!p->left)
        {
            p->Ltag=Thread;
            p->left=pre;        //    
        }
        if(!pre->right)
        {
            pre->Rtag=Thread;
            pre->right=p;        //    
        }

        pre=p;
    }
}//InThreading
Treep backorderThreading(Treep &rt)
{
    Treep thrt;
    if(    !(thrt = (Treep) malloc (sizeof(Treenode) ) ) )
        exit(1);
    thrt->Ltag=Link;
    thrt->Rtag=Thread;    //    
    thrt->right=thrt;    //     
    if(!rt)
        thrt->left=thrt;    //     ，      
    else
    {
        thrt->left=rt;
        pre=thrt;

        backThreading(rt);        //           

        thrt->right=pre;        //        
    }
    return thrt;
}

Treep parent(Treep &thrt,Treep    &p)
{
    Treep    temp;
    temp=thrt;
    if(temp->left==p)
        return temp;    //       
    else
    {    
        temp=temp->left;
        while( temp->left!=p && temp->right!=p )
        {
            if(Link==temp->Rtag)
                temp=temp->right;    //        ，    
            else
                temp=temp->left;    //         ，      ，     ，   ，     
        }
        return temp;
    }
}
//         
void backorderTraver(Treep &thrt)
{
    Treep    p;
    Treep    par;
    p=thrt->left;
    while(1)
    {
        while(Link==p->Ltag)
            p=p->left;
        if(Link==p->Rtag)
            p=p->right;
        else
            break;        //p           
    }
    while(p!=thrt)
    {
        cout<data<right || Thread==par->Rtag)    //2. p       ，        ，      
            p=par;
        else
        {
            while(par->Rtag==Link)        //3. p        ，                         。
            {
                par=par->right;
                while(par->Ltag==Link)
                {
                    par=par->left;
                }
            }
            p=par;
        }
    }
}

int main()
{
    Treep root;
    init_tree(root);        //    
    cout<