#include <iostream>
          using namespace std;
    
    #define visit(t) cout<<t->data
    #define N 100
    typedef char elemtype;
    
    typedef struct Bnode
    {
            elemtype data;
            struct Bnode *lchild;
            struct Bnode *rchild;
    }Bnode;
    
    void createTree(Bnode**);   //create a tree 
    void preorder(Bnode*);   //preoreder using recursion
    void midorder(Bnode*);   // midordern using recursion
    void postorder(Bnode*);  // postorder using recursion
    void _preorder(Bnode*);  //preorder using stack
    void _midorder(Bnode*);  // midorder using stack
    void _postorder(Bnode*); // postorder using stack
    bool findBnode(Bnode*, elemtype, Bnode* &); //find node
    bool findParentNode(Bnode*, Bnode*, Bnode* &);  
    bool delBnode(Bnode* &, elemtype);  // delete node
    void delTree(Bnode*);    //delete this tree
    
    int main()
    {
        Bnode *tree;
        cout << "intput: " << endl;
        createTree(&tree);
        cout << "output: " << endl;
        
        cout << "preorder using recursion :" << endl;
        preorder(tree);
        cout << endl;
        
        cout << "preorder using stack:" << endl;
        _preorder(tree);
        cout << endl;
        
        cout << "midorder using recursion :" << endl;
        midorder(tree);
        cout << endl;
        
        cout << "midorder using stack :" << endl;
        _midorder(tree);
        cout << endl;
        
        cout << "postorder using recursion :" << endl;
        postorder(tree);
        cout << endl;
        
        cout << "postorder using stack :" << endl;
        _postorder(tree);
        cout << endl;
        
        Bnode *p;
        if(findBnode(tree,'C',p))
            cout << "find result is " << p->data << endl;
        else 
            cout << "can't find" << endl;
        
        Bnode* parent;    
        findParentNode(tree,p,parent);
        cout <<"parent is "<< parent->data << endl;
        
        
        delBnode(tree,'A');
        preorder(tree);
        cout << endl;
        
        delTree(tree);
        system("pause");
        return 0;
    }   
    
    void createTree(Bnode** T)         //create a tree 
    {
         char ch;
         if( (ch=getchar()) == ' ' )
              *T = 0;
          else{
               (*T) = new Bnode;
               (*T)->data = ch;
               createTree(&(*T)->lchild);
               createTree(&(*T)->rchild);
          }
    }
    
    void preorder(Bnode* root)   //preoreder using recursion
    {
         Bnode *p = root;
         if(p)
         {
              visit(p);
              preorder(p->lchild);
              preorder(p->rchild);
         }
    }
    
    void midorder(Bnode* root)  // midordern using recursion
    {
         Bnode *p = root;
         if(p)
         {
              midorder(p->lchild);
              visit(p);
              midorder(p->rchild);
         }
    }
    
    void postorder(Bnode* root)  // postorder using recursion
    {
         Bnode *p = root;
         if(p)
         {
              postorder(p->lchild);
              postorder(p->rchild);
              visit(p);
         }
    }
    
    void _preorder(Bnode* root)  //preorder using stack
    {
         Bnode *p = root;
         Bnode *stack[N];
         int top = 0;
         stack[top++] = p;
         while(top)
         {
              p = stack[--top];
              if(p){
                   visit(p);
                   if(p->rchild)
                        stack[top++] = p->rchild;
                   if(p->lchild)
                        stack[top++] = p->lchild;
              }
         } 
    }
    void _midorder(Bnode* root)  // midorder using stack
    {
         Bnode *stack[N];
         Bnode *p = root;
         int top = 0;
        do{
             while(p)
             {
                  stack[top++] = p;
                  p = p->lchild;
             }
             if(top)
             {
                 p = stack[--top];
                 visit(p);
                 p = p->rchild;
             }
        }while(top!=0||p!=0);
                     
    }
    
    void _postorder(Bnode* root)  // postorder using stack
    {
        Bnode *p, *parent;
        Bnode *stack[N];
        int top = 0;
        p = root;
        if(p==0) return ;
        stack[top++] = p;
        do{
             if(p->lchild != 0)
             {
                  p = p->lchild;
                  stack[top++] = p;
             }
             else if(p->rchild != 0)
             {
                  p = p->rchild;
                  stack[top++] = p;
             }
             else{
                  
                  while(1)
                  {
                       p = stack[--top];
                       visit(p);
                       if(!top) return ;
                       parent = stack[top-1];
                       if(parent->rchild!=0&&p!=parent->rchild)
                       {
                            p = parent->rchild;
                            stack[top++] = p;
                            break;
                        }
                  }
             }
        }while(top);
        
    }
    
    bool findBnode(Bnode* root,elemtype nodeData, Bnode* &p) 
    {
         p = root;
         Bnode *stack[N];
         int top = 0;
         stack[top++] = p;
         while(top)
         {
              p = stack[--top];
              if(p)
              {
                   if(nodeData == p->data)
                         return true;
                   else{
                         if(p->rchild != 0)
                              stack[top++] = p->rchild;
                         if(p->lchild !=0)
                              stack[top++] = p->lchild;
                   }   
               }
         }
         if(!top)
              return false;
    }     
    bool findParentNode(Bnode* root, Bnode* p, Bnode* &parent)  
    {
         if(p == root)
         {
              parent = 0;
              return false;
         }
         parent = root;
         Bnode *queue[N];
         int front,rear;
         front = rear = 0;
         queue[rear++] = parent;
         while(front < rear)
         {
            parent = queue[front++];
            if(parent->lchild != 0)
            {
                if(parent->lchild == p)
                     return true;
                else
                     queue[rear++] = parent->lchild;
            }
            if(parent->rchild != 0)
            {
                if(parent->rchild == p)
                     return true;
                else
                     queue[rear++] = parent->rchild;
            }
                
         }
    }
    
    bool delBnode(Bnode* &root, elemtype nodeData)  // delete node
    {
         Bnode *p,*parent;
         Bnode *temp;
         if(!findBnode(root,nodeData,p))  
              return false;
          findParentNode(root,p,parent);  // find the parent node
          if(p->lchild == 0)     
          {
                if(parent == 0)     // if this node is root
                     root = p->rchild;                
                else if(p == parent ->lchild)   
                     parent->lchild = p->rchild;
                else if(p == parent ->rchild)      
                     parent->rchild = p->rchild;
          }
          else{           
               temp = p->lchild;
               
               while(temp->rchild)
                    temp = temp->rchild;
               
               temp->rchild = p->rchild;
               if(parent == 0)        
                    root = p->lchild;
               else if(p == parent ->lchild)  
                    parent->lchild = p->lchild;
               else if(p == parent ->rchild)     
                    parent->rchild = p->lchild;
          }                     
    }
    void delTree(Bnode *root)  //delete this tree
    {
         Bnode *p = root;
         if(p)
         {
              delTree(p->lchild);
              delTree(p->rchild);
              delete p;
         }
    }