예상했던 대로 잘 순회하는군요. 이번에는 스택 자료 구조와 반복문을 이용해서 구현해 보겠습니다.
코드 7-4는 전위 순회를 스택과 반복문으로 구현한 것입니다.
코드 7-4
def iter_preorder(cur):
s = Stack()
while True:
while cur:
print(cur.data, end=' ') ➊
s.push(cur)
cur = cur.left ➋
cur = s.pop() ➌
if not cur:
break
cur = cur.right ➍
➊ 방문
➋ 현재 노드의 왼쪽 방향으로 쭉 내려갑니다.
➌ pop으로 가져온 노드가
1. None이라면 스택이 비어 있는 경우, 즉 모든 노드를 순회한 경우
2. 왼쪽 서브 트리가 없거나
3. 왼쪽 서브 트리를 방문한 상태입니다.
➍ 왼쪽 서브 트리를 방문했으므로 오른쪽 서브 트리를 순회합니다.
코드 7-4는 재귀 함수로 구현한 코드보다 가독성이 좋지 않군요. 하지만 스택 프레임을 하나만 사용하므로 성능은 재귀 함수에 비해 좋을 것입니다. 스택 자료 구조를 하나 만든 후 현재 노드에서 시작해서 먼저 방문을 하고 왼쪽 자식 노드가 있다면 쭉 따라 내려갑니다. 왼쪽 자식 노드가 없거나 왼쪽 자식의 모든 노드를 순회했다면 pop을 이용하여 이전 노드로 돌아와 오른쪽 자식 노드를 순회합니다.