[ 文章收集 ] Inorder Tree Traversal without Recursion

來源自 這裡 
前言: 
在 Tree algorithm 中的 Inorder traversal 一般是使用 recursive 的方法完成. 假設我們有定義一個 Node 的 class: 

view plaincopy to clipboardprint?

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 的代碼如下: 

view plaincopy to clipboardprint?

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 代碼如下: 

view plaincopy to clipboardprint?

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.

而上面演算法的實作代碼如下: 

view plaincopy to clipboardprint?

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. }  

而你可以使用下面的測試代碼: 

view plaincopy to clipboardprint?

1. public static void main(String args[])  
2. {  
3.     Node root = GenTree1();  
4.     Inorder(root);  
5. }  

執行結果如下: 

4 2 5 1 3

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