树的基本操作的非递归实现

树结点

1. struct TreeNode { 
2.  
3.         int val; 
4.         struct TreeNode *left; 
5.         struct TreeNode *right; 
6.         TreeNode(int x):val(x),left(NULL),right(NULL){} 
7. }; 
8. typedef struct TreeNode TreeNode; 

1. void visit(TreeNode *root) 
2. { 
3.         if(root) 
4.                 cout <<root->val<<" "; 
5. } 

1. void preorder(TreeNode *root)
2. { 
3.         if(root) 
4.         { 
5.                 visit(root); 
6.                 preorder(root->left); 
7.                 preorder(root->right); 
8.         } 
9. } 

1. void preorder1(TreeNode *root) 
2. { 
3.         stack<TreeNode*> s; 
4.         while(root || !s.empty()) 
5.         { 
6.                 if(root) 
7.                 { 
8.                         visit(root); 
9.                         s.push(root->right); 
10.                         root = root->left; 
11.                 } 
12.                 else 
13.                 { 
14.                         root = s.top(); 
15.                         s.pop(); 
16.                 } 
17.         } 
18. } 

1. void inorder(TreeNode *root) 
2. { 
3.         if(root) 
4.         { 
5.                 inorder(root->left); 
6.                 visit(root); 
7.                 inorder(root->right); 
8.         } 
9. } 

1. void inorder1(TreeNode *root) 
2. { 
3.         stack<TreeNode*> s; 
4.         while(root || !s.empty()) 
5.         { 
6.                 if(root) 
7.                 { 
8.                         s.push(root); 
9.                         root = root->left; 
10.                 } 
11.                 else 
12.                 { 
13.                         root = s.top(); 
14.                         s.pop(); 
15.                         visit(root); 
16.                         root = root->right; 
17.                 } 
18.         } 
19. } 

1. void postorder(TreeNode *root) 
2. { 
3.         if(root) 
4.         { 
5.                 postorder(root->left); 
6.                 postorder(root->right); 
7.                 visit(root); 
8.         } 
9. } 

1. void postorder1(TreeNode *root) 
2. { 
3.         stack<TreeNode*> s1; 
4.         stack<TreeNode*> s2; 
5.         if(!root) return; 
6.         s1.push(root); 
7.         while(!s1.empty()) 
8.         { 
9.                 s2.push(s1.top()); 
10.                 s1.pop(); 
11.                 if(s2.top()->left) 
12.                         s1.push(s2.top()->left); 
13.                 if(s2.top()->right) 
14.                         s1.push(s2.top()->right); 
15.         } 
16.         while(!s2.empty()) 
17.         { 
18.                 visit(s2.top()); 
19.                 s2.pop(); 
20.         } 
21. } 

1. void postorder2(TreeNode *root) 
2. { 
3.         stack<TreeNode*> s; 
4.         TreeNode *pre = NULL; 
5.         TreeNode *cur; 
6.         if(!root) return; 
7.         s.push(root); 
8.         while(!s.empty()) 
9.         { 
10.                 cur = s.top(); 
11.                 if(!pre || (pre != cur->right && pre != cur->left)) 
12.                 { 
13.                         if(!cur->left && !cur->right) 
14.                         { 
15.                                 visit(cur); 
16.                                 s.pop(); 
17.                                 pre = cur; 
18.                         } 
19.                         if(cur->right) 
20.                                 s.push(cur->right); 
21.                         if(cur->left) 
22.                                 s.push(cur->left); 
23.                 } 
24.  
25.                 else if( pre == cur->left) 
26.                 { 
27.                         if(cur->right) 
28.                                 s.push(cur->right); 
29.                         else 
30.                         { 
31.                                 visit(cur); 
32.                                 s.pop(); 
33.                                 pre = cur; 
34.                         } 
35.                 } 
36.                 else if(pre == cur->right) 
37.                 { 
38.                         visit(cur); 
39.                         s.pop(); 
40.                         pre = cur; 
41.                 } 
42.         } 
43. } 

1. void level_traversal(TreeNode *root) 
2. { 
3.         queue<TreeNode*> q; 
4.         if(!root) return; 
5.         q.push(root); 
6.         while(!q.empty()) 
7.         { 
8.                 if(q.front()->left) 
9.                         q.push(q.front()->left); 
10.                 if(q.front()->right) 
11.                         q.push(q.front()->right); 
12.                 visit(q.front()); 
13.                 q.pop(); 
14.         } 
15. } 

(更新中)

本文转自nxlhero 51CTO博客，原文链接：http://blog.51cto.com/nxlhero/1159213，如需转载请自行联系原作者