개발일지/Algorithm

백준 - 1991 트리 순회 [Tree]

E-room 2023. 11. 1. 16:47
728x90

 

 

1991번: 트리 순회

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파

www.acmicpc.net

 

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

728x90
저작자표시 비영리 변경금지