การลบใน Binary Tree ใน C ++?

การลบทำได้โดยแทนที่โหมดที่ถูกลบด้วยโหนดด้านล่างและขวาสุด

ให้เรากำหนดโครงสร้างที่จะเป็นตัวแทนของโหนดต้นไม้ที่มีข้อมูลและโหนดลูกของโหนดซ้ายและขวา หากนี่เป็นโหนดแรกที่สร้างขึ้น แสดงว่าเป็นโหนดรูท มิฉะนั้นจะเป็นโหนดย่อย

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

ต่อไป เราสร้างฟังก์ชัน newNode(int data) ที่ใช้ค่า int และกำหนดให้กับสมาชิกข้อมูลของโหนด ฟังก์ชันจะส่งกลับตัวชี้ไปยังโหนดโครงสร้างที่สร้างขึ้น นอกจากนี้ ลูกซ้ายและขวาของโหนดที่สร้างขึ้นใหม่จะถูกตั้งค่าเป็นโมฆะ

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 นอกจากนี้เรายังประกาศ temp และ data_node ซึ่งเป็นตัวชี้ไปยังโหนดและตั้งค่า data_node เป็น NULL

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

ต่อไป เราดำเนินการข้ามระดับเพื่อค้นหาโหนดที่ลึกที่สุด วนรอบในขณะที่ดำเนินการจนกว่าคิว q ไม่ว่างเปล่า คิวเป็นโครงสร้างข้อมูล FIFO ดังนั้นองค์ประกอบสุดท้ายในคิวจะเป็นโหนดที่ลึกที่สุดด้านขวาสุด เนื่องจากเรากำลังดำเนินการตามระดับการข้ามผ่าน อุณหภูมิจะชี้ไปที่ด้านหน้าของคิวเสมอและองค์ประกอบจะโผล่ขึ้นมาจากด้านหน้าเมื่อเราไปต่อ

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 ก่อนลบพาเรนต์ซึ่งเป็น โหนดที่ลึกที่สุด

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