## 2010年12月6日 星期一

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

- Pseudo code :
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 :
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>0return 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

### [ Python 文章收集 ] List Comprehensions and Generator Expressions

Source From  Here   Preface   Do you know the difference between the following syntax?  view plain copy to clipboard print ? [x  for ...