이진 트리는 계층적 데이터를 표현하는 대표적인 비선형 자료구조로, 각 노드가 최대 두 개의 자식을 가지는 구조를 말합니다. 분할 정복의 "반으로 나누기" 전략을 직관적으로 구현할 수 있어 다양한 알고리즘의 기반이 됩니다.

노드 구조와 기본 개념

이진 트리의 기본 단위인 노드는 데이터 값과 두 개의 자식 참조로 구성됩니다. 부모-자식 관계를 통해 하위 트리가 형성되며, 특정 노드를 기준으로 왼쪽에 연결된 부분을 왼쪽 서브트리, 오른쪽에 연결된 부분을 오른쪽 서브트리라 부릅니다.

class Node {
    int data;
    Node lChild;
    Node rChild;

    Node(int value) {
        this.data = value;
    }
}

리프 노드를 제외한 모든 노드는 하나 이상의 자식을 보유하며, 이를 통해 트리의 전체 구조가 확장됩니다.

트리 구성 방법

링크드 리스트와 유사한 방식으로 노드를 생성하고 연결하여 트리를 구축합니다.

Node root = new Node(10);
Node leftNode = new Node(20);
Node rightNode = new Node(30);
Node llNode = new Node(40);
Node lrNode = new Node(50);

root.lChild = leftNode;
root.rChild = rightNode;
leftNode.lChild = llNode;
leftNode.rChild = lrNode;

노드 삽입과 제거

노드 간의 연결만 조작하면 삽입과 삭제를 수행할 수 있습니다.

Node newNode = new Node(5);

// 노드 삽입: root와 leftNode 사이
root.lChild = newNode;
newNode.lChild = leftNode;

// 노드 제거: newNode를 제거하고 원래 구조 복원
root.lChild = leftNode;

삽입 시에는 트리의 논리적 관계가 변할 수 있으므로 주의가 필요하며, 삭제는 일반적으로 해당 노드와 그 하위 전체를 제거하는 의미로 사용됩니다.

주요 이진 트리 유형

트리 순회 기법

너비 우선 탐색 (BFS / Level-Order)

상위 레벨부터 하위 레벨로, 각 레벨 내에서는 왼쪽에서 오른쪽으로 노드를 방문합니다. 큐를 활용하여 구현하며, "물결처럼 퍼져 나가는" 탐색 패턴을 보입니다.

List<Integer> bfsTraversal(Node root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<Node> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        Node current = queue.poll();
        result.add(current.data);
        
        if (current.lChild != null) queue.offer(current.lChild);
        if (current.rChild != null) queue.offer(current.rChild);
    }
    return result;
}

깊이 우선 탐색 (DFS)

재귀를 활용한 세 가지 대표적인 DFS 방식이 있습니다. 각 방식은 노드를 방문하는 시점의 차이에 따라 구분됩니다.

// 전위 순회: 현재 노드 -> 왼쪽 -> 오른쪽
void traversePre(Node node, List<Integer> output) {
    if (node == null) return;
    output.add(node.data);
    traversePre(node.lChild, output);
    traversePre(node.rChild, output);
}

// 중위 순회: 왼쪽 -> 현재 노드 -> 오른쪽
void traverseIn(Node node, List<Integer> output) {
    if (node == null) return;
    traverseIn(node.lChild, output);
    output.add(node.data);
    traverseIn(node.rChild, output);
}

// 후위 순회: 왼쪽 -> 오른쪽 -> 현재 노드
void traversePost(Node node, List<Integer> output) {
    if (node == null) return;
    traversePost(node.lChild, output);
    traversePost(node.rChild, output);
    output.add(node.data);
}

전위 순회는 노드를 먼저 처리하므로 복사나 직렬화에, 중위 순회는 이진 탐색 리에서 정렬된 결과를 얻는 데, 후위 순회는 하위 트리를 먼저 처리해야 하는 삭제 연산 등에 각각 유리하게 활용됩니다.