程式扎記: [ 文章收集 ] Inorder Tree Traversal without Recursion

標籤

2013年4月8日 星期一

[ 文章收集 ] Inorder Tree Traversal without Recursion

來源自 這裡 
前言: 
在 Tree algorithm 中的 Inorder traversal 一般是使用 recursive 的方法完成. 假設我們有定義一個 Node 的 class: 
  1. package ref;  
  2.   
  3. public class Nodeextends Comparablesuper E>> {  
  4.     public Node left = null;  
  5.     public Node right = null;  
  6.     public E data;  
  7.     public Node(E data){this.data = data;}  
  8. }  
接著我們建立一個 Tree 如下結構: 
 

而該 Tree 的 inorder traversal 應該是: 4->2->5->1->3. 建立該 Tree 的代碼如下: 
  1. public static Node GenTree1()  
  2. {  
  3.     Node root = new Node(1);  
  4.     root.left = new Node(2);  
  5.     root.right = new Node(3);  
  6.     root.left.left = new Node(4);  
  7.     root.left.right = new Node(5);  
  8.     return root;  
  9. }  
而常見的 Recursive Inorder 代碼如下: 
  1. public static void InorderRecur(Node node)  
  2. {  
  3.     if(node!=null)  
  4.     {  
  5.         InorderRecur(node.left); // Left  
  6.         System.out.printf("%s ", node.data); // Visit   
  7.         InorderRecur(node.right); // Right  
  8.     }  
  9. }  
而接下來要介紹的是使用 ADT Stack 在不使用 Recursive 情況下完成 Inorder traversal. 

Inorder Tree Traversal without Recursion: 
首先我們知道 Stack 是 LIFO 的 ADT, 接著我們要利用這個特性來設計 algorithm 進行 Tree 的 inorder traversal. 因為 Inorder traversal 是 LVR (Left->Visit->Right), 所以一開始要走到 Tree 的最左邊的 node, 而走的過程中需要把走過的 node 記起來方便後續取出, 因為最後走過的 node 要先拿出來, 故我們採用 Stack 來存放. 整個演算法過程如下: 
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
>>a) Pop the top item from stack.
>>b) Print the popped item, set current = current->right
>>c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

而上面演算法的實作代碼如下: 
  1. public static void Inorder(Node node)  
  2. {  
  3.     Stack> stack = new Stack>();  
  4.     Node curNode = node;  
  5.     while(curNode!=null || !stack.isEmpty())  
  6.     {  
  7.         while(curNode!=null)  
  8.         {  
  9.             stack.push(curNode);  
  10.             curNode = curNode.left;  
  11.         }  
  12.         curNode = stack.pop();  
  13.         System.out.printf("%s ", curNode.data);  
  14.         curNode = curNode.right;  
  15.     }  
  16. }  
而你可以使用下面的測試代碼: 
  1. public static void main(String args[])  
  2. {  
  3.     Node root = GenTree1();  
  4.     Inorder(root);  
  5. }  
執行結果如下: 
4 2 5 1 3

Supplement: 
[ 資料結構 小學堂 ] 樹狀結構導論 : 二元樹的走訪

沒有留言:

張貼留言

網誌存檔

關於我自己

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