백준 - 1991 트리 순회 [Tree]

 

1991번: 트리 순회

 

1. 문제 요약

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하라.

 

2. 접근 방법

트리 예시

새로운 노드로 이동할 때마다 순회별 방문 순서를  반복한다고 생각하면 됩니다.

순서가 헷갈릴 수 있는데, 세 단계를 반복하면 쉽습니다.

예시) 전위 순회의 경우

1. 현재 노드 출력
2. 왼쪽 이동
3. 오른쪽 이동

 

2 - 1. 전위 순회

전위 순회

ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)

1. 전위 순회의 경우 루트가 가장 먼저 나오기 때문에, 노드를 방문하자마자 A(1)를 출력합니다.
2. 왼쪽 노드(B)로 이동합니다.
   
   1. 루트가 나왔으므로 B(2)를 출력합니다.(다시 루트-왼쪽-오른쪽 순서를 반복)
   2. 왼쪽 노드(D)로 이동합니다.
      
      1. 루트가 나왔으므로 D(3)를 출력합니다.(다시 루트-왼쪽-오른쪽 순서를 반복)
      2. 왼쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
      3. 오른쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
   3. 오른쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
3.  오른쪽 노드(C)로 이동합니다.
   1. 루트가 나왔으므로 C(4)를 출력합니다.(다시 루트-왼쪽-오른쪽 순서를 반복)
   2. 왼쪽 노드(E)로 이동합니다.
      1. 루트가 나왔으므로 E(5)를 출력합니다.(다시 루트-왼쪽-오른쪽 순서를 반복)
      2. 왼쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
      3. 오른쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
   3. 오른쪽 노드(F)로 이동합니다.
      1. 루트가 나왔으므로 F(6)를 출력합니다.(다시 루트-왼쪽-오른쪽 순서를 반복)
      2. 왼쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
      3. 오른쪽 노드(G)로 이동합니다.
         1. 루트가 나왔으므로 G(7)를 출력합니다.(다시 루트-왼쪽-오른쪽 순서를 반복)
         2. 왼쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
         3. 오른쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.

 

2 - 2. 중위 순회

중위 순회

DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)

중위 순회의 경우 각각의 노드의 자식이 두 개 이하일 때만 사용할 수 있습니다.

1. 중위 순회의 경우 왼쪽 노드가 가장 먼저 나오기 때문에 왼쪽 노드(B)로 이동합니다.
   
   1. 왼쪽 노드(D)로 이동합니다.(다시 왼쪽-루트-오른쪽 순서를 반복)
      1. 왼쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.(다시 왼쪽-루트-오른쪽 순서를 반복)
      2. 루트가 나왔으므로 D(1)를 출력합니다.
      3. 오른쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
   2. 루트가 나왔으므로 B(2)를 출력합니다.
   3. 오른쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
2. 루트가 나왔으므로 A(3)를 출력합니다.
3. 오른쪽 노드(C)로 이동합니다.
   1. 왼쪽 노드(E)로 이동합니다.(다시 왼쪽-루트-오른쪽 순서를 반복)
      1. 왼쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.(다시 왼쪽-루트-오른쪽 순서를 반복)
      2. 루트가 나왔으므로 E(4)를 출력합니다.
      3. 오른쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
   2. 루트가 나왔으므로 C(5)를 출력합니다.
   3. 오른쪽 노드(F)로 이동합니다.
      1. 왼쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.(다시 왼쪽-루트-오른쪽 순서를 반복)
      2. 루트가 나왔으므로 F(6)를 출력합니다.
      3. 오른쪽 노드(G)로 이동합니다. 
         1. 왼쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.(다시 왼쪽-루트-오른쪽 순서를 반복)
         2.  루트가 나왔으므로 G(7)를 출력합니다.
         3. 오른쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.

 

2 - 3. 후위 순회

DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

후위 순회

1. 중위 순회의 경우 왼쪽 노드가 가장 먼저 나오기 때문에 왼쪽 노드(B)로 이동합니다.
   1. 왼쪽 노드(D)로 이동합니다.(다시 왼쪽-오른쪽-루트 순서를 반복)
      1. 왼쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.(다시 왼쪽-오른쪽-루트 순서를 반복)
      2. 오른쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
      3. 루트가 나왔으므로 D(1)를 출력합니다.
   2. 오른쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
   3. 루트가 나왔으므로 B(2)를 출력합니다.
2. 오른쪽 노드(C)로 이동합니다.
   1. 왼쪽 노드(E)로 이동합니다.(다시 왼쪽-오른쪽-루트 순서를 반복)
      1. 왼쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.(다시 왼쪽-오른쪽-루트 순서를 반복)
      2. 오른쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
      3. 루트가 나왔으므로 E(3)를 출력합니다.
   2. 오른쪽 노드(F)로 이동합니다.
      1. 왼쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.(다시 왼쪽-오른쪽-루트 순서를 반복)
      2. 오른쪽 노드(G)로 이동합니다.
         1. 왼쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.(다시 왼쪽-오른쪽-루트 순서를 반복)
         2. 오른쪽 노드를 방문할 차례인데, 방문할 곳이 없습니다.
         3. 루트가 나왔으므로 G(4)를 출력합니다.
      3. 루트가 나왔으므로 F(5)를 출력합니다.
   3.  루트가 나왔으므로 C(6)를 출력합니다.
3. 루트가 나왔으므로 A(7)를 출력합니다.

 

3. 파이썬

# 전위 순회
def preorder(node):
    if node != '.':
        print(node, end='') # 현재 노드 출력
        preorder(tree[node][0]) # 왼쪽 노드
        preorder(tree[node][1]) # 오른쪽 노드
        
# 중위 순회
def inorder(node):
    if node != '.':
        inorder(tree[node][0]) # 왼쪽 노드
        print(node, end='') # 현재 노드 출력
        inorder(tree[node][1]) # 오른쪽 노드
        
# 후위 순회
def postorder(node):
    if node != '.':
        postorder(tree[node][0]) # 왼쪽 노드
        postorder(tree[node][1]) # 오른쪽 노드
        print(node, end='') # 현재 노드 출력

 

4. 자바

// 전위 순회
private static void preorder(char node) {
    if (node != '.') {
        System.out.print(node); // 현재 노드 출력
        preorder(tree.get(node).left); // 왼쪽 노드
        preorder(tree.get(node).right); // 오른쪽 노드
    }
}

// 중위 순회
private static void inorder(char node) {
    if (node != '.') {
        inorder(tree.get(node).left); // 왼쪽 노드
        System.out.print(node); // 현재 노드 출력
        inorder(tree.get(node).right); // 오른쪽 노드
    }
}

// 후위 순회
private static void postorder(char node) {
    if (node != '.') {
        postorder(tree.get(node).left); // 왼쪽 노드
        postorder(tree.get(node).right); // 오른쪽 노드
        System.out.print(node); // 현재 노드 출력
    }
}

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/1991.%E2%80%85%ED%8A%B8%EB%A6%AC%E2%80%85%EC%88%9C%ED%9A%8C