C++의 이진 트리에서 삭제?

삭제 모드를 최하단 우측 노드로 교체하여 삭제를 수행합니다.

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

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

삭제(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;
   }

이제 struct Node * 유형의 큐를 만들고 이름을 q로 지정하고 루트 노드를 q로 푸시합니다. 또한 Node에 대한 포인터인 temp와 data_node를 선언하고 data_node를 NULL로 설정합니다.

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

다음으로 가장 깊은 노드를 찾기 위해 레벨 순서 순회를 수행합니다. while 루프는 큐 q가 비어 있지 않을 때까지 실행됩니다. 큐는 FIFO 데이터 구조이므로 큐의 마지막 요소는 레벨 순서 순회에 따라 가장 오른쪽에 있는 가장 깊은 노드가 됩니다. temp는 항상 대기열의 앞쪽을 가리키며 계속 진행하면서 요소가 앞쪽에서 튀어나옵니다.

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(struct Node* root,struct Node* deepestNode) 함수는 전달된 노드가 실제로 가장 깊은 노드인지 또는 오른쪽 또는 왼쪽 자식이 가장 깊은 노드인지 확인합니다. 이 경우 부모를 삭제하기 전에 자식 값을 null로 설정합니다. deepestNode.

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