1 #include <iostream>
2 #include <cstring>
3 #include <stack>
4 #include <queue>
5 #include <cmath>
6 #include <exception>
7 #include <stdexcept>
8
9 using namespace std;
10
11 typedef
struct Node {
12 int key;
13 struct Node *
left;
14 struct Node *
right;
15 }Node;
16
17
18 void PreOrder(Node*
head) {
19 if(head) {
20 cout<<head->key<<
"\t";
21 PreOrder(head->
left);
22 PreOrder(head->
right);
23 }
24 }
25
26 void InOrder(Node*
head) {
27 if(head) {
28 InOrder(head->
left);
29 cout<<head->key<<
"\t";
30 InOrder(head->
right);
31 }
32 }
33
34 void PostOrder(Node*
head) {
35 if(head) {
36 PostOrder(head->
left);
37 PostOrder(head->
right);
38 cout<<head->key<<
"\t";
39 }
40 }
41
42 void IterInOrder(Node*
head) {
43 stack<Node*>
ss;
44 Node* headCp =
head;
45 for(;;) {
46 for(;headCp;headCp=headCp->
left) {
47 ss.push(headCp);
48 }
49 if(ss.size()!=
0) {
// key point, if stack is of no item inside, top() will cause trouble.
50 headCp =
ss.top();
51 ss.pop();
52 }
53 if(!
headCp) {
54 break;
55 }
56 cout<<headCp->key<<
"\t";
57 headCp = headCp->
right;
58 }
59 }
60
61 void LevelOrder(Node*
head) {
62 queue<Node*>
que;
63 if(!
head) {
64 return;
65 }
66 que.push(head);
67 for(;;) {
68 if(que.size()==
0) {
69 break;
70 }
71 head =
que.front();
72 que.pop();
73 if(head) {
74 cout<<head->key<<
"\t";
75 if(head->
left) {
76 que.push(head->
left);
77 }
78 if(head->
right) {
79 que.push(head->
right);
80 }
81 }
82 }
83 }
84
85 Node* BuildTree(
int* startPreorder,
int* endPreorder,
int* startInorder,
int*
endInorder);
86
87 Node* ConstructNewTree(
int* PreOrderArr,
int* InOrderArr,
int length) {
88 if(PreOrderArr == NULL || InOrderArr == NULL || length ==
0) {
89 return NULL;
90 }
else {
91 int* startPreorder =
PreOrderArr;
92 int* endPreorder = PreOrderArr+length-
1;
93 int* startInorder =
InOrderArr;
94 int* endInorder = InOrderArr+length-
1;
95 return BuildTree(startPreorder,endPreorder,startInorder,endInorder);
96 }
97 }
98
99 Node* BuildTree(
int* startPreorder,
int* endPreorder,
int* startInorder,
int*
endInorder) {
100 int rootValue = -
1;
101 if(startPreorder == NULL || endPreorder==NULL || startInorder==NULL || endInorder==
NULL) {
102 return NULL;
103 }
else {
104 rootValue = *
startPreorder;
105 }
106 Node* root =
new Node();
107 root->key =
rootValue;
108 root->left =
NULL;
109 root->right =
NULL;
110
111 if(startPreorder==
endPreorder) {
112 if(startInorder==endInorder && *startPreorder == *
startInorder) {
113 return root;
114 }
else {
115 throw exception();
116 }
117 }
118
119 int* rootInorder =
startInorder;
120 while(rootInorder<=endInorder && *rootInorder!=
rootValue) {
121 rootInorder++
;
122 }
123 if(*rootInorder!=
rootValue) {
124 throw exception();
125 }
126 int leftLen = rootInorder-
startInorder;
127 int righLen = endInorder-
rootInorder;
128 int* leftPreorderEnd = startPreorder+
leftLen;
129 if(leftLen>
0) {
130 root->left = BuildTree(startPreorder+
1,leftPreorderEnd,startInorder,rootInorder-
1);
131 }
132 if(righLen>
0) {
133 root->right = BuildTree(leftPreorderEnd+
1,endPreorder,rootInorder+
1,endInorder);
134 }
135 return root;
136 }
137
138
139 int main(
int argc,
char*
argv[]) {
140 Node node1,node2,node3,node4,node5,node6,node7,node8;
141
142 node1.key =
1;
143 node1.left = &
node2;
144 node1.right = &
node3;
145
146 node2.key =
2;
147 node2.left = &
node4;
148 node2.right =
NULL;
149
150 node3.key =
3;
151 node3.left = &
node5;
152 node3.right = &
node6;
153
154 node4.key =
4;
155 node4.left =
NULL;
156 node4.right = &
node7;
157
158 node5.key =
5;
159 node5.left =
NULL;
160 node5.right =
NULL;
161
162 node6.key =
6;
163 node6.left = &
node8;
164 node6.right =
NULL;
165
166 node7.key =
7;
167 node7.left =
NULL;
168 node7.right =
NULL;
169
170 node8.key =
8;
171 node8.left =
NULL;
172 node8.right =
NULL;
173
174 cout<<
"preorder:"<<
endl;
175 PreOrder(&
node1);
176 cout<<
endl;
177
178 cout<<
"inorder:"<<
endl;
179 InOrder(&
node1);
180 cout<<
endl;
181
182
183 /*
184 cout<<"PreOrder:\n";
185 PreOrder(&node1);
186 cout<<endl;
187
188 cout<<"recursive InOrder:\n";
189 InOrder(&node1);
190 cout<<endl;
191
192 cout<<"loop InOrder:\n";
193 IterInOrder(&node1);
194 cout<<endl;
195
196 cout<<"PostOrder:\n";
197 PostOrder(&node1);
198 cout<<endl;
199
200 cout<<"Level Order:\n";
201 LevelOrder(&node1);
202 cout<<endl;
203 */
204
205 cout<<
"start building the tree ..."<<
endl;
206 int PreorderArr[] = {
1,
2,
4,
7,
3,
5,
6,
8};
207 int InorderArr[] = {
4,
7,
2,
1,
5,
3,
8,
6};
208 Node* root = ConstructNewTree(PreorderArr,InorderArr,
sizeof(PreorderArr)/
sizeof(
int));
209 cout<<
"build done."<<
endl;
210
211 cout<<
"preorder:"<<
endl;
212 PreOrder(root);
213 cout<<
endl;
214 cout<<
"inorder:"<<
endl;
215 InOrder(root);
216 cout<<
endl;
217 cout<<
"postorder:"<<
endl;
218 PostOrder(root);
219 cout<<
endl;
220
221 return 0;
222 }
转载于:https://www.cnblogs.com/warnet/p/3985722.html
