C++ delete 키워드로 이진 트리 삭제하기 – 소멸자를 활용한 재귀적 메모리 해제

C++에서 동적으로 할당한 이진 트리를 해제할 때는 delete 키워드와 소멸자(destructor)를 활용하는 것이 가장 간단하고 확실한 방법입니다. 루트 노드에 대해 delete를 한 번만 호출하면, 소멸자가 재귀적으로 실행되면서 모든 자식 노드까지 순차적으로 메모리에서 해제됩니다.

이진 트리 노드 클래스 정의

먼저 int형 데이터와 왼쪽·오른쪽 자식 노드를 가리키는 포인터를 멤버로 갖는 클래스로 이진 트리를 정의합니다. leftChild와 rightChild는 btree_node 타입의 포인터이며, 여기서는 편의상 모든 멤버를 public으로 선언했습니다.

class btree_node {
    public:
        int data;
        btree_node* leftChild;
        btree_node* rightChild;
};

생성자(Constructor)

새 노드를 만들 때는 int 값을 매개변수로 받아 새로 생성된 노드의 data 멤버에 할당하는 생성자를 사용합니다. 이때 leftChild와 rightChild는 NULL로 초기화하여 자식이 없음을 명확히 합니다.

btree_node(int data){
    this->data = data;
    this->leftChild = NULL;
    this->rightChild = NULL;
}

소멸자(Destructor)

소멸자는 객체가 삭제될 때 자동으로 호출되며, delete 키워드를 사용해 왼쪽 자식과 오른쪽 자식을 먼저 삭제합니다. 자식 노드의 소멸자가 다시 자신의 자식들을 삭제하는 방식으로 재귀가 진행되므로, 별도의 순회 코드 없이도 트리 전체가 해제됩니다.

~btree_node(){
    delete leftChild;
    delete rightChild;
    cout << this->data << " is being deleted" << endl;
}

참고로 C++에서 delete는 NULL(nullptr) 포인터에 대해 호출해도 안전하므로, 자식이 없는 리프 노드에서도 별도의 조건 검사 없이 그대로 사용할 수 있습니다.

트리 삭제 실행하기

트리 전체의 삭제를 시작하려면 루트 노드에 대해 delete를 호출하면 됩니다. 루트가 삭제되면서 왼쪽과 오른쪽 서브트리도 함께 제거됩니다.

delete root;

전체 예제 코드

다음은 delete 키워드를 사용해 이진 트리를 삭제하는 전체 구현 예제입니다.

#include <iostream>
using namespace std;

class btree_node {
    public:
    int data;
    btree_node* leftChild;
    btree_node* rightChild;
    btree_node(int data){
        this->data = data;
        this->leftChild = NULL;
        this->rightChild = NULL;
    }
    ~btree_node(){
        delete leftChild;
        delete rightChild;
        cout << this->data << " is being deleted" << endl;
    }
};

int main(){
    btree_node* root = new btree_node(2);
    btree_node* node1 = new btree_node(4);
    btree_node* node2 = new btree_node(6);
    btree_node* node3 = new btree_node(8);
    btree_node* node4 = new btree_node(10);
    root->leftChild = node1;
    root->rightChild = node2;
    node1->leftChild = node3;
    node1->rightChild = node4;
    delete root;
    return 0;
}

실행 결과

위 코드를 컴파일하여 실행하면 다음과 같은 출력이 나옵니다.

8 is being deleted
10 is being deleted
4 is being deleted
6 is being deleted
2 is being deleted

출력 결과를 보면 값 8, 10처럼 리프 노드가 먼저 삭제되고, 그다음 부모 노드인 4, 마지막으로 루트인 2가 삭제되는 것을 확인할 수 있습니다. 즉, 소멸자가 후위 순회(post-order) 방식으로 동작하기 때문에 자식 노드가 모두 해제된 뒤에야 부모 노드가 안전하게 삭제되며, 메모리 누수 없이 트리 전체가 깔끔하게 정리됩니다.