트리 자료구조 차이: 이진 트리 BST MST 구분하기

여기부터는 필요한 기능을 골라 읽는 참고 영역입니다. 새로운 파일로 전체 코드를 실행할 때는 아래 Node.js 실행 안내를 따르세요. 앞쪽의 작은 브라우저 실습과 전체 파일을 한 콘솔에 이어 붙이지 마세요. 기능별 입력 조건과 반환 형식은 아래 설명을 기준으로 합니다.

트리·이진 트리·BST·MST는 서로 다른 질문에 답합니다

트리는 정점들이 연결되어 있고 사이클이 없는 무방향 그래프입니다. 두 정점 사이의 단순 경로가 하나뿐이라는 성질 때문에 계층의 부모를 정할 수 있습니다. 정점이 n개인 비어 있지 않은 트리의 간선은 n-1개이며, 정점 하나만 있어도 트리입니다. 연결되지 않은 여러 트리는 포리스트라고 부릅니다.

트리 중 한 정점을 루트로 정하면 루트 방향의 이웃이 부모, 반대 방향이 자식이 됩니다. 부모가 같은 노드는 형제이고 자식이 없는 노드는 리프입니다. 깊이는 루트에서 해당 노드까지의 간선 수, 높이는 루트에서 가장 먼 리프까지의 간선 수로 셉니다. 따라서 루트 하나의 높이는 0입니다. 레벨을 1부터 세는 자료와 수치를 비교할 때 기준을 먼저 확인해야 합니다.

배열과 연결 표현 중 무엇을 저장할 것인가

완전 이진 트리는 루트를 1번 칸에 두면 i의 왼쪽 자식이 2i, 오른쪽이 2i+1인 배열로 표현할 수 있습니다. 빈자리가 거의 없어 위치만으로 부모·자식을 찾습니다. 반대로 한쪽으로 길게 뻗은 트리에 같은 배치를 적용하면 쓰지 않는 칸이 급격히 늘어납니다. 이런 모양에는 left와 right 참조를 가진 노드가 자연스럽습니다.

자식 수가 제한되지 않는 일반 트리는 children 배열로 표현할 수 있습니다. 또 첫 자식-다음 형제 표현은 노드마다 두 연결만 둡니다. A의 자식이 B,C,D라면 A.left=B, B.right=C, C.right=D처럼 저장합니다. 이때 right는 자식이 아니라 형제이므로 아래의 일반 이진 트리 순회를 그대로 적용하면 계층 의미가 달라집니다.

완전·포화·정 이진 트리와 높이

간선 기준 높이 h인 이진 트리에는 최대 2^(h+1)-1개의 노드가 있습니다. n ≥ 1인 이진 트리의 가능한 최소 높이는 ceil(log2(n+1))-1입니다. 노드 7개면 최소 높이는 2지만 8개는 최소 3입니다. 이 식은 가능한 최솟값일 뿐, 실제 삽입 순서가 나쁜 BST가 그 높이를 가진다는 보장은 아닙니다.

순회를 구현하기 전에 방문 순서를 정합니다

전위는 노드-왼쪽-오른쪽, 중위는 왼쪽-노드-오른쪽, 후위는 왼쪽-오른쪽-노드입니다. 같은 연결을 읽더라도 값을 기록하는 시점이 다릅니다. 계층을 부모부터 보여 줄 때는 전위, 자식 결과를 모아 부모를 처리할 때는 후위가 알맞습니다. 중위가 정렬 결과가 되는 것은 일반 이진 트리가 아니라 BST일 때입니다.

아래 코드는 {value,left,right} 형태의 유효한 이진 트리를 받습니다. 없는 자식은 null 또는 생략이며 빈 트리는 null입니다. 노드 값은 중복되어도 되지만 같은 노드 객체가 두 부모에 공유되거나 사이클을 만들면 안 됩니다. 그런 입력을 검증하는 그래프 알고리즘이 아니라 이미 트리인 구조의 순회입니다.

