C++ 이진 트리(Binary Tree)에서 노드 삭제하는 방법

이진 트리에서 노드를 삭제할 때는 일반적으로 삭제하려는 노드의 값을 트리에서 가장 깊고 오른쪽에 있는 노드(마지막 노드)의 값으로 대체한 뒤, 해당 마지막 노드를 제거하는 방식을 사용합니다.

트리 노드 구조체 정의

먼저 데이터와 왼쪽·오른쪽 자식 노드를 담고 있는 트리 노드를 표현하는 구조체를 정의합니다. 처음 생성되는 노드라면 루트(root) 노드가 되고, 그렇지 않으면 자식 노드가 됩니다.

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

새 노드 생성 함수

다음으로 newNode(int data) 함수를 만듭니다. 이 함수는 int 값을 인자로 받아 노드의 data 멤버에 할당하고, 새로 생성된 노드의 왼쪽과 오른쪽 자식은 NULL로 초기화한 후 해당 struct Node 포인터를 반환합니다.

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

삭제(deletion) 함수 구현

deletion(struct Node* root, int data) 함수는 주어진 데이터 값을 가진 노드를 삭제하는 역할을 합니다. 루트 노드와 검색 및 삭제할 데이터 값을 인자로 받습니다. 만약 자식 노드가 하나도 없고 데이터 값이 루트의 값과 같다면 NULL을 반환하고, 그렇지 않으면 루트 노드를 그대로 반환합니다.

