반복문을 이용한 Tree 의 후위순회(Post-order Traversal)

 

보통 트리의 순회를 구현하게되면, 간단한 재귀함수의 호출 형태로 구현하게 되는데, 이 때 고려해야할 점은 재귀함수의 호출은 Stack 메모리의 희생을 요구한다는 점이다.

즉, 순회만으로도 노드의 갯수가 많아진다면 Stack Overflow 에러가 발생하게 된다.

의외로 Tree 의 Traversal 을 Recursion 이 아닌 Iteratation 로 구현하는데 어려움을 겪을 수 있어 정리해보았다.

 

public class Algorithm {

	/***
    	TreeMap 은 index 를 키값으로하는 Map 의 형식으로 저장된 n-Ary tree
        TreeValues 는 index 에 따라 트리의 Value 를 저장한 리스트
    **/
	public void postOrderTraversal(Map<Integer, List<Integer>> treeMap, List<Integer> treeValues) {
		Stack<Integer> returnStack = new Stack<>();		//순회할 노드들의 인덱스를 저장하는 스택
		Stack<Integer> resultStack = new Stack<>();		//순회하고 나온 Return 값을 저장하는 스택
		returnStack.push(0);					//0번 노드를 루트로 가정하고 루트부터 순회
		while (!returnStack.isEmpty()) {
			int next = returnStack.pop();
			resultStack.push(treeValues.get(next));
			if(treeMap.containsKey(next)) {
				List<Integer> children = treeMap.get(next);
				for(int child : children) {
					returnStack.push(child);
				}
			}
		}
		while (!resultStack.isEmpty()) {
			System.out.println(resultStack.pop());		//후위 순서대로 출력
		}
	}
}

 

귀찮아서 별도의 노드 클래스 없이 Map 과 List 를 활용해 트리 구조를 제공하였으나 ;;

위와 같이하면 저장된 비선형 트리를 재귀구조없이 후위 순회할 수 있다.