The former sequence traversal

void PreOrder(BiNode *bt){ BiNode * p=bt; stack<BiNode*> s; while(p! =NULL||! s.empty()){ while(p! =NULL){ cout<<p->data<<" "; s.push(p); p=p->lchild; } if(! s.empty()){ p=s.top(); s.pop(); p=p->rchild; }}}Copy the code

In the sequence traversal

void InOrder(BiNode *bt){ stack<BiNode*> s; BiNode *p=bt; while(p! =NULL||! s.empty()){ while(p! =NULL){ s.push(p); p=p->lchild; } if(! s.empty()){ p=s.top(); s.pop(); cout<<p->data<<" "; p=p->rchild; }}}Copy the code

After the sequence traversal

void PostOrder(BiNode* bt){
    BiNode *p=bt;
    element elem;
    stack<element> s;
    while(p!=NULL||!s.empty()){
        if(p!=NULL){
            elem.ptr=p;
            elem.flag=1;
            s.push(elem);
            p=p->lchild;
        }
        else{
            elem=s.top();
            s.pop();
            p=elem.ptr;
            if(elem.flag==1){
                elem.flag=2;
                s.push(elem);
                p=p->rchild;
            }
            else{
                cout<<p->data<<" ";
                p=NULL;
            }
        }
    }
}
Copy the code

The complete code

#include<iostream> #include<stack> using namespace std; struct BiNode{ char data; BiNode *lchild,*rchild; }; struct element{ BiNode *ptr; int flag; }; void create(BiNode* &bt){ char ch; cin>>ch; if(ch=='#') bt=NULL; else{ bt=new BiNode; bt->data=ch; create(bt->lchild); create(bt->rchild); } } void PreOrder(BiNode *bt){ BiNode * p=bt; stack<BiNode*> s; while(p! =NULL||! s.empty()){ while(p! =NULL){ cout<<p->data<<" "; s.push(p); p=p->lchild; } if(! s.empty()){ p=s.top(); s.pop(); p=p->rchild; } } } void InOrder(BiNode *bt){ stack<BiNode*> s; BiNode *p=bt; while(p! =NULL||! s.empty()){ while(p! =NULL){ s.push(p); p=p->lchild; } if(! s.empty()){ p=s.top(); s.pop(); cout<<p->data<<" "; p=p->rchild; } } } void PostOrder(BiNode* bt){ BiNode *p=bt; element elem; stack<element> s; while(p! =NULL||! s.empty()){ if(p! =NULL){ elem.ptr=p; elem.flag=1; s.push(elem); p=p->lchild; } else{ elem=s.top(); s.pop(); p=elem.ptr; if(elem.flag==1){ elem.flag=2; s.push(elem); p=p->rchild; } else{ cout<<p->data<<" "; p=NULL; } } } } int main(){ BiNode *root; create(root); PreOrder(root); cout<<endl; InOrder(root); cout<<endl; PostOrder(root); return 0; }Copy the code

Input:

AB#D##C##

Output:

A B D C

B D A C

D B C A