C++에서 한 번의 순회만으로 이진 트리 밀도 계산하기

이진 트리(binary tree)의 밀도(density)는 트리의 크기(size)를 높이(height)로 나누어 계산합니다.

이진 트리 밀도 = 크기 / 높이

여기서 '크기'는 트리에 포함된 전체 노드의 개수를 의미하고, '높이'는 루트 노드에서 가장 깊은 리프 노드까지의 경로 길이를 의미합니다. 일반적으로 크기와 높이를 각각 구하려면 두 번의 순회가 필요하지만, 참조(reference)를 활용하면 한 번의 순회만으로 두 값을 동시에 얻을 수 있습니다.

1. 트리 노드 구조체 정의

먼저 데이터와 왼쪽·오른쪽 자식 노드를 담고 있는 트리 노드를 나타내는 구조체를 정의합니다. 가장 처음 생성되는 노드는 루트(root) 노드가 되며, 그 이후에 생성되는 노드들은 모두 자식(child) 노드입니다.

struct Node {
    int data;
    struct Node *leftChild, *rightChild;
};

2. 노드 생성 함수 만들기

다음으로 정수 값을 전달받아 해당 노드의 data 멤버에 할당하는 createNode(int data) 함수를 작성합니다. 이 함수는 새로 생성된 Node 구조체의 포인터를 반환하며, 새 노드의 왼쪽과 오른쪽 자식은 NULL로 초기화됩니다.

Node* createNode(int data){
    Node* node = new Node;
    node->data = data;
    node->leftChild = node->rightChild = NULL;
    return node;
}

3. 밀도를 계산하는 treeDensity 함수

treeDensity(Node *root) 함수는 루트 노드를 전달받아 NULL 여부를 먼저 확인합니다. 그다음 size 변수를 선언하고 0으로 초기화한 뒤, heightAndSize(root, size) 함수의 반환값을 height 변수에 저장합니다. 마지막으로 height와 size를 float 형태로 나눈 결과를 반환합니다.

float treeDensity(Node* root){
    if (root == NULL)
        return 0;
    int size = 0;
    int height = heightAndSize(root, size);
    return (float)size/height;
}

4. 높이와 크기를 동시에 구하는 heightAndSize 함수

heightAndSize(Node* node, int &size) 함수는 루트 노드와 size 변수에 대한 참조를 함께 전달받습니다. 노드가 NULL이면 0을 반환하고, 각 서브트리(subtree)의 높이를 재귀적으로 계산하면서 재귀 호출이 진행될 때마다 size를 1씩 증가시킵니다. 최종적으로 왼쪽과 오른쪽 서브트리 중 더 큰 값에 1을 더해 반환합니다.

핵심은 size를 참조(&)로 전달하기 때문에 별도의 순회 없이 재귀 과정에서 노드 개수가 함께 누적된다는 점입니다. 이 덕분에 단 한 번의 순회로 높이와 크기를 모두 구할 수 있습니다.

int heightAndSize(Node* node, int &size){
    if (node==NULL)
        return 0;
    int left = heightAndSize(node->leftChild, size);
    int right = heightAndSize(node->rightChild, size);
    size++;
    return (left > right) ? ++left : ++right;
}

전체 예제 코드

지금까지 설명한 내용을 바탕으로, 한 번의 순회만으로 이진 트리의 밀도를 구하는 전체 구현은 다음과 같습니다.

#include<iostream>
using namespace std;
struct Node{
    int data;
    Node *leftChild, *rightChild;
};
Node* createNode(int data){
    Node* node = new Node;
    node->data = data;
    node->leftChild = node->rightChild = NULL;
    return node;
}
int heightAndSize(Node* node, int &size){
    if (node==NULL)
        return 0;
    int left = heightAndSize(node->leftChild, size);
    int right = heightAndSize(node->rightChild, size);
    size++;
    return (left > right) ? ++left : ++right;
}
float treeDensity(Node* root){
    if (root == NULL)
        return 0;
        int size = 0;
        int height = heightAndSize(root, size);
    return (float)size/height;
}
int main(){
    Node* root = createNode(7);
    root->leftChild = createNode(9);
    root->rightChild = createNode(11);
    cout<< "The density of the above given binary tree is "<<treeDensity(root);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 나타납니다.

The density of the above given binary tree is 1.5

예제 트리는 총 3개의 노드(크기 = 3)와 높이 2를 가지므로, 밀도는 3 ÷ 2 = 1.5가 됩니다. 이처럼 참조 변수를 활용한 단일 순회 기법을 사용하면 시간 복잡도 O(n) 안에 효율적으로 이진 트리의 밀도를 계산할 수 있습니다.