참고한 문서
전위탐색
- 루트를 방문한다.
- 왼쪽 서브트리를 방문한다.
- 오른쪽 서브트리를 방문한다.
재귀적인 함수 호출을 막을려면 효율적인 순회 처리가 필요하다.
순회되는 객체를 즉시 사용하는 방법으로 스택을 사용했습니다.
def preorder(self):
stack = [self.root] # 1
while len(stack) > 0: # 2
item = stack.pop() # 2-1
print(item.value, end=' ')
if item.right: # 2-2
stack.append(item.right)
if item.left: # 2-2
stack.append(item.left)
- 루트 객체를 스택에 할당한다.
- 스택 요소가 존재하는 동안 아래 절차를 반복한다.
- 스택의 한 요소를 빼내고 출력한다.
- 빼낸 요소가 가리키는 오른쪽 노드를 스택에 집어넣는다.
- 빼낸 요소가 가리키는 왼쪽 노드를 스택에 집어넣는다.
재귀 구현체와 달리1 우선적으로 넣는 노드의 left, right 순서가 반대인데, 마지막으로 넣은 요소가 먼저 출력되는 스택의 특성 때문이다.
중위순회
- 왼쪽 서브트리를 방문한다.
- 루트를 방문한다.
- 오른쪽 노드 방문
def inorder(self):
stack, current, loop = [], self.root, True # 1
while loop:
if current:
stack.append(current) # 2, 3-3
current = current.left
elif stack: # 3
current = stack.pop() # 3-1
print(current.value, end=' ') # 3-2
current = current.right
else:
loop = False # 4
- 루트 객체를
current에 할당한다. - 스택에
current객체를 집어넣고current.left를current에 할당시킨다. current의 값이 없지만 스택의 값이 있는 경우에 아래 절차를 시행한다.- 스택의 한 요소를
current로 빼낸다. - 빼낸 요소의 값을 출력하고,
current.right를current에 재할당한다. - 2번째 단계로 이동한다.
- 스택의 한 요소를
current와 스택의 값이 비어 있을 때 반복을 중단시킨다.
순회 예시
A
/ \
B C
/ \ / \
D E F G
/
H
1. 빈 스택을 생성한다 : Stack = []
2. current 를 루트로 초기화한다 : current = A
3. 스택에 current 객체를 집어넣고 current.left를 current에 할당시킨다.
current -> A
push 1: stack -> 1
current -> B
push B: stack -> B, A
current -> D
push D: stack -> D, B, A
current -> H
push H: stack -> H, D, B, A
current = None
4. stack 요소 꺼내기
a) pop H: stack -> D, B, A
b) H 출력
c) H의 오른쪽 노드가 없음, current = None 유지
4. 다시 꺼내기
a) pop D: stack -> B, A
b) D 출력
c) D의 오른쪽 노드가 없음, current = None 유지
4. 계속 꺼내기
a) pop B: stack -> A
b) B 출력
c) B의 오른쪽 노드 E, current -> E
3. E를 스택에 넣고 current를 None으로 만듬
stack -> E, A
current = None
4. stack 요소 꺼내기
a) pop E: stack -> A
b) E 출력
c) E의 오른쪽 노드 없음, current = None 유지
4. 더 꺼내기
a) pop A: stack -> None
b) A 출력
c) A의 오른쪽 노드 C, current -> C
3. C, F를 스택에 넣음
push C: stack -> C
currnet -> F
push F: stack -> F, C
current = None
4. stack 요소 꺼내기
a) pop F: stack -> C
b) F 출력
c) F의 오른쪽 노드 없음, current = None
4. stack 하나 더 꺼내기
a) pop C: stack -> None
b) C 출력
c) C의 오른쪽 노드 G, current -> G
3. G를 스택에 넣음
push G: stack -> G
current -> None
4. stack 요소 꺼내기
a) pop G: stack -> None
b) G 출력
c) G의 오른쪽 노드 없음, current = None
stack이 비었고, current가 None의 상태이다. 순회 종료.
스택 없는 중위순회
def inorder_without_stack(self):
current = self.root # 1
while current: # 2
if current.left is None: # 2-1
print(current.value, end=' ') # 2-1-2
current = current.right # 2-1-2
else: # 2-2
pre = current.left # 2-2-1~
while pre.right and pre.right != current:
pre = pre.right # ~2-2-1
if pre.right is None: # 2-2-2~
pre.right = current
current = current.left # ~2-2-2
else:
pre.right = None
print(current.value, end=' ')
current = current.right
print()
- 루트 객체를
current에 할당한다. current의 값이 있을 동안 아래 절차를 반복한다.- 만약
current.left가 없다면current의 값을 출력한다.current.right를current에 재할당한다.
- 아니면?
current.left의 가장 오른쪽 자식을currnet에 할당시킨다.current.left를current에 재할당한다.
- 만약
후위순회
- 왼쪽 서브트리를 방문한다.
- 오른쪽 서브트리를 방문한다.
- 루트를 방문한다.
def postorder(self):
stack, root, ans = [], self.root, []
while True:
while root:
if root.right:
stack.append(root.right)
stack.append(root)
root = root.left
root = stack.pop()
if (root.right and
self.peek(stack) == root.right):
stack.pop() # 오른쪽 자식 제거
stack.append(root)
root = root.right
else:
ans.append(root.value)
root = None
if len(stack) <= 0:
for i in ans:
print(i, end=' ')
print()
return
def peek(self, stack):
if len(stack) > 0:
return stack[-1]
return None
- 루트 객체를
root변수에 할당한다. root값이 존재할 동안 아래 절차를 반복한다.root.right과root를 스택에 넣는다.root.left를root에 재할당한다.
stack의 한 요소를 빼내root로 할당한다.root.right값이 스택의 맨 위와 동일하면stack.pop()및 루트를 스택에 할당한다.
- 아니라면
root의 값을ans스택에 저장해두고,root를None으로 초기화 한다.
- 스택의 값이 존재 할 동안 1~3번 항목을 반복한다.
ans의 처음부터 끝 요소 전부 출력한다.
순회 예시
A
/ \
B C
/ \ / \
D E F G
/
H
1. 루트의 오른쪽(이 존재하면)와 그 자신을 스택에 넣는다. 왼쪽 자식으로 이동한다.
a) stack -> A, C
b) root = B
2. B의 오른쪽과 B를 스택에 넣는다. 왼쪽 자식으로 루트를 이동한다.
a) stack -> B, E, A, C
b) root = D
3. D의 오른쪽이 없음, D를 스택에 넣는다. 왼쪽 자식으로 이동한다.
a) stack -> D, B, E, A, C
b) root = H
4. H의 오른쪽이 없음, H를 스택에 넣는다. 왼쪽 자식이 없음
a) stack -> H, D, B, E, A, C
b) root = None
5. 루트 노드가 비어 있음
a) pop H: stack -> D, B, E, A, C
b) H의 오른쪽 노드가 존재하지 않음, H 출력
c) root = None
6. 루트 노드가 비어 있음
a) pop D: stack -> B, E, A, C
b) D의 오른쪽 노드가 존재하지 않음, D 출력
c) root = None
7. 루트 노드가 비어 있음
a) pop B: stack -> E, A, C
b) B의 오른쪽 노드가 스택의 맨 위 요소와 동일함, pop E && push B: stack -> B, A, C
c) root = E (B의 오른쪽 노드)
8. E의 오른쪽 노드가 존재하지 않음. E를 스택에 넣는다. 왼쪽 자식으로 이동.
stack -> E, B, A, C
9. 루트 노드가 비어 있음
a) pop E: stack -> B, A, C
b) E의 오른쪽 노드가 존재하지 않음, E 출력
c) root = None
10. 루트 노드가 비어 있음
a) pop B: stack -> A, C
b) B의 오른쪽 자식이 스택의 멘 위 요소와 동일하지 않음, B 출력
c) root = None
11. 루트 노드가 비어 있음
a) pop A: stack -> C
b) A의 오른쪽 자식은 스택의 맨 위와 동일하다. pop C && push A : stack -> A
c) 루트를 A의 오른쪽 노드로 이동한다. root = C
12. 위와 같은 순서를 4-5단계를 제외해서 반복한다. F, G와 C를 출력하고, A를 꺼내 출력된다.
파이썬 구현체
여기에서 코드를 보실 수 있습니다.
재귀 구현체와 비교한 테스트 코드와 테스트 결 과도 있습니다.
왼쪽 노드를 먼저 받고 넘김(call-back) ↩︎