전체 코드를 tree.cjs로 저장하고 Node.js에서 node ./tree.cjs를 실행합니다. CommonJS 파일 한 개로 네 순서를 모두 출력합니다. 함수 자체는 재귀를 사용하지 않아 깊은 트리에서 JavaScript 호출 스택 한도를 직접 소모하지 않습니다. 다만 큰 객체의 JSON 직렬화 한도나 메모리 한도까지 없애는 것은 아닙니다.

'use strict';

function traversals(root) {
  const preorder = [];
  const inorder = [];
  const postorder = [];
  const breadthFirst = [];
  if (root == null) return { preorder, inorder, postorder, breadthFirst };

  const preStack = [root];
  while (preStack.length > 0) {
    const node = preStack.pop();
    preorder.push(node.value);
    if (node.right != null) preStack.push(node.right);
    if (node.left != null) preStack.push(node.left);
  }

  const inStack = [];
  let current = root;
  while (current != null || inStack.length > 0) {
    while (current != null) {
      inStack.push(current);
      current = current.left;
    }
    current = inStack.pop();
    inorder.push(current.value);
    current = current.right;
  }

  const postStack = [[root, false]];
  while (postStack.length > 0) {
    const [node, expanded] = postStack.pop();
    if (expanded) {
      postorder.push(node.value);
      continue;
    }
    postStack.push([node, true]);
    if (node.right != null) postStack.push([node.right, false]);
    if (node.left != null) postStack.push([node.left, false]);
  }

  const queue = [root];
  let head = 0;
  while (head < queue.length) {
    const node = queue[head];
    head += 1;
    breadthFirst.push(node.value);
    if (node.left != null) queue.push(node.left);
    if (node.right != null) queue.push(node.right);
  }
  return { preorder, inorder, postorder, breadthFirst };
}

module.exports = { traversals };

if (require.main === module) {
  const root = {
    value: 'A',
    left: { value: 'B', left: { value: 'D' }, right: { value: 'E' } },
    right: { value: 'C', right: { value: 'F' } }
  };
  console.log(JSON.stringify(traversals(root)));
}

실행 출력

{"preorder":["A","B","D","E","C","F"],"inorder":["D","B","E","A","C","F"],"postorder":["D","E","B","F","C","A"],"breadthFirst":["A","B","C","D","E","F"]}

스택은 아직 끝내지 않은 작업을 기억합니다

전위의 스택은 방문 예정 노드입니다. 스택은 마지막에 넣은 항목부터 꺼내므로 오른쪽을 먼저 넣고 왼쪽을 나중에 넣어야 왼쪽부터 처리합니다. 이 순서를 바꾸면 오른쪽 우선 전위가 되며, 단순한 성능 차이가 아니라 결과 계약이 바뀝니다.

중위의 내부 반복문은 왼쪽 끝까지 내려가며 노드를 보류합니다. 왼쪽에 더 갈 곳이 없어야 스택에서 노드를 꺼내 값을 기록하고 오른쪽으로 이동합니다. “스택 안의 노드는 왼쪽 작업을 기다리는 조상”이라는 의미를 잡으면 current와 스택을 모두 조건에 넣는 이유가 보입니다.

후위는 [노드, 확장 여부]를 쌓습니다. 처음 만났을 때 자기 자신을 expanded=true로 다시 넣은 뒤 자식들을 올립니다. 자식 작업이 모두 빠져나온 뒤 표시된 자신이 나타나므로 값은 마지막에 기록됩니다. 같은 노드를 두 번 작업 항목으로 다룰 뿐 결과에 두 번 넣지는 않습니다.

너비 우선은 먼저 발견한 노드부터 처리합니다. head를 증가시키고 자식은 queue 뒤에 넣으므로 같은 깊이의 기존 노드를 다음 깊이보다 먼저 읽습니다. 배열 앞을 shift하지 않는 대신 이미 읽은 항목도 배열에 남습니다. 따라서 이 코드의 큐 저장 공간은 최대 폭만이 아니라 전체 노드 수에 비례합니다.

