이진트리의 순차적 중위 순회 (iterative in-order traversal)

이진 트리의 in-order traversal을 재귀호출(recursion)을 사용하지 않고 구현해보자.



탐색할 때 주어진 노드의 왼쪽 subtree를 우선적으로 탐색해야 하고, 먼저 방문된 parent node보다 나중에 방문된 left child node가 우선적으로 처리가 되는 특성(LIFO)을 보이므로, stack을 사용하여 구현한다.
알고리즘을 기술해보면,

1. Root node를 시작으로 node의 왼쪽 자식 노드를 따라가며 stack에 push
2. Stack에 노드가 있는 동안
1. Node를 pop하고
2. Node를 출력
3. 이 node의 오른쪽 자식 node를 시작으로 node의 왼쪽 자식 노드를 따라가며 stack에 push

가 된다.

(아래 구현에서 stack은 slice를 이용하여 간단히 흉내만 낸다)

func inorderTraverseIterative(root *Node) {

S := []*Node{}

node := root

for node != nil {

S = append(S, node)

node = node.Left

}

for size := len(S); size > 0; size = len(S) {

node = S[size-1]

S = S[:size-1]

fmt.Printf("%d ", node.Val)

node = node.Right

for node != nil {

S = append(S, node)

node = node.Left

}

}

}