C++에서 값이 k인 리프 노드 삭제하는 방법

이진 트리에서 특정 값을 가진 리프(leaf) 노드를 삭제하는 것은 트리 자료구조를 다룰 때 자주 등장하는 기본 연산입니다. 이 글에서는 C++로 재귀 함수를 활용해 값이 k인 모든 리프 노드를 안전하게 제거하는 방법을 단계별로 살펴보겠습니다.

1. 트리 노드 구조체 정의

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

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

2. 새 노드 생성 함수

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

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

3. 리프 노드 삭제 함수

이제 핵심인 deleteLeafNode(Node* root, int k) 함수를 작성합니다. 이 함수는 루트 노드와 삭제할 노드의 데이터 값을 인자로 받으며, 다음과 같은 방식으로 동작합니다.

현재 노드가 NULL이면 nullptr을 반환합니다.
왼쪽과 오른쪽 서브트리에 대해 재귀적으로 삭제를 수행한 뒤, 그 결과를 각 자식 포인터에 다시 대입합니다.
현재 노드의 값이 k이고, 왼쪽·오른쪽 자식이 모두 없다면(즉, 리프 노드라면) 해당 노드를 삭제하기 위해 nullptr을 반환합니다.
그 외의 경우에는 원래 노드를 그대로 반환합니다.

재귀 호출의 결과를 부모 노드의 자식 포인터에 다시 연결해 주기 때문에, 리프 노드가 삭제되어도 트리의 구조가 올바르게 유지됩니다.

Node* deleteLeafNode(Node* root, int k) {
    if (root == NULL)
        return nullptr;
    root->leftChild = deleteLeafNode(root->leftChild, k);
    root->rightChild = deleteLeafNode(root->rightChild, k);
    if (root->data == k && root->leftChild == NULL &&
        root->rightChild == NULL)
        return nullptr;
    return root;
}

4. 트리 순회 및 출력 함수

마지막으로 삭제 후 트리의 상태를 확인하기 위해 inorder(Node* root) 함수를 사용합니다. 이 함수는 트리를 재귀적으로 순회하면서 각 노드의 데이터를 화면에 출력합니다.

void inorder(Node* root){
    if (root != NULL){
        inorder(root->leftChild);
        inorder(root->rightChild);
        cout << root->data << " ";
    }
}

전체 예제 코드

지금까지 설명한 내용을 하나로 합친 전체 구현 코드입니다. 아래 예제에서는 값이 7인 리프 노드들을 삭제합니다.

#include <iostream>
using namespace std;
struct Node {
    int data;
    struct Node *leftChild, *rightChild;
};
struct Node* newNode(int data){
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->leftChild = newNode->rightChild = NULL;
    return (newNode);
}
Node* deleteLeafNode(Node* root, int k){
    if (root == NULL)
        return nullptr;
    root->leftChild = deleteLeafNode(root->leftChild, k);
    root->rightChild = deleteLeafNode(root->rightChild, k);
    if (root->data == k && root->leftChild == NULL &&
    root->rightChild == NULL)
        return nullptr;
    return root;
}
void inorder(Node* root){
    if (root != NULL){
        inorder(root->leftChild);
        inorder(root->rightChild);
        cout << root->data << " ";
    }
}
int main(void){
    struct Node* root = newNode(6);
    root->leftChild = newNode(7);
    root->rightChild = newNode(7);
    root->leftChild->leftChild = newNode(5);
    root->leftChild->rightChild = newNode(3);
    root->rightChild->rightChild = newNode(7);
    deleteLeafNode(root, 7);
    cout << "Inorder traversal after deleting given leaf node: ";
    inorder(root);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Inorder traversal after deleting given leaf node: 5 3 7 6

정리

이 예제에서 루트의 오른쪽 자식(값 7)은 자식 노드를 하나 가지고 있으므로 리프 노드가 아니어서 삭제되지 않지만, 그 아래의 값 7을 가진 리프 노드와 왼쪽 서브트리의 값 7 리프 노드는 모두 제거됩니다. 이처럼 후위(postorder) 방식의 재귀 처리를 사용하면 자식부터 먼저 검사하고 삭제할 수 있어, 내부 노드가 리프 노드로 바뀌는 경우까지도 자연스럽게 처리할 수 있다는 점이 이 알고리즘의 핵심입니다.