Node* deletion(struct Node* root, int data){
    if (root == NULL)
        return NULL;
    if (root->leftChild == NULL && root->rightChild == NULL) {
        if (root->data == data)
            return NULL;
        else
            return root;
    }

큐를 활용한 레벨 순회(Level Order Traversal)

이제 struct Node* 타입의 큐(queue) q를 만들어 루트 노드를 넣습니다. 또한 Node 포인터인 temp와 data_node를 선언하고, data_node는 NULL로 초기화합니다.

struct Node* temp;
struct Node* data_node = NULL;

다음으로 레벨 순회를 수행하여 가장 깊은 노드를 찾습니다. while 루프는 큐 q가 빌 때까지 실행됩니다. 큐는 FIFO(선입선출) 자료구조이므로, 레벨 순서대로 순회할 경우 큐에 마지막으로 들어간 요소가 곧 가장 오른쪽에 있는 깊은 노드가 됩니다. temp는 항상 큐의 맨 앞 요소를 가리키며, 순회가 진행됨에 따라 앞에서부터 요소를 꺼내(pop) 처리합니다.

while (!q.empty()) {
    temp = q.front();
    q.pop();
    if (temp->data == data)
        data_node = temp;
    if (temp->leftChild)
        q.push(temp->leftChild);
    if (temp->rightChild)
        q.push(temp->rightChild);
}

순회가 끝난 후 data_node가 NULL이 아니라면, 삭제할 노드의 데이터를 x에 저장하고 마지막 순회에서 발견된 가장 깊은 노드(temp)를 삭제합니다. 그런 다음 data_node의 값을 가장 깊은 노드의 값으로 대체함으로써 사실상 삭제 효과를 얻습니다. 삭제와 대체가 완료되면 갱신된 루트 노드를 반환합니다.

if (data_node != NULL) {
    int x = temp->data;
    deleteDeepest(root, temp);
    data_node->data = x;
}

가장 깊은 노드 삭제(deleteDeepest) 함수

deleteDeepest(struct Node* root, struct Node* deepestNode) 함수는 전달된 노드가 실제로 가장 깊은 노드인지, 아니면 그 노드의 왼쪽 또는 오른쪽 자식이 가장 깊은 노드인지 확인합니다. 자식이 가장 깊은 노드라면 해당 자식 포인터를 NULL로 설정한 뒤 deepestNode를 메모리에서 해제(delete)합니다.

void deleteDeepest(struct Node* root,
    struct Node* deepestNode){
        queue<struct Node*> q;
        q.push(root);
        struct Node* temp;
        while (!q.empty()) {
            temp = q.front();
            q.pop();
            if (temp == deepestNode) {
                temp = NULL;
                delete (deepestNode);
                return;
            }
            if (temp->rightChild) {
                if (temp->rightChild == deepestNode) {
                    temp->rightChild = NULL;
                    delete (deepestNode);
                    return;
                }
                else
                    q.push(temp->rightChild);
            }
            if (temp->leftChild) {
                if (temp->leftChild == deepestNode) {
                    temp->leftChild = NULL;
                    delete (deepestNode);
                    return;
                }
                else
                    q.push(temp->leftChild);
            }
        }
    }

전체 예제 코드

아래 전체 구현 예제를 통해 이진 트리에서의 삭제 과정을 직접 확인해 보겠습니다.

#include <iostream>
#include <queue>
using namespace std;
struct Node {
    int data;
    struct Node *leftChild, *rightChild;
};
struct Node* NewNode(int data){
    struct Node* temp = new Node;
    temp->data = data;
    temp->leftChild = temp->rightChild = NULL;
    return temp;
};
void inorder(struct Node* temp){
    if (!temp)
        return;
    inorder(temp->leftChild);
    cout << temp->data << " ";
    inorder(temp->rightChild);
}
void deleteDeepest(struct Node* root,
    struct Node* deepestNode){
        queue<struct Node*> q;
        q.push(root);
        struct Node* temp;
        while (!q.empty()) {
            temp = q.front();
            q.pop();
            if (temp == deepestNode) {
                temp = NULL;
                delete (deepestNode);
                return;
            }
            if (temp->rightChild) {
                if (temp->rightChild == deepestNode) {
                    temp->rightChild = NULL;
                    delete (deepestNode);
                    return;
                }
                else
                    q.push(temp->rightChild);
            }
            if (temp->leftChild) {
                if (temp->leftChild == deepestNode) {
                    temp->leftChild = NULL;
                    delete (deepestNode);
                    return;
                }
                else
                    q.push(temp->leftChild);
            }
        }
    }
Node* deletion(struct Node* root, int data){
    if (root == NULL)
        return NULL;
    if (root->leftChild == NULL && root->rightChild == NULL) {
        if (root->data == data)
            return NULL;
        else
            return root;
    }
    queue<struct Node*> q;
    q.push(root);  
    struct Node* temp;
    struct Node* data_node = NULL;
while (!q.empty()) {
    temp = q.front();
    q.pop();
    if (temp->data == data)
        data_node = temp;
    if (temp->leftChild)
        q.push(temp->leftChild);
    if (temp->rightChild)
        q.push(temp->rightChild);
}
if (data_node != NULL) {
    int x = temp->data;
    deleteDeepest(root,temp);
    data_node->data = x;
    }
    return root;
}
// Driver code
int main(){
    struct Node* root = NewNode(12);
    root->leftChild = NewNode(13);
    root->leftChild->leftChild = NewNode(9);
    root->leftChild->rightChild = NewNode(14);
    root->rightChild = NewNode(11);
    root->rightChild->leftChild = NewNode(17);
    root->rightChild->rightChild = NewNode(10);
    cout << "Inorder traversal before deletion : ";
    inorder(root);
    int data = 13;
    root = deletion(root, data);
    cout <<endl<< "Inorder traversal after deletion : ";
    inorder(root);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.

Inorder traversal before deletion : 9 13 14 12 17 11 10
Inorder traversal after deletion : 9 10 14 12 17 11

출력 결과에서 볼 수 있듯이, 값 13을 가진 노드가 삭제되면서 가장 깊고 오른쪽에 있던 노드의 값(10)이 그 자리를 대체한 것을 확인할 수 있습니다. 이처럼 큐를 이용한 레벌 순회를 활용하면 이진 트리에서 임의의 노드를 효율적으로 삭제할 수 있습니다.