การลบในไบนารีทรีในโปรแกรม C++

ในบทช่วยสอนนี้ เราจะเรียนรู้วิธีลบโหนดในไบนารีทรี

โหนดในแผนผังไบนารีไม่เป็นไปตามลำดับใดๆ เช่น ต้นไม้การค้นหาแบบไบนารี ดังนั้นจะจัดเรียงโหนดหลังจากลบโหนดในไบนารีทรีได้อย่างไร

เราจะแทนที่โหนดที่ลึกที่สุดของต้นไม้ด้วยโหนดการลบ จากนั้นเราจะลบโหนดที่ลึกที่สุดออกจากโหนด

มาดูขั้นตอนการแก้ปัญหากัน

• เริ่มต้นต้นไม้ด้วยโครงสร้างโหนดไบนารี

• เขียนฟังก์ชัน (สั่งล่วงหน้า เรียงลำดับ และโพสต์) เพื่อพิมพ์โหนดของทรี

• เขียนฟังก์ชันเพื่อลบโหนด

  • เริ่มต้นคิวเพื่อวนซ้ำผ่านทรี

  • วนซ้ำจนกว่าคิวจะว่าง

  • ค้นหาโหนดด้วยคีย์ที่กำหนดและเก็บไว้ในตัวแปร

  • และโหนดสุดท้ายจากคิวคือโหนดที่ลึกที่สุด

• ลบโหนดที่ลึกที่สุดโดยใช้ฟังก์ชันอื่น

  • ใช้คิวลัดเลาะไปตามต้นไม้

  • เมื่อเราพบโหนดให้ลบและส่งคืน

• พิมพ์ต้นไม้เพื่อดูว่าโหนดถูกลบหรือไม่

ตัวอย่าง

มาดูโค้ดกันเลย

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
struct Node* newNode(int data) {
   struct Node* temp = new Node;
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
};
void inorder(struct Node* node) {
   if (node == NULL) {
      return;
   }
   inorder(node->left);
   cout << node->data << " ";
   inorder(node->right);
}
void deleteDeepestNode(struct Node* root, struct Node* deleting_node){
   queue<struct Node*> nodes;
   nodes.push(root);
   struct Node* temp;
   while (!nodes.empty()) {
      temp = nodes.front();
      nodes.pop();
      if (temp == deleting_node) {
         temp = NULL;
         delete (deleting_node);
         return;
      }
      if (temp->right) {
         if (temp->right == deleting_node) {
            temp->right = NULL;
            delete deleting_node;
            return;
         }
         else {
            nodes.push(temp->right);
         }
      }
      if (temp->left) {
         if (temp->left == deleting_node) {
            temp->left = NULL;
            delete deleting_node;
            return;
         }
         else {
            nodes.push(temp->left);
         }
      }
   }
}
Node* deleteNode(struct Node* root, int key) {
   if (root == NULL){
      return NULL;
   }
   if (root->left == NULL && root->right == NULL) {
      if (root->data == key) {
         return NULL;
      }
      else {
         return root;
      }
   }
   queue<struct Node*> nodes;
   nodes.push(root);
   struct Node* temp;
   struct Node* key_node = NULL;
   while (!nodes.empty()) {
      temp = nodes.front();
      nodes.pop();
      if (temp->data == key) {
         key_node = temp;
      }
      if (temp->left) {
         nodes.push(temp->left);
      }
      if (temp->right) {
         nodes.push(temp->right);
      }
   }
   if (key_node != NULL) {
      int deepest_node_data = temp->data;
      deleteDeepestNode(root, temp);
      key_node->data = deepest_node_data;
   }
   return root;
}
int main() {
   struct Node* root = newNode(1);
   root->left = newNode(2);
   root->left->left = newNode(3);
   root->left->right = newNode(4);
   root->right = newNode(5);
   root->right->left = newNode(6);
   root->right->right = newNode(7);
   root->right->left->left = newNode(8);
   root->right->left->right = newNode(9);
   cout << "Tree before deleting key: ";
   inorder(root);
   int key = 5;
   root = deleteNode(root, key);
   cout << "\nTree after deleting key: ";
   inorder(root);
   cout << endl;
   return 0;
}

ผลลัพธ์

หากคุณเรียกใช้โค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้

Tree before deleting key: 3 2 4 1 8 6 9 5 7
Tree after deleting key: 3 2 4 1 8 6 9 7

บทสรุป

หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น