트리(Tree): 계층 구조와 순회

트리는 부모와 자식 관계로 데이터를 조직한다. 파일 시스템, 문서 구조, 수식의 연산 순서를 표현할 때 사용한다. 루트를 제외한 노드는 부모가 정확히 하나이며 순환이 없다. 노드가 n개인 트리의 간선은 n-1개다. 트리 자체가 빠른 검색을 보장하지는 않는다. 값의 순서를 유지하는 이진 탐색 트리와 일반 이진 트리를 구분해야 한다.

용어와 높이

• 루트(root): 부모가 없는 노드.
• 잎(leaf): 자식이 없는 노드. 그 외 노드는 내부 노드다.
• 깊이(depth): 루트에서 노드까지 간선 수. 루트 깊이는 0이다.
• 높이(height): 노드에서 가장 깊은 잎까지 간선 수. 잎 높이는 0이다.
• 차수(degree): 해당 노드의 자식 수.
• 서브트리(subtree): 한 노드와 모든 자손이 이루는 트리.

예를 들어 A의 자식이 B·C이고 B의 자식이 D라면 D의 깊이는 2, A의 높이는 2다. A에서 D까지의 경로 길이는 간선 기준 2, 노드 기준 3이다. 문제마다 정의를 확인해야 한다. 빈 트리의 높이도 -1 또는 0으로 정의할 수 있으므로 구현 안에서 일관되게 사용한다.

자식 수가 일정하지 않은 일반 트리

왼쪽 자식·오른쪽 형제 표현은 각 노드에 포인터 두 개만 둔다. left는 첫 자식, right는 같은 부모의 다음 형제다. 이진 트리의 left/right와 이름은 같아도 의미가 다르다.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *left;   // 첫 자식
    struct Node *right;  // 다음 형제
} Node;

