자료구조 트리 기본 개념

데이터를 계층적으로 관리하는 비선형 자료구조인 트리(Tree)의 개념과 구현 방법을 정리한다.

노드 구조 설계

이진 트리(Binary Tree)를 기준으로 각 노드는 데이터와 두 개의 자식 노드 참조를 가진다.

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

이진 트리 구현 및 삽입

데이터를 계층적으로 연결하여 트리를 구성한다.

class BinaryTree {
    Node root;

    public BinaryTree() {
        root = null;
    }

    // 간단한 삽입 예시 (수동 연결)
    public void createSampleTree() {
        root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
    }
}

트리 순회 (Traversal)

재귀 함수를 사용하여 모든 노드를 방문하는 세 가지 방식이 있다.

// 전위 순회 (Root -> Left -> Right)
public void preOrder(Node node) {
    if (node != null) {
        System.out.print(node.value + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
}

// 중위 순회 (Left -> Root -> Right)
public void inOrder(Node node) {
    if (node != null) {
        inOrder(node.left);
        System.out.print(node.value + " ");
        inOrder(node.right);
    }
}

// 후위 순회 (Left -> Right -> Root)
public void postOrder(Node node) {
    if (node != null) {
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.value + " ");
    }
}

주요 용어 및 특징

• 루트(Root): 최상위 노드.
• 부모/자식(Parent/Child): 상하 관계로 연결된 노드들.
• 리프(Leaf): 자식이 없는 단말 노드.
• 깊이(Depth): 루트에서 특정 노드까지의 간선 수.
• 높이(Height): 루트에서 가장 먼 리프 노드까지의 간선 수.

P.S

트리는 계층적 데이터를 표현하는 데 최적화되어 있으며, 이진 탐색 트리(BST), 힙(Heap), 트라이(Trie) 등 다양한 응용 자료구조의 기반이 된다.

재귀적 특성을 이해하는 것이 구현의 핵심인 것 같다.

웨이호프