Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

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

C++를 이용해 이진 트리에서 값이 x와 일치하는 리프 노드(자식이 없는 노드)를 찾아 삭제하는 방법을 알아보겠습니다. 핵심 아이디어는 트리를 재귀적으로 순회하면서 조건에 맞는 리프 노드를 제거하고, 잘린 서브트리를 다시 부모 노드에 연결하는 것입니다.

1. 트리 노드 구조체 정의

먼저 노드의 데이터와 왼쪽·오른쪽 자식 노드를 가리킬 포인터를 포함하는 트리 노드 구조체를 정의합니다. 처음 생성되는 노드는 루트(root) 노드가 되고, 이후에 생성되는 노드들은 모두 자식 노드로 연결됩니다.

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

2. 새 노드 생성 함수(newNode)

다음으로 정수 값을 인자로 받아 노드의 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. 리프 노드 삭제 함수(deleteNode)

이제 루트 노드와 삭제할 값 x를 인자로 받는 deleteNode(Node* root, int x) 함수를 만듭니다. 이 함수는 다음과 같이 재귀적으로 동작합니다.

  • 현재 노드가 NULL이면 nullptr을 반환합니다.
  • 왼쪽과 오른쪽 서브트리를 먼저 재귀적으로 처리한 뒤, 그 결과를 다시 자식 포인터에 연결합니다.
  • 처리가 끝난 후 현재 노드의 값이 x이고 자식 노드가 없다면(즉 리프 노드라면) nullptr을 반환하여 해당 노드를 삭제합니다.

주의할 점은 값이 x인 내부(internal) 노드는 자식이 존재하는 한 삭제되지 않는다는 것입니다. 다만 자식들이 모두 삭제되어 스스로 리프 노드가 되는 경우에는 연쇄적으로 함께 제거될 수 있습니다. 함수는 삭제 작업이 완료된 수정된 트리의 루트를 반환합니다.

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

4. 트리 순회 및 출력(inorder)

마지막으로 삭제 후 트리의 상태를 확인할 수 있도록 inorder(Node* root) 함수를 통해 트리를 순회하며 남아 있는 노드들의 값을 화면에 출력합니다.

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

전체 예제 코드

지금까지 설명한 내용을 하나로 합친, 값이 x인 리프 노드를 삭제하는 전체 구현 예제는 다음과 같습니다.

#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* deleteNode(Node* root, int x){
    if (root == NULL)
        return nullptr;
    root->leftChild = deleteNode(root->leftChild, x);
    root->rightChild = deleteNode(root->rightChild, x);
    if (root->data == x && 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(4);
    root->leftChild = newNode(2);
    root->rightChild = newNode(12);
    root->leftChild->leftChild = newNode(3);
    root->leftChild->rightChild = newNode(5);
    root->rightChild->rightChild = newNode(9);
    deleteNode(root, 3);
    cout << "Inorder traversal after deletion : ";
    inorder(root);
    return 0;
}

실행 결과

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

Inorder traversal after deletion : 5 2 9 12 4

출력 결과에서 값이 3인 리프 노드가 성공적으로 삭제된 것을 확인할 수 있으며, 나머지 노드들은 그대로 트리에 유지됩니다.