트리 자료구조 풀이 (트리 순회)#2

트리 (순회 구현하기)

https://www.acmicpc.net/problem/1991

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
가 된다.

입력
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력
첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

=> 즉 전위 , 중위, 후위 순회를 함수화하여 푸는 문제이다.

문제 풀이

• 전위 순회에 대한 함수 생성 ( visit -> left -> right )
• 중위 순회에 대한 함수 생성 ( left -> visit -> right )
• 후위 순회에 대한 함수 생성 ( left -> right -> visit )

// 노드 수와 트리 정보를 입력받아 처리하는 함수
function processTree(input) {
  // 입력 문자열에서 앞뒤 공백을 제거한 후 , 줄 단위로 분리
  const lines = input.trim().split("\n");

  // 첫번 째 요소가 노드의 갯수
  const N = parseInt(lines[0]);
  const tree = {};

  // 트리 구성
  for (let i = 1; i <= N; i++) {
    // 각 줄을 공백으로 나누어 현재 노드와 왼쪽 자식, 오른쪽 자식으로 추출
    const [node, left, right] = lines[i].split(" ");
    // 현재 노드에 대해 왼쪽 자식과 오른쪽 자식을 저장
    tree[node] = { left, right };
  }

  // 전위 순회 ( visit -> left -> right )
  function preorder(node) {
    // 현재 노드가 . 일 경우, 노드가 없는것이므로 빈 문자열 반환
    if (node === ".") return "";
    const { left, right } = tree[node];
    // 현재 노드를 들어가서 , 왼쪽 서브트리 전위 순회 결과와 오른쪽 서브트리 전위 순회 결과를 이어붙혀 반환
    return node + preorder(left) + preorder(right);
  }

  // 중위 순회 ( left -> visit -> right )
  function inorder(node) {
    // 현재 노드가 . 일 경우, 노드가 없는것이므로 빈 문자열 반환
    if (node === ".") return "";
    const { left, right } = tree[node];
    // 왼쪽 서브트리 중위 순회 결과와 현재 노드 , 오른쪽 서브트리 중위 순회 결과를 이어붙혀 반환하면된다.
    return inorder(left) + node + inorder(right);
  }

  // 후위 순회 ( left -> right -> visit )
  function postorder(node) {
    // 현재 노드가 . 일 경우, 노드가 없는것이므로 빈 문자열 반환
    if (node === ".") return "";
    const { left, right } = tree[node];
    // 왼쪽 서브트리 후위 순회 결과와 오른쪽 서브트리 후위 순회 결과, + 현재 노드를 이어붙이면된다.
    return postorder(left) + postorder(right) + node;
  }

  // 결과 출력
  console.log(preorder("A"));
  console.log(inorder("A"));
  console.log(postorder("A"));
}

마무리

• 이번 문제는 각 순회를 구현할 줄 아느냐의 문제였습니다.
• 이론 정리를 하면서 훑어만 봤던 내용이라 , 아직 구현하는데는 시간이 꽤 걸렸습니다.
• 순회도 규칙이 있어서 여러번해보다보면 익숙해질 것 같습니다.