C++에서 값이 x인 리프 노드를 삭제하시겠습니까?

먼저 데이터와 왼쪽 및 오른쪽 노드 자식을 포함하는 트리 노드를 나타내는 구조체를 정의하겠습니다. 이것이 생성될 첫 번째 노드이면 루트 노드이고 그렇지 않으면 자식 노드입니다.

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

다음으로 int 값을 취하여 노드의 데이터 멤버에 할당하는 newNode(int 데이터) 함수를 만듭니다. 함수는 생성된 구조체 노드에 대한 포인터를 반환합니다. 또한 새로 생성된 노드의 왼쪽과 오른쪽 자식은 null로 설정됩니다.

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

이제 루트 노드와 삭제할 노드의 데이터 값을 취하는 deleteNode(Node* root, int x) 함수를 만듭니다. 주어진 노드가 부모 노드이면 왼쪽 및 오른쪽 자식도 삭제합니다. 주어진 노드를 삭제한 후 수정된 루트 노드를 반환하는 함수입니다.

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;
}

마지막으로 삭제 후 트리를 표시하기 위해 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