효율적인 트리 순열 구현

참고한 문서

전위탐색

  1. 루트를 방문한다.
  2. 왼쪽 서브트리를 방문한다.
  3. 오른쪽 서브트리를 방문한다.

재귀적인 함수 호출을 막을려면 효율적인 순회 처리가 필요하다.

순회되는 객체를 즉시 사용하는 방법으로 스택을 사용했습니다.

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. 루트 객체를 스택에 할당한다.
  2. 스택 요소가 존재하는 동안 아래 절차를 반복한다.
    1. 스택의 한 요소를 빼내고 출력한다.
    2. 빼낸 요소가 가리키는 오른쪽 노드를 스택에 집어넣는다.
    3. 빼낸 요소가 가리키는 왼쪽 노드를 스택에 집어넣는다.

재귀 구현체와 달리1 우선적으로 넣는 노드의 left, right 순서가 반대인데, 마지막으로 넣은 요소가 먼저 출력되는 스택의 특성 때문이다.

중위순회

  1. 왼쪽 서브트리를 방문한다.
  2. 루트를 방문한다.
  3. 오른쪽 노드 방문
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
  1. 루트 객체를 current 에 할당한다.
  2. 스택에 current 객체를 집어넣고 current.leftcurrent에 할당시킨다.
  3. current 의 값이 없지만 스택의 값이 있는 경우에 아래 절차를 시행한다.
    1. 스택의 한 요소를 current로 빼낸다.
    2. 빼낸 요소의 값을 출력하고, current.rightcurrent에 재할당한다.
    3. 2번째 단계로 이동한다.
  4. 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()
  1. 루트 객체를 current 에 할당한다.
  2. current의 값이 있을 동안 아래 절차를 반복한다.
    1. 만약 current.left 가 없다면
      1. current의 값을 출력한다.
      2. current.rightcurrent에 재할당한다.
    2. 아니면?
      1. current.left 의 가장 오른쪽 자식을 currnet에 할당시킨다.
      2. current.leftcurrent에 재할당한다.

후위순회

  1. 왼쪽 서브트리를 방문한다.
  2. 오른쪽 서브트리를 방문한다.
  3. 루트를 방문한다.
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
  1. 루트 객체를 root 변수에 할당한다.
  2. root 값이 존재할 동안 아래 절차를 반복한다.
    1. root.rightroot를 스택에 넣는다.
    2. root.leftroot에 재할당한다.
  3. stack의 한 요소를 빼내 root로 할당한다.
    1. root.right 값이 스택의 맨 위와 동일하면
      1. stack.pop() 및 루트를 스택에 할당한다.
    2. 아니라면 root의 값을 ans 스택에 저장해두고, rootNone으로 초기화 한다.
  4. 스택의 값이 존재 할 동안 1~3번 항목을 반복한다.
  5. 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를 꺼내 출력된다.

파이썬 구현체

여기에서 코드를 보실 수 있습니다.

재귀 구현체와 비교한 테스트 코드테스트 결과도 있습니다.


  1. 왼쪽 노드를 먼저 받고 넘김(call-back) [return]