C++ 배열로 구현하는 이진 트리 완벽 가이드

이진 트리(Binary Tree)는 트리의 각 노드가 최대 두 개의 자식 노드만 가질 수 있는 특수한 형태의 트리입니다. 이 두 자식 노드는 각각 왼쪽 자식(left child)과 오른쪽 자식(right child)이라고 부릅니다.

이진 트리의 표현 방법

트리를 컴퓨터 메모리에 표현하는 방법은 크게 두 가지가 있습니다.

연결 리스트를 이용한 동적 노드 표현 — 각 노드가 포인터로 자식을 가리키는 방식
배열을 이용한 순차 표현 — 인덱스 계산으로 부모·자식 관계를 파악하는 방식

이 글에서는 그중 배열을 활용한 이진 트리 표현 방법을 자세히 알아보겠습니다. 배열로 이진 트리를 표현하려면 먼저 트리의 각 노드에 번호를 매겨야 합니다. 이 번호 매기기는 0부터 (n-1)까지 시작할 수도 있고, 1부터 n까지 시작할 수도 있습니다.

0 기반 인덱싱 (0-index based)

부모 노드의 인덱스를 p라고 할 때, 다음과 같은 관계가 성립합니다.

루트 노드: 인덱스 0
왼쪽 자식: 인덱스 1
오른쪽 자식: 인덱스 2
부모가 p일 때 왼쪽 자식: (2 × p) + 1
부모가 p일 때 오른쪽 자식: (2 × p) + 2

1 기반 인덱싱 (1-index based)

부모 노드의 인덱스를 p라고 할 때, 다음과 같은 관계가 성립합니다.

루트 노드: 인덱스 1
왼쪽 자식: 인덱스 2
오른쪽 자식: 인덱스 3
부모가 p일 때 오른쪽 자식: 2 × p
부모가 p일 때 왼쪽 자식: (2 × p) + 1

C++ 예제 코드

아래는 0 기반 인덱싱을 사용해 크기 10의 문자 배열에 이진 트리를 구현한 C++ 코드입니다. 루트 설정, 왼쪽·오른쪽 자식 삽입, 트리 순회 기능을 포함하고 있습니다.

#include<bits/stdc++.h>
using namespace std;
char tree[10];

// 루트 노드 설정
int rootnode(char key){
    if(tree[0] != '\0')
        cout<<"Tree already had root";
    else
        tree[0] = key;
    return 0;
}

// 왼쪽 자식 노드 삽입
int leftchild(char key, int parent){
    if(tree[parent] == '\0')
        cout <<"\nCan't set child at"<<(parent * 2) + 1<<" , no parent found";
    else
        tree[(parent * 2) + 1] = key;
    return 0;
}

// 오른쪽 자식 노드 삽입
int rightchild(char key, int parent){
    if(tree[parent] == '\0')
        cout<<"\nCan't set child at"<<(parent * 2) + 2<<" , no parent found";
    else
        tree[(parent * 2) + 2] = key;
    return 0;
}

// 트리 순회 및 출력
int traversetree(){
    cout << "\n";
    for(int i = 0; i < 10; i++){
        if(tree[i] != '\0')
            cout<<tree[i];
        else
            cout<<"-";
    }
    return 0;
}

int main(){
    rootnode('A');
    rightchild('C', 2);
    leftchild('D', 0);
    rightchild('E', 1);
    rightchild('F', 2);
    traversetree();
    return 0;
}

실행 결과

Can't set child at6 , no parent found
Can't set child at6 , no parent found
AD--E-----

결과 분석

실행 결과를 살펴보면 몇 가지 흥미로운 점을 확인할 수 있습니다.

rightchild('C', 2) 호출 시, 인덱스 2에는 아직 아무 노드도 존재하지 않으므로(부모 없음) "no parent found"라는 오류 메시지가 출력되며 삽입이 거부됩니다. 마찬가지로 rightchild('F', 2) 역시 같은 이유로 실패합니다.

성공적으로 삽입된 노드들을 보면 다음과 같습니다.

'A' → 인덱스 0 (루트 노드)
'D' → 인덱스 1 ('A'의 왼쪽 자식)
'E' → 인덱스 4 ('D'의... 즉 인덱스 1의 오른쪽 자식, (2×1)+2 = 4)

최종 출력 AD--E-----에서 비어있는 위치는 '-'로 표시됩니다. 이처럼 배열 기반 표현은 구현이 간단하고 인덱스 연산만으로 부모·자식 접근이 가능하다는 장점이 있지만, 트리가 성긴(sparse) 경우 빈 공간이 많아져 메모리 낭비가 발생할 수 있다는 단점도 함께 기억해두어야 합니다.