트리(Tree) 구조와 트리 순회

🌲 트리의 개념

• 트리는 노드로 이루어진 자료 구조이다.
• 트리는 하나의 루트 노드를 갖는다.
  • 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
  • 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있다.
• 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.
• 그래프의 한 종류로, 사이클이 없는 하나의 연결 그래프이다. 

트리의 개념 자세히 알아보기 ➔ https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

 

🌲 이진트리

• 각 노드가 최대 2개의 자식을 갖는 트리

 

🌲 이진트리 순회(Tree Traversal)

✦ 전위 순회: 뿌리(root)를 먼저 방문

✦ 중위 순회: 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문

✦ 후위 순회: 하위 트리 모두 방문 후 뿌리(root)를 방문

 

 

🌲 알고리즘 적용(JavaScript)

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

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input.shift();
let result = '';

const tree = {};
for (let i = 0; i < N; i++) {
  const [node, left, right] = input[i].split(' ');
  tree[node] = [left, right];
}

// 전위
function preorder(node) {
  if (node === ".") return;
  const [left, right] = tree[node];
  result += node;
  preorder(left);
  preorder(right);
}

// 중위
function inorder(node) {
  if (node === ".") return;
  const [left, right] = tree[node];
  inorder(left);
  result += node;
  inorder(right);
}

// 후위
function postorder(node) {
  if (node === ".") return;
  const [left, right] = tree[node];
  postorder(left);
  postorder(right);
  result += node;
}

preorder("A");
result += "\n";
inorder("A");
result += "\n";
postorder("A");

console.log(result);