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 = http://www.mamicode.com/-1;101     if(startPreorder == NULL || endPreorder==NULL || startInorder==NULL || endInorder==NULL) {102         return NULL;103     } else {104         rootValue = http://www.mamicode.com/*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 }