1 #include <stdio.h>
2 #include <string.h>
3 #include <iostream>
4 #include <stack>
5 using namespace std;
6
7 typedef struct TreeNode
8 {
9 int data;
10 struct TreeNode * left;
11 struct TreeNode * right;
12 }TreeNode;
13
14 TreeNode node[11],node1[3];
15 TreeNode *root1=&node[0],*root2=&node1[0];
16
17 int compare(TreeNode *p1,TreeNode *p2)
18 {
19 if(p2==NULL)return 1;
20 else if(p1==NULL)return 0;
21 if(p1->data!=p2->data)
22 {
23 return compare(p1->left,root2)||compare(p1->right,root2);
24 }
25 else
26 {
27 return compare(p1->left,p2->left)&&compare(p1->right,p2->right);
28 }
29 }
30
31 void preorder(TreeNode *p)
32 {
33 if(p!=NULL)
34 {
35 printf("%d ",p->data);
36 preorder(p->left);
37 preorder(p->right);
38 }
39 }
40
41 void inorder(TreeNode *p)
42 {
43 if(p!=NULL)
44 {
45 inorder(p->left);
46 printf("%d ",p->data);
47 inorder(p->right);
48 }
49 }
50
51 void postorder(TreeNode *p)
52 {
53 if(p!=NULL)
54 {
55 postorder(p->left);
56 postorder(p->right);
57 printf("%d ",p->data);
58 }
59 }
60
61 void print_data(TreeNode *p)
62 {
63 printf("%d ",p->data);
64 }
65
66 void println()
67 {
68 printf("\n");
69 }
70
71 void preorder_loop(TreeNode *p)
72 {
73 stack<TreeNode*> s;
74 while(p!=NULL)
75 {
76 print_data(p);
77 s.push(p);
78 p = p->left;
79 }
80 while(!s.empty())
81 {
82 TreeNode * temp = s.top();
83 s.pop();
84 temp = temp->right;
85 while(temp!=NULL)
86 {
87 print_data(temp);
88 s.push(temp);
89 temp = temp->left;
90 }
91 }
92 }
93
94 void inorder_loop(TreeNode *p)
95 {
96 stack<TreeNode*> s;
97 while(p!=NULL)
98 {
99 s.push(p);
100 p = p->left;
101 }
102 while(!s.empty())
103 {
104 TreeNode * temp = s.top();
105 s.pop();
106 print_data(temp);
107 temp = temp->right;
108 while(temp!=NULL)
109 {
110 s.push(temp);
111 temp = temp->left;
112 }
113 }
114 }
115
116 TreeNode* visited[100];
117 int vnum=0;
118
119 int find(TreeNode *temp)
120 {
121 int i;
122 for(i=0;i<vnum;i++)
123 {
124 if(visited[i]==temp)return 1;
125 }
126 visited[vnum++] = temp;
127 return 0;
128 }
129
130 void postorder_loop(TreeNode *p)
131 {
132 stack<TreeNode*> s;
133 while(p!=NULL)
134 {
135 s.push(p);
136 p = p->left;
137 }
138 while(!s.empty())
139 {
140 TreeNode * temp = s.top();
141 if(temp->right==NULL||find(temp))
142 {
143 print_data(temp);
144 s.pop();
145 }
146 else
147 {
148 temp = temp->right;
149 while(temp!=NULL)
150 {
151 s.push(temp);
152 temp = temp->left;
153 }
154 }
155 }
156 }
157
158 TreeNode *pathp[100],*pathq[100];
159 int pnum=0,qnum=0;
160 int f=0;
161 void dfs(TreeNode *root,TreeNode *p,TreeNode**path,int *num)
162 {
163 if(f)return;
164 if(root==p)
165 {
166 f = 1;
167 return;
168 }
169 if(root->left!=NULL&&!f)
170 {
171 path[(*num)++] = root->left;
172 dfs(root->left,p,path,num);
173 if(!f)(*num)--;
174 }
175 if(root->right!=NULL&&!f)
176 {
177 path[(*num)++] = root->right;
178 dfs(root->right,p,path,num);
179 if(!f)(*num)--;
180 }
181 }
182
183 TreeNode * find_last_same_node()
184 {
185 int i=0;
186 while(pathp[i]==pathq[i])i++;
187 return pathp[i-1];
188 }
189
190 TreeNode * find_first_father(TreeNode *root,TreeNode * p,TreeNode *q)
191 {
192 dfs(root,p,pathp,&pnum);
193 f = 0;
194 dfs(root,q,pathq,&qnum);
195 TreeNode * first_father = find_last_same_node();
196 return first_father;
197 // printf("%d\n",first_father->data);
198 }
199
200 int main()
201 {
202
203 node[0].data = 0;
204 node[0].left = &node[1];
205 node[0].right = &node[2];
206 node[1].data = 1;
207 node[1].left = &node[3];
208 node[1].right = &node[4];
209 node[2].data = 2;
210 node[2].left = &node[5];
211 node[2].right = &node[6];
212 node[3].data = 3;
213 node[3].left = &node[7];
214 node[3].right = NULL;
215 node[4].data = 4;
216 node[4].left = &node[8];
217 node[4].right = NULL;
218 node[5].data = 2;
219 node[5].left = &node[9];
220 node[5].right = &node[10];
221 node[6].data = 6;
222 node[6].left = NULL;
223 node[6].right = NULL;
224 node[7].data = 7;
225 node[7].left = NULL;
226 node[7].right = NULL;
227 node[8].data = 8;
228 node[8].left = NULL;
229 node[8].right = NULL;
230 node[9].data = 5;
231 node[9].left = NULL;
232 node[9].right = NULL;
233 node[10].data = 9;
234 node[10].left = NULL;
235 node[10].right = NULL;
236
237 node1[0].data = 2;
238 node1[0].left = &node1[1];
239 node1[0].right = &node1[2];
240 node1[1].data = 2;
241 node1[1].left = NULL;
242 node1[1].right = NULL;
243 node1[2].data = 6;
244 node1[2].left = NULL;
245 node1[2].right = NULL;
246
247 preorder(root1);
248 // printf("\n");
249 // preorder(root2);
250 // printf("\n");
251
252 // printf("%d\n",compare(root1,root2));
253 println();
254 preorder_loop(root1);
255 println();
256 println();
257 inorder(root1);
258 println();
259 inorder_loop(root1);
260 println();
261 println();
262 postorder(root1);
263 println();
264 postorder_loop(root1);
265 println();
266 println();
267 TreeNode * first_father = find_first_father(root1,&node[6],&node[9]);
268 printf("%d\n",first_father->data);
269 return 0;
270 }
View Code
