트리와 이진 트리

트리 (Tree)란?

트리는 하나의 노드에서 시작해 나무가 가지를 뻗듯이 뻗어나가는 비선형 자료구조다.
계층 구조를 표현하기에 적합하며, 파일 시스템, 조직도, DOM 구조 등에서 널리 사용된다.

        A          ← 루트 노드
       / \
      B   C        ← A의 자식 노드
     /|\   \
    D E F   G      ← 터미널 노드(리프 노드)

트리의 구성 요소

용어	설명
노드(Node)	데이터를 담는 가장 작은 단위
간선(Edge)	노드와 노드를 연결하는 선
루트 노드(Root)	트리의 최상위 노드. 부모가 없다
부모 노드(Parent)	간선으로 연결된 두 노드 중 상위 노드
자식 노드(Child)	간선으로 연결된 두 노드 중 하위 노드
터미널 노드(Terminal)	자식이 없는 노드. 리프(Leaf) 노드라고도 함
인터널 노드(Internal)	터미널 노드를 제외한 모든 노드
서브 트리(Subtree)	트리 내의 작은 트리. 어떤 노드를 루트로 하는 부분 트리

 

이진 트리 (Binary Tree)

각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리다. 자식 노드는 왼쪽 자식(left child)과 오른쪽 자식(right child)으로 구분된다.

        1
       / \
      2   3
     / \
    4   5

이진 트리는 구현이 단순하고 탐색 효율이 좋아 가장 널리 사용되는 트리 형태다.

 

트리의 레벨과 높이

Level 0:        A           Height = 2
               / \
Level 1:      B   C
             /
Level 2:    D

• 레벨(Level): 루트 노드를 레벨 0(또는 1)으로 시작해 아래로 내려갈수록 1씩 증가한다.
• 높이(Height): 트리에서 가장 깊은 레벨. 즉, 루트에서 가장 먼 터미널 노드까지의 거리다.

 

이진 트리의 종류

포화 이진 트리 (Perfect Binary Tree)

모든 레벨이 노드로 꽉 찬 이진 트리.
모든 터미널 노드가 같은 레벨에 있고, 모든 인터널 노드가 두 개의 자식을 가진다.

포화 이진 트리 O          포화 이진 트리 X

       1                       1
      / \                     / \
     2   3                   2   3
    / \ / \                 / \
   4  5 6  7               4   5

• 레벨 k의 노드 수: 2^k
• 높이 h인 포화 이진 트리의 총 노드 수: 2^(h+1) - 1

 

완전 이진 트리 (Complete Binary Tree)

마지막 레벨을 제외한 모든 레벨이 채워져 있고, 마지막 레벨은 왼쪽부터 순서대로 채워진 트리.

완전 이진 트리 O          완전 이진 트리 X

       1                       1
      / \                     / \
     2   3                   2   3
    / \                       \
   4   5                       4

완전 이진 트리는 배열로 효율적으로 표현할 수 있어 힙(Heap) 구현에 사용된다.

 

이진 트리 순회 (Binary Tree Traversal)

트리의 모든 노드를 한 번씩 방문하는 것을 순회라고 한다. 방문 순서에 따라 세 가지로 나뉜다.

        1
       / \
      2   3
     / \
    4   5

1. 전위 순회 (Preorder)

루트 → 왼쪽 → 오른쪽 순서로 방문한다.

• 방문 순서: 1 → 2 → 4 → 5 → 3
• 트리를 복사하거나 전체 구조를 출력할 때 유용하다.

2. 중위 순회 (Inorder)

왼쪽 → 루트 → 오른쪽 순서로 방문한다.

• 방문 순서: 4 → 2 → 5 → 1 → 3
• 이진 탐색 트리에서 오름차순 정렬된 결과를 얻을 때 사용한다.

3. 후위 순회 (Postorder)

왼쪽 → 오른쪽 → 루트 순서로 방문한다.

• 방문 순서: 4 → 5 → 2 → 3 → 1
• 트리를 삭제할 때 유용하다. 자식을 먼저 처리한 후 부모를 처리해야 하기 때문이다.

 

구현

BinaryTree 클래스

class BinaryTree {
  constructor(data, leftTree = null, rightTree = null) {
    this.data = data;
    this.leftTree = leftTree;
    this.rightTree = rightTree;
  }
  // ...
}

각 노드는 data, leftTree, rightTree 세 가지 속성을 가진다.

 

주요 메서드

메서드	설명
getData()	현재 노드의 데이터 반환
setData(data)	현재 노드의 데이터 설정
getLeftSubTree()	왼쪽 서브트리 반환
getRightSubTree()	오른쪽 서브트리 반환
setLeftSubTree(tree)	왼쪽 서브트리 설정
setRightSubTree(tree)	오른쪽 서브트리 설정

 

순회 메서드

// 전위 순회: 루트 → 왼쪽 → 오른쪽
preOrderTraversal(tree) {
  if (tree == null) return;
  console.log(tree.data);                         // 1. 루트 방문
  this.preOrderTraversal(tree.getLeftSubTree());  // 2. 왼쪽 순회
  this.preOrderTraversal(tree.getRightSubTree()); // 3. 오른쪽 순회
}

// 중위 순회: 왼쪽 → 루트 → 오른쪽
inOrderTraversal(tree) {
  if (tree == null) return;
  this.inOrderTraversal(tree.getLeftSubTree());   // 1. 왼쪽 순회
  console.log(tree.data);                         // 2. 루트 방문
  this.inOrderTraversal(tree.getRightSubTree());  // 3. 오른쪽 순회
}

// 후위 순회: 왼쪽 → 오른쪽 → 루트
postOrderTraversal(tree) {
  if (tree == null) return;
  this.postOrderTraversal(tree.getLeftSubTree()); // 1. 왼쪽 순회
  this.postOrderTraversal(tree.getRightSubTree());// 2. 오른쪽 순회
  console.log(tree.data);                         // 3. 루트 방문
}

세 순회 메서드 모두 재귀적으로 구현되며, console.log(tree.data) 위치만 다르다.

 

사용 예제

// 트리 생성
let tree1 = new BinaryTree(1);
let tree2 = new BinaryTree(2);
let tree3 = new BinaryTree(3);
let tree4 = new BinaryTree(4);
let tree5 = new BinaryTree(5);

// 트리 구조 설정
tree1.setLeftSubTree(tree2);
tree1.setRightSubTree(tree3);
tree2.setLeftSubTree(tree4);
tree2.setRightSubTree(tree5);

// 순회 실행
tree1.preOrderTraversal(tree1);  // 1, 2, 4, 5, 3
tree1.inOrderTraversal(tree1);   // 4, 2, 5, 1, 3
tree1.postOrderTraversal(tree1); // 4, 5, 2, 3, 1