트리 (Tree)

트리는 값을 가진 노드(Node)와 이 노드들을 연결하는 간선(Edge)로 이루어진 계층형 자료구조이다.
가족 관계도나 조직도처럼, 데이터의 계층적인 관계를 표현하는 데 매우 효과적이다.

🔗 Tree의 종류 설명 영상

용어 정리

용어	설명
노드 (Node)	트리를 구성하는 기본 요소. (데이터)
간선 (Edge)	노드와 노드를 연결하는 선.
루트 (Root)	트리 구조의 시작점이 되는 최상위 노드.
부모/자식 (Parent/Child)	간선으로 직접 연결된 두 노드의 관계.

특징

• 사이클이 없다 (No Cycles): 트리에는 순환하는 경로가 존재할 수 없다. (만약 사이클이 있다면, 그것은 그래프이다.)
• 하나의 유일한 경로: 루트에서 특정 노드로 가는 경로는 항상 하나뿐이다.
• 노드와 간선의 관계: 노드의 개수가 N개일 때, 간선의 개수는 항상 N-1개이다.

트리 순회 방식

트리를 순회하는 방식은 총 4가지가 있다.

전위 순회 (Pre-order)

루트(Root)를 먼저 방문하고, 그 후 자식 노드를 방문하는 방식이다.

루트 → 왼쪽 자식 → 오른쪽 자식
1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14

중위 순회 (In-order)

왼쪽 하위 트리를 방문 후 루트(Root)를 방문하는 방식이다.

왼쪽 자식 → Root → 오른쪽 자식
8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7

후위 순회(post-order)

왼쪽 하위 트리부터 하위를 모두 방문 후 루트(Root)를 방문하는 방식이다.

왼쪽 자식 → 오른쪽 자식 → Root
8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1

레벨 순회(level-order)

루트(Root)부터 계층 별로 방문하는 방식이다.

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14

전위 순회 (Pre-order) 구현해보기

class Node {
  constructor(data) {
    this.data = data; // 노드가 가진 값
    this.children = []; // 자식 노드를 담을 배열
  }

  add(data) {
    this.children.push(new Node(data));
  }
}

class Tree {
  constructor() {
    this.root = null;
  }

  // 전위 순회를 시작하고, 결과를 배열로 반환하는 메서드
  traversePreOrder() {
    const result = [];

    // 실제 순회를 담당하는 재귀 함수
    function traverse(node) {
      // 1. 루트(현재 노드)를 먼저 처리한다. (결과 배열에 추가)
      result.push(node.data);

      // 2. 자식들을 순서대로 방문하며 재귀 호출한다.
      for (const child of node.children) {
        traverse(child);
      }
    }

    if (this.root) {
      traverse(this.root);
    }

    return result;
  }
}

//트리와 루트 노드 생성
const tree = new Tree();
tree.root = new Node('A'); // 루트는 'A'

/*
트리 구조
   A
 /   \
B     C
|     |
D     E
*/
tree.root.add('B');
tree.root.add('C');
tree.root.children[0].add('D'); // B의 자식으로 D 추가
tree.root.children[1].add('E'); // C의 자식으로 E 추가

// 전위 순회 실행
const traversalResult = tree.traversePreOrder();
// A -> B -> D -> C -> E
console.log(traversalResult.join(' -> '));