Node *createNode(int value) {
    Node *node = malloc(sizeof *node);
    if (node == NULL) return NULL;
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void addChild(Node *parent, Node *child) {
    if (parent == NULL || child == NULL) return;
    child->right = NULL;
    if (parent->left == NULL) {
        parent->left = child;
        return;
    }
    Node *last = parent->left;
    while (last->right != NULL) last = last->right;
    last->right = child;
}

void printTree(const Node *node, int depth) {
    if (node == NULL) return;
    for (int i = 0; i < depth; i++) printf("  ");
    printf("%d\n", node->value);
    for (const Node *child = node->left; child != NULL; child = child->right) {
        printTree(child, depth + 1);
    }
}

void freeTree(Node *node) {
    if (node == NULL) return;
    Node *child = node->left;
    while (child != NULL) {
        Node *next = child->right;
        freeTree(child);
        child = next;
    }
    free(node);
}

자식을 추가할 때 첫 자식이 없으면 바로 연결하고, 있으면 형제 연결의 끝을 찾는다. 이미 k명의 자식이 있다면 추가 비용은 O(k)다. 마지막 자식 포인터를 부모에 별도로 두면 O(1)로 줄일 수 있지만 공간이 늘어난다. 출력은 각 노드를 한 번씩 방문하므로 O(n) 시간, 재귀 스택은 높이 h에 비례하는 O(h) 공간이다. 해제 함수는 자식을 해제하기 전에 다음 형제를 보관한다. 해제한 노드의 포인터를 다시 읽지 않기 위해서다. 자식이 두 부모에 공유되거나 조상을 다시 가리키면 이 코드는 안전하지 않다.

수식 트리(Expression Tree)

수식 트리에서 숫자는 잎, 이항 연산자는 내부 노드다. 1 * 2 + (7 - 8)의 루트는 +이며, 왼쪽 서브트리는 *, 오른쪽 서브트리는 -다. 후위 순회 결과인 1 2 * 7 8 - +에는 괄호가 필요하지 않다. 아래 코드는 공백으로 구분한 후위 표기식을 스택으로 읽는다.

import java.util.ArrayDeque;
import java.util.Deque;

public class ExpressionTree {
    static class Node {
        final String token;
        final Node left, right;
        Node(String token, Node left, Node right) {
            this.token = token;
            this.left = left;
            this.right = right;
        }
    }

    static Node parse(String postfix) {
        Deque<Node> stack = new ArrayDeque<>();
        for (String token : postfix.trim().split("\\s+")) {
            if (token.matches("-?\\d+")) {
                stack.push(new Node(token, null, null));
            } else if ("+-*/".contains(token) && token.length() == 1) {
                if (stack.size() < 2) {
                    throw new IllegalArgumentException("피연산자가 부족합니다");
                }
                Node right = stack.pop();
                Node left = stack.pop();
                stack.push(new Node(token, left, right));
            } else {
                throw new IllegalArgumentException("알 수 없는 토큰: " + token);
            }
        }
        if (stack.size() != 1) {
            throw new IllegalArgumentException("올바른 후위 수식이 아닙니다");
        }
        return stack.pop();
    }

    static double evaluate(Node node) {
        if (node.left == null && node.right == null) {
            return Double.parseDouble(node.token);
        }
        double left = evaluate(node.left);
        double right = evaluate(node.right);
        switch (node.token) {
            case "+": return left + right;
            case "-": return left - right;
            case "*": return left * right;
            case "/":
                if (right == 0) throw new ArithmeticException("0으로 나눌 수 없습니다");
                return left / right;
            default: throw new IllegalArgumentException("지원하지 않는 연산");
        }
    }

    public static void main(String[] args) {
        Node root = parse("1 2 * 7 8 - +");
        System.out.println(evaluate(root)); // 1.0
    }
}

숫자 1과 2를 넣은 뒤 *를 만나면 오른쪽 2, 왼쪽 1을 꺼내 *의 자식으로 붙인다. 7과 8을 -로 묶은 뒤 마지막 +가 두 서브트리를 합친다. 스택에 끝내 노드가 하나만 남아야 올바른 식이다. 구성과 계산은 각각 O(n) 시간, 구성 공간은 O(n), 계산 재귀 공간은 O(h)다. 이 예제는 정수와 이항 연산자만 다룬다. 일반 중위 수식을 입력받으려면 토큰화, 괄호, 연산자 우선순위를 별도로 처리해야 한다.

이진 트리(Binary Tree)

각 노드의 왼쪽·오른쪽 자식은 각각 최대 하나다. 자식이 하나만 있을 때도 왼쪽인지 오른쪽인지 구별한다.

형태	조건	쓰임
포화 이진 트리(perfect)	내부 노드는 자식 둘, 모든 잎의 깊이는 같음	노드 수와 높이의 기준
완전 이진 트리(complete)	마지막 층만 비어 있을 수 있고 왼쪽부터 채움	배열 기반 힙
정 이진 트리(full/proper)	자식 수가 0 또는 2	이항 수식 구조
균형 이진 트리	높이 차이를 제한하는 규칙을 유지	검색 높이 제어

루트에 왼쪽 자식만 있는 트리는 완전 이진 트리이지만 정 이진 트리는 아니다. 한쪽으로만 계속 자식이 달리면 높이는 n-1이 된다. 균형이 필요한 검색에서는 AVL 또는 레드블랙 트리처럼 높이 제어 규칙을 유지해야 한다.

전위·중위·후위 순회

예제 트리의 루트가 1, 왼쪽은 2(자식 4·5), 오른쪽은 3(자식 6·7)이라고 하자. 그림의 노드 배치와 무관하게 다음 표는 이 예제 트리의 순서다.

방식	규칙	결과	대표 용도
전위	루트 → 왼쪽 → 오른쪽	1 2 4 5 3 6 7	부모부터 직렬화
중위	왼쪽 → 루트 → 오른쪽	4 2 5 1 6 3 7	이진 탐색 트리의 정렬 순서
후위	왼쪽 → 오른쪽 → 루트	4 5 2 6 7 3 1	자식 처리 후 부모 계산·해제

다음 C 함수는 출력문 위치만 바꾸어 세 순회를 구현한다. 자식이 없는 곳에서 재귀가 끝나므로 빠뜨리거나 중복 방문하는 노드가 없다.

#include <stdio.h>

typedef struct TreeNode {
    char data;
    struct TreeNode *left, *right;
} TreeNode;

void preorder(const TreeNode *node) {
    if (node == NULL) return;
    printf("%c ", node->data);
    preorder(node->left);
    preorder(node->right);
}

void inorder(const TreeNode *node) {
    if (node == NULL) return;
    inorder(node->left);
    printf("%c ", node->data);
    inorder(node->right);
}

void postorder(const TreeNode *node) {
    if (node == NULL) return;
    postorder(node->left);
    postorder(node->right);
    printf("%c ", node->data);
}

각 노드를 한 번 방문하므로 시간은 O(n)이다. 재귀 스택은 높이만큼 쌓여 O(h)이고, 편향 트리에서는 O(n)까지 늘어난다. 이 순회는 모든 값을 읽는 작업이다. 단일 키 검색을 빠르게 하려면 왼쪽 키 < 부모 키 < 오른쪽 키의 탐색 트리 불변식과 균형 관리가 필요하다. 또 트리 노드를 직접 연결할 때는 순환이나 자식 공유를 만들지 않아야 한다. 그런 구조에서는 재귀가 끝나지 않거나 동일 노드가 여러 번 처리된다.