DataStructure & Algorithm/Algorithm
반복문을 이용한 Tree 의 후위순회(Post-order Traversal)
진스팍
2019. 7. 30. 21:01
보통 트리의 순회를 구현하게되면, 간단한 재귀함수의 호출 형태로 구현하게 되는데, 이 때 고려해야할 점은 재귀함수의 호출은 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 를 활용해 트리 구조를 제공하였으나 ;;
위와 같이하면 저장된 비선형 트리를 재귀구조없이 후위 순회할 수 있다.