C++에서 이진 트리 데이터 구조 구현

C++에서는 값과 두 개의 자식 링크를 가진 노드 struct로 이진 트리를 표현할 수 있습니다. 아래 예제에서는 작은 트리를 만들고, 노드 수와 간선 기준 높이를 계산한 다음 inorder 순회로 값을 출력합니다.

노드 struct로 이진 트리 표현하기

이진 트리의 각 노드는 자식을 최대 두 개까지 가질 수 있으며, 일반적으로 left와 right라고 부릅니다. struct는 멤버가 기본적으로 공개인 클래스 형식이므로 이처럼 작은 자료 구조를 표현하기에 편리합니다. 각 노드는 정수를 저장하고 std::unique_ptr로 자식 노드를 소유합니다. 널 포인터는 자식 링크가 없음을 나타냅니다. 널 포인터 자체가 리프 노드라는 뜻은 아닙니다. 리프 노드는 두 자식 링크가 모두 널인 노드입니다.

정이진 트리에서는 모든 노드의 자식 수가 0개 또는 2개입니다. 포화 이진 트리는 정이진 트리이면서 모든 리프의 깊이가 같습니다. 아래에서 만드는 예제 트리는 정이진 트리이지만 완전 이진 트리는 아닙니다. 마지막 레벨에서 뒤쪽 노드보다 앞선 자리가 비어 있기 때문입니다. 이 용어들은 서로 다른 트리 모양을 가리키므로 혼용하지 마세요.

작은 이진 트리 만들기

프로그램은 순회 순서를 쉽게 따라갈 수 있도록 다음과 같은 모양으로 트리를 만듭니다. 8 (left: 3, right: 10 (left: 9, right: 14)).

std::make_unique는 각 노드를 만들고 그 노드를 소유하는 포인터를 반환합니다. 포인터를 자식에 이동하면 소유권도 함께 이전됩니다. 따라서 루트가 트리 전체를 소유하고, 루트가 범위를 벗어나면 노드가 자동으로 해제됩니다. 이렇게 하면 일반 포인터로 new를 호출했을 때 필요한 수동 정리를 피할 수 있습니다.

아래 예제를 실행해 보세요. 코드와 실행 결과에 표시되는 size, height, inorder 레이블은 바이트 단위로 보존되므로 영어로 나타납니다.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

#include <iostream>
#include <memory>

struct BinTreeNode {
    int data;
    std::unique_ptr<BinTreeNode> left;
    std::unique_ptr<BinTreeNode> right;

    explicit BinTreeNode(int value) : data(value) {}
};

int treeSize(const BinTreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    return 1 + treeSize(node->left.get()) + treeSize(node->right.get());
}

int treeHeight(const BinTreeNode* node) {
    if (node == nullptr) {
        return -1;
    }
    const int leftHeight = treeHeight(node->left.get());
    const int rightHeight = treeHeight(node->right.get());
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

void printData(const BinTreeNode* node) {
    if (node == nullptr) {
        return;
    }
    printData(node->left.get());
    std::cout << node->data << ' ';
    printData(node->right.get());
}

int main() {
    auto root = std::make_unique<BinTreeNode>(8);
    root->left = std::make_unique<BinTreeNode>(3);
    root->right = std::make_unique<BinTreeNode>(10);
    root->right->left = std::make_unique<BinTreeNode>(9);
    root->right->right = std::make_unique<BinTreeNode>(14);

    std::cout << "size = " << treeSize(root.get()) << '\n';
    std::cout << "height = " << treeHeight(root.get()) << '\n';
    std::cout << "inorder = ";
    printData(root.get());
    std::cout << '\n';
}

이 함수들은 노드 포인터를 인수로 받지만 소유권을 가져가지는 않습니다. root.get()을 전달하면 소유 포인터인 unique_ptr가 트리의 수명을 관리하는 동안 함수가 트리에 접근할 수 있습니다. 같은 재귀 정의는 어떤 모양의 트리에도 적용됩니다.

노드 수 세기와 트리 높이 계산하기

treeSize는 비어 있는 하위 트리에 대해 0을 반환합니다. 하위 트리가 있으면 현재 노드 하나를 세고 양쪽 자식 하위 트리의 크기를 더합니다. treeHeight는 비어 있는 하위 트리에 대해 -1을 반환한 다음, 두 자식의 높이 중 더 큰 값에 1을 더합니다. 이 기준에서 높이는 루트에서 리프까지 가장 긴 경로의 간선 수입니다. 따라서 리프의 높이는 0이고 위 예제 트리의 높이는 2입니다. 높이를 노드 수로 세는 정의도 있어 이 경우 리프의 높이는 1입니다. 한 가지 기준을 정해 일관되게 사용하세요.

inorder 순회로 노드 출력하기

printData는 왼쪽 하위 트리를 방문하고 현재 값을 출력한 다음 오른쪽 하위 트리를 방문합니다. 이것이 inorder 순회입니다. 이진 탐색 트리에서는 값이 정렬된 순서로 출력되지만, 일반 이진 트리에서는 이 순회 순서를 따를 뿐입니다. 자세한 내용은 inorder 순회 안내를 참조하세요.

재귀 흐름을 따라가려면 각 노드에서 함수가 어떻게 동작하는지 살펴보세요. 함수는 더 내려갈 자식이 없을 때까지 왼쪽으로 이동하고, 부모로 돌아오면서 값을 출력한 뒤 오른쪽 하위 트리를 처리합니다. 따라서 예제의 값은 3 8 9 10 14 순서로 나타납니다. 트리에는 노드가 다섯 개 있고 간선 기준 높이는 2입니다. 이 프로그램은 단독으로 실행할 수 있습니다. 노드 값의 형식을 바꾸거나 연산을 추가할 때도 소유권과 선택한 높이 기준을 명확히 유지하세요.