程式扎記: [C++ 演算法] 使用 Iterative 進行 Binary Tree 中序訪問

標籤

2010年12月6日 星期一

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

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

範例代碼 : 

- 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

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!