BST의 순서와 MST의 비용을 혼동하지 않기

루트 30, 왼쪽 15(자식 10,20), 오른쪽 40(오른쪽 50)인 BST에서 25를 찾으면 30→15→20→없는 오른쪽으로 진행합니다. 비교할 때마다 반대 부분 트리를 배제할 수 있는 이유는 해당 부분 트리의 모든 키가 순서 조건을 만족하기 때문입니다. 그렇다고 매번 노드 수를 절반씩 버리는 것은 아니므로 편향되면 탐색은 O(n)입니다.

MST는 이미 주어진 가중 무방향 연결 그래프에서 간선을 선택하는 최적화 문제입니다. 예를 들어 AB=1, AC=4, BC=2, BD=5, CD=3이라면 AB,BC,CD를 고른 합 6이 최소 신장 트리입니다. 원래 그래프의 모든 정점을 잇되 사이클이 없는 n-1개 간선을 선택합니다. 가중치 동률이 있으면 최소 해가 여러 개일 수 있습니다.

위 예에서 크루스칼은 AB(1), BC(2), CD(3)를 받아들입니다. 프림을 A에서 시작해도 AB를 고르고, 경계 간선 중 BC, 다음 CD를 고릅니다. 출발점 하나에서 다른 정점까지의 거리 합이나 각각의 최단 경로를 최소화하는 문제가 아니므로 다익스트라와 목표를 섞지 않아야 합니다. 연결되지 않았다면 모든 정점을 잇는 트리는 없고 최소 신장 포리스트를 구합니다.

복잡도와 선택 기준

n은 노드 수, h는 간선 기준 높이입니다. 네 순회는 각 노드를 상수 번 다루므로 각각 O(n) 시간입니다. 전위·중위·표시를 둔 후위의 보조 스택은 O(h+1)이고, 이 코드의 BFS 큐는 O(n)입니다. 반환하는 네 배열이 각각 n개 값을 보관하므로 함수 전체 추가 공간은 O(n)입니다. 출력 공간을 빼고 BFS를 무조건 O(폭)이라고 적으면 실제 구현과 맞지 않습니다.

이진 트리의 모양을 다루는 문제라면 먼저 순회 순서를 고르고, 정렬된 동적 키 검색이면 BST를 검토하며, 연결 비용 최적화라면 가중 그래프와 MST 알고리즘을 선택합니다. 그래프의 기본 용어는 그래프 이론 기초, 행렬 표기는 행렬 기초에서 이어 볼 수 있습니다.

경계 확인과 연습

빈 트리, 루트만 있는 트리, 모든 값이 같은 트리, 오른쪽으로만 긴 트리를 따로 확인하세요. 값 중복은 방문을 생략할 이유가 되지 않습니다. 노드 식별과 노드에 저장한 값을 구별하는 습관은 이어지는 그래프 순회에서도 중요합니다.

JavaScript 트리 순회 연습: 깊이별 노드 묶기에서 직접 구현을 적용해 보세요.

삽입·탐색·삭제 구현은 JavaScript 이진 탐색 트리 구현으로 이어집니다.

함께 연습하고 확인할 자료

Binary Tree Level Order Traversal: 이진 트리를 레벨 순서로 방문하는 외부 연습입니다. 플랫폼의 노드 형식과 제출 인터페이스는 공식 페이지에서 확인하세요.

관련 개념 참고: Princeton Algorithms — Minimum Spanning Trees, Princeton — Binary Search Trees, BlogFlow — 기존 트리 자료구조 글 공식 자료와 문제 페이지는 2026년 9월 10일 확인했습니다. 외부 문제의 지문·예시를 복제하지 않고 이 글의 예제와 창작 문제를 별도로 구성했습니다.