[C++ 演算法] 使用 Iterative 進行 Binary Tree 中序訪問

前言 : 
常見的二元樹中序走法版本為 Recursive 版本 (參考這裡), 這裡介紹 Iterative 版本. 

範例代碼 : 

- Pseudo code :

view plaincopy to clipboardprint?

1. traverse(node) {  
2.    if(!node) return;  
3.    while (!empty(stack) && node->right==null) {  
4.      /*Remember the left nodes in stack*/  
5.      while (node->left && flag) {  
6.         push(stack, node);  
7.         node = node->left;  
8.       }  
9.   
10.       /*Process the node*/  
11.       printf("%d", node->data);  
12.   
13.       /*Do the tail recursion*/  
14.       if(node->right) {  
15.          node = node->right  
16.          flag = true;  
17.       } else {  
18.          node = pop(stack); /*New Node will be from previous*/  
19.          flag = false;  
20.       }  
21.     }  
22. }  

- Implementation in C :

view plaincopy to clipboardprint?

1. #include   
2. #include   
3. #include   
4. #include   
5. #include   
6. using namespace std;  
7.   
8. struct Node {  
9.      int value;  
10.      Node *left;  
11.      Node *right;  
12. };  
13.   
14. Node* addNewNode(Node *root, int val) {  
15.     if(root==NULL) {  
16.         cout << "Build root(" << val << ")..." << endl;  
17.         root = new Node();  
18.         root->value = val;  
19.         root->left = root->right = NULL;  
20.         return root;  
21.     } else {  
22.         Node *tmp = root;  
23.         bool flag = false;  
24.         while(tmp!=NULL) {  
25.             if(tmp->value>val) { // 往左子樹移動  
26.                 if(tmp->left!=NULL) tmp = tmp->left;  
27.                 else {  
28.                     cout << "Build new lnode(" << val << ")..." << endl;  
29.                     tmp->left = new Node();  
30.                     tmp->left->value = val;  
31.                     tmp->left->left = tmp->left->right = NULL;  
32.                     flag = true;  
33.                     break;  
34.                 }  
35.             } else if(tmp->value// 往右子樹移動  
36.                 if(tmp->right!=NULL) tmp = tmp->right;  
37.                 else {  
38.                     cout << "Build new rnode(" << val << ")..." << endl;  
39.                     tmp->right = new Node();  
40.                     tmp->right->value = val;  
41.                     tmp->right->left = tmp->right->right = NULL;  
42.                     flag = true;  
43.                     break;  
44.                 }  
45.             } else {  
46.                 break; // The value already exist  
47.             }  
48.         }  
49.         return root;  
50.     }  
51. }  
52.   
53. void inorderVisit(Node *root) {  
54.     if(root!=NULL) {  
55.         inorderVisit(root->left);  
56.         cout << root->value << " ";  
57.         inorderVisit(root->right);  
58.     }  
59. }  
60.   
61. // Iterative Inorder Visit : http://datastructures.itgo.com/trees/nrtraversal.htm  
62. //  root 為一個h的根, n 為中序追蹤的第幾n個節點。  
63. //  函數最後要回傳要回傳中序追蹤第n個節點內的value。  
64. //  補充說明: int findValue()就是要找這個binary tree第n大的數  
65. int findValue(Node *root, int n) {  
66.     Node *tmp = root;  
67.     stack mystack;  
68.     //mystack.push(tmp);  
69.     int cnt = n, rst = -1;  
70.     bool flag = true;  
71.     while(cnt>0) {  
72.         /*Remember the left nodes in stack*/  
73.         while(tmp->left && flag) {  
74.             mystack.push(tmp);  
75.             tmp = tmp->left;  
76.         }  
77.   
78.         /*Process the node*/  
79.         rst = tmp->value;  
80.         printf("Count %d (%d)...\n", cnt, rst);  
81.   
82.   
83.         /*Do the tail recursion*/  
84.         if(tmp->right)  {  
85.             tmp = tmp->right;  
86.             flag = true;  
87.         } else {  
88.             tmp = mystack.top();  
89.             mystack.pop(); // http://www.cplusplus.com/reference/stl/stack/pop/  
90.             flag = false;  
91.         }  
92.         cnt--;  
93.         if(mystack.empty() && tmp->right==NULL) break;  
94.     }  
95.     if(cnt==0 && n>0) return rst;  
96.     return -1;  
97. }  
98. void main(){  
99.     Node *root = NULL;  
100.     int n = 5;  
101.     int data[] = {2,3,1,5,7,8,6,4,9,10};  
102.     /*Build Binary Search Tree*/  
103.     for(int i=0; i<10; i++) root = addNewNode(root, data[i]);  
104.     /*Inorder Traversal*/  
105.     inorderVisit(root);  
106.     cout << endl;  
107.     /*Find value in location=n*/  
108.     cout << "Location(" << n << ")=" << findValue(root, n) << endl;  
109. }  

Output : 

Build root(2)...
Build new rnode(3)...
Build new lnode(1)...
Build new rnode(5)...
Build new rnode(7)...
Build new rnode(8)...
Build new lnode(6)...
Build new lnode(4)...
Build new rnode(9)...
Build new rnode(10)...
1 2 3 4 5 6 7 8 9 10
Count 5 (1)...
Count 4 (2)...
Count 3 (3)...
Count 2 (4)...
Count 1 (5)...
Location(5)=5

補充說明 : 
* Non-recursive traversal using a Threaded Binary Tree 
* Help me understand Inorder Traversal without using recursion