1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef char ElemType; 
  4 
  5 typedef struct BiNode{
  6     ElemType data;
  7     BiNode* lchild;
  8     BiNode* rchild;     
  9     BiNode(ElemType data, BiNode* lchild, BiNode* rchild) {
 10         this->data = data;
 11         this->lchild = lchild;
 12         this->rchild = rchild;
 13     }   
 14 }*BiTree;
 15 
 16 stack<BiTree>s;
 17 
 18 void postorder(BiTree T){
 19     BiTree p=T;
 20     BiTree r=NULL;
 21     while(p||!s.empty()){
 22         if(p){
 23             s.push(p);
 24             p=p->lchild;
 25         }
 26         else{
 27             p=s.top();
 28             if(p->rchild&&p->rchild!=r)p=p->rchild;
 29             else{
 30                 s.pop();
 31                 printf("%c",p->data);
 32                 r=p;
 33                 p=NULL;
 34             }
 35         }
 36     }
 37 
 38 }
 39 
 40 void preorder(BiTree T){
 41     while(T||!s.empty()){
 42         //if(s.empty())printf("q");
 43         if(T){
 44             printf("%c",T->data);
 45             s.push(T);
 46             T=T->lchild;
 47         }
 48         else{
 49             T=s.top();
 50             s.pop();
 51             T=T->rchild;
 52         }
 53         
 54 
 55     }
 56 }
 57 
 58 void delnode(BiTree &p){
 59     if(!p->lchild)p=p->rchild;
 60     else if(!p->rchild)p=p->lchild;
 61     else{
 62         BiTree t=p->rchild;
 63         BiTree q=p;
 64         while(t->lchild){
 65             q=t;
 66             t=t->lchild;
 67         }
 68         p->data=t->data;
 69         if(q==p){
 70             p->rchild=t->rchild;
 71             //free(t);
 72         }
 73         else{
 74             q->lchild=t->rchild;
 75             t=NULL;
 76         }
 77     }
 78 }
 79 
 80 BiTree findnode(BiTree &T,char x){
 81     if(!T||T->data==x){
 82         delnode(T);
 83         return T;
 84     }
 85     if(x<T->data)return findnode(T->lchild,x);
 86     return findnode(T->rchild,x);
 87 }
 88 
 89 int main(){
 90     /*BiNode* v4 = new BiNode('4', NULL, NULL);
 91     BiNode* v6 = new BiNode('6', NULL, NULL);
 92     BiNode* v5 = new BiNode('5', v4, v6);
 93     BiNode* v1 = new BiNode('1', NULL, NULL);
 94     BiNode* v3 = new BiNode('3', v1, v5);
 95     BiNode* v7 = new BiNode('7', v3, NULL);*/
 96     BiNode* v7 = new BiNode('7', NULL, NULL);
 97     BiNode* v1 = new BiNode('1', NULL, NULL);
 98     BiNode* v3 = new BiNode('3', NULL, NULL);
 99     BiNode* v2 = new BiNode('2', v1, v3);
100     BiNode* v5 = new BiNode('5', NULL, NULL);
101     BiNode* v6 = new BiNode('6', v5, v7);
102     BiNode* v4 = new BiNode('4', v2, v6);
103     //BiNode* T = v4;*/
104     BiTree T=v7;
105     preorder(T);
106     printf("\n");
107     findnode(T,'3');
108     preorder(T);
109     printf("\n");
110     postorder(T);
111 }