C++로 이진 트리에서 값이 x인 리프 노드 삭제하기

이 튜토리얼에서는 이진 트리에서 주어진 값과 일치하는 리프 노드(leaf node)를 삭제하는 방법을 알아봅니다. 리프 노드란 왼쪽과 오른쪽 자식 노드가 모두 없는 노드를 의미합니다.

문제 해결 접근 방식

재귀적으로 트리를 순회하면서 조건에 맞는 리프 노드를 제거하는 후위 순회(postorder) 방식으로 문제를 해결할 수 있습니다. 단계별로 살펴보겠습니다.

이진 트리의 노드를 나타내는 struct Node 구조체를 정의합니다.
트리를 순회(inorder, preorder, postorder)하며 모든 데이터를 출력하는 함수를 작성합니다.
구조체를 이용해 노드를 생성하고 트리를 초기화합니다.
삭제할 대상 값 x를 초기화합니다.
주어진 값을 가지는 리프 노드를 삭제하는 함수를 작성합니다. 이 함수는 루트 노드와 값 x 두 개의 인자를 받습니다.
- 루트가 NULL이면 그대로 반환합니다.
- 루트의 왼쪽 자식을 삭제 처리 후 반환된 새로운 서브트리 루트로 교체합니다.
- 오른쪽 자식도 동일하게 처리합니다.
- 현재 노드의 데이터가 x와 같고, 자식 노드가 없는 리프 노드라면 nullptr을 반환하여 해당 노드를 삭제합니다.
- 그 외의 경우에는 현재 루트 노드를 그대로 반환합니다.

예제 코드

전체 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node *left, *right;
};

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

Node* deleteLeafNodes(Node* root, int x) {
    if (root == NULL) {
        return nullptr;
    }
    root->left = deleteLeafNodes(root->left, x);
    root->right = deleteLeafNodes(root->right, x);
    // 현재 노드의 데이터와 x 비교
    if (root->data == x && root->left == NULL && root->right == NULL) {
        // 해당 노드 삭제
        return nullptr;
    }
    return root;
}

void inorder(Node* root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main(void) {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(3);
    root->left->right = newNode(4);
    root->right->right = newNode(5);
    root->right->left = newNode(4);
    root->right->right->left = newNode(4);
    root->right->right->right = newNode(4);

    deleteLeafNodes(root, 4);

    cout << "Tree: ";
    inorder(root);
    cout << endl;

    return 0;
}

실행 결과

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

Tree: 3 2 1 3 5

동작 원리 설명

이 코드에서 핵심은 재귀 호출 순서입니다. 먼저 왼쪽과 오른쪽 서브트리를 각각 처리한 후에 현재 노드를 검사하기 때문에, 자식 노드가 삭제되어 리프 노드가 된 경우도 올바르게 처리됩니다. 예를 들어 값이 4인 노드 아래에 또 다른 값이 4인 자식이 있었다면, 자식이 먼저 삭제된 후 부모 노드가 리프 노드가 되므로 연쇄적으로 삭제가 가능합니다.

마무리

이번 튜토리얼에서는 C++을 사용해 이진 트리에서 특정 값을 가지는 리프 노드를 재귀적으로 삭제하는 방법을 배웠습니다. 궁금한 점이 있다면 댓글로 남겨주세요.