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("
");
107 findnode(T,'3');
108 preorder(T);
109 printf("
");
110 postorder(T);
111 }
