數據結構 二叉樹 索引鏈表 及其索引話 輸出

[cpp] 
#include <iostream> 
#include <string.h> 
using namespace std; 
class tree 
{ 
public: 
    char c; 
    tree *lchild,*rchild; 
    int ltag,rtag; 
}; 
char c; 
tree *pre; 
int main() 
{ 
    void build(tree * &p); 
    void inthread(tree* p,tree* &list); 
    void Inorder(tree* p,tree* list); 
    tree *head,*list; 
    build(head); 
    inthread(head,list); 
    Inorder(head,list); 
    cout<<endl; 
    return 0; 
} 
void build(tree* &p) 
{ 
    cin>>c; 
    if(c=='$') 
    { 
        p=NULL; 
    }else 
    { 
        p=new(tree); 
        p->c=c; 
        p->ltag=0; 
        p->rtag=0; 
        build(p->lchild); 
        build(p->rchild); 
    } 
} 
void inorderthread(tree *p) 
{ 
    if(p) 
    { 
        inorderthread(p->lchild); 
        if(!p->lchild) 
        { 
            p->ltag=1; p->lchild=pre; 
        } 
        if(!pre->rchild) 
        { 
            pre->rtag=1; 
            pre->rchild=p; 
        } 
        pre=p; 
        inorderthread(p->rchild); 
    } 
} 
void inthread(tree* p,tree* &list) 
{ 
    list=new(tree); 
    list->ltag=0; list->rtag=1; 
    list->rchild=list; 
    if(p==NULL) 
    { 
        list->lchild=list; 
    }else 
    { 
        list->lchild=p; 
        pre=list; 
        inorderthread(p); 
        pre->rchild=list; pre->rtag=1; 
        list->rchild=pre; 
    } 
} 
void Inorder(tree* p,tree *list) 
{ 
    while(p!=list) 
    { 
        while(p->ltag==0) 
        { 
            p=p->lchild; 
        } 
        cout<<p->c; 
        while(p->rtag&&p->rchild!=list) 
        { 
            p=p->rchild; 
            cout<<p->c; 
        } 
        p=p->rchild; 
    } 
}