트리 탐색 (Iterative Tree Traversal) - 비 재귀

Iterative Tree Traversal

 Pre-order, Post-order, In-order 알고리즘

실행 결과는 위키피디아의 트리 샘플을 참고

(http://en.wikipedia.org/wiki/Tree_traversal#Example)

 Pre-order,

void preOrderIterative(Node n) {     Stack<Node> s = new new Stack<Node>();     s.push(n);       while (!s.empty()) {         n = s.pop();         n.visit();           if (n.right != null) {             s.push(n.right);         }         if (n.left != null) {             s.push(n.left);         }     } }

Each line of the example shows the stack at the beginning of the iteration, the set of visited nodes so far after the iteration, and the stack at the end of the iteration.

1: s={}, visited={F}, s={B,G} 2: s={G}, visited={F,B}, s={A,D,G} 3: s={D,G}, visited={F,B,A}, s={D,G} 4: s={G}, visited={F,B,A,D}, s={C,E,G} 5: s={E,G}, visited={F,B,A,D,C}, s={E,G} 6: s={G}, visited={F,B,A,D,C,E}, s={G} 7: s={}, visited={F,B,A,D,C,E,G}, s={I} 8: s={}, visited={F,B,A,D,C,E,G,I}, s={H} 9: s={}, visited={F,B,A,D,C,E,G,I,H}, s={}

Post-order,

This one uses two stacks. It consumes the input stack and builds the output stack. At the end of the method, it pops each node from the output stack and visits it.

void postOrderIterative(Node n) {     Stack<Node> s = new new Stack<Node>();     Stack<Node> o = new new Stack<Node>();     s.push(n);       while (!s.empty()) {         n = s.pop();         o.push(n);           if (n.left != null) {             s.push(n.left);         if (n.right != null) {             s.push(n.right);         }     }     while (!o.empty()) {         o.pop().visit();     } }

Each line of the example below shows state of the input stack and output stack after the iteration.

1: out={F}, in={G,B} 2: out={G,F}, in={I,B} 3: out={I,G,F}, in={H,B} 4: out={H,I,G,F}, in={B} 5: out={B,H,I,G,F}, in={D,A} 6: out={D,B,H,I,G,F}, in={E,C,A} 7: out={E,D,B,H,I,G,F}, in={C,A} 8: out={C,E,D,B,H,I,G,F}, in={A} 9: out={A,C,E,D,B,H,I,G,F}, in={}

In-order,

void inOrderIterative(Node n) {     Stack<Node> s = new new Stack<Node>();     s.push(n);       while (!s.empty()) {         while (n.left != null) {             n = n.left;             s.push(n);         }         n = s.pop();         n.visit();         if (n.right != null) {             s.push(n.right);         }     } }

Each line of the example shows the stack at the beginning of the iteration, the set of visited nodes so far after the iteration, and the stack at the end of the iteration.

1: s={A,B,F}, v={A}, s={B,F} 2: s={B,F}, v={A,B}, s={D,F} 3: s={C,D,F}, v={A,B,C}, s={D,F} 4: s={D,F}, v={A,B,C,D}, s={E,F} 5: s={E,F}, v={A,B,C,D,E}, s={F} 6: s={F}, v={A,B,C,D,E,F}, s={G} 7: s={G}, v={A,B,C,D,E,F,G}, s={I} 8: s={H,I}, v={A,B,C,D,E,F,G,H}, s={I} 9: s={I}, v={A,B,C,D,E,F,G,H,I}, s={}

 

 

출처:

http://zerocredibility.wordpress.com/2010/11/16/iterative-tree-traversal/#comments