Computer >> Máy Tính >  >> Lập trình >> C ++

Xóa trong cây nhị phân trong C ++?

Việc xóa sẽ được thực hiện bằng cách thay thế chế độ đã xóa bằng nút dưới cùng và ngoài cùng bên phải.

Đầu tiên chúng ta hãy xác định cấu trúc đại diện cho một nút cây chứa dữ liệu và nút con trái và phải của nó. Nếu đây là nút đầu tiên được tạo thì đó là nút gốc, ngược lại là nút con.

Nút 
struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

Tiếp theo, chúng tôi tạo hàm newNode (int data) của chúng tôi, nhận một giá trị int và gán nó cho thành viên dữ liệu của nút. Hàm trả về con trỏ tới struct Node đã tạo. Ngoài ra, nút con bên trái và bên phải của nút mới tạo được đặt thành null. 

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

Hàm xóa (struct Node * root, int data) được sử dụng để xóa nút có giá trị dữ liệu đã cho. Nó có nút gốc và giá trị dữ liệu được tìm kiếm và xóa. Nếu không có bất kỳ nút con nào và giá trị dữ liệu bằng với giá trị dữ liệu của gốc thì null được trả về nếu không thì nút gốc được trả về. 

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

Bây giờ chúng ta tạo một hàng đợi kiểu struct Node * và đặt tên là q và đẩy nút gốc đến q. Chúng tôi cũng khai báo temp và data_node là những con trỏ tới Node và đặt data_node là NULL. 

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

Tiếp theo, chúng tôi thực hiện duyệt thứ tự cấp độ để tìm ra nút sâu nhất. Vòng lặp while được thực hiện cho đến khi hàng đợi q không trống. Hàng đợi là một cấu trúc dữ liệu FIFO vì vậy phần tử cuối cùng trong hàng đợi sẽ là nút sâu nhất bên phải khi chúng ta đang duyệt theo thứ tự cấp. Nhiệt độ luôn luôn hướng đến phía trước hàng đợi và các phần tử sẽ xuất hiện từ phía trước khi chúng ta tiếp tục. 

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

Tiếp theo nếu data_node không phải là NULL thì chúng tôi lưu trữ dữ liệu của nút cần xóa trong x và xóa tạm thời là nút sâu nhất. Giá trị data_node sau đó được thay thế bằng giá trị nút sâu nhất và nút sâu nhất bị xóa. Nút mới được trả lại từ hàm sau khi xóa và thay thế. 

if (data_node != NULL) {
   int x = temp->data;
   deleteDeepest(root, temp);
   data_node->data = x;
}

Hàm deleteDeepest (struct Node * root, struct Node * deepNode) kiểm tra xem nút đã truyền thực sự là nút sâu nhất hay nút con bên phải hoặc bên trái là nút sâu nhất, trong trường hợp đó nó đặt giá trị con thành null trước khi xóa nút cha đó là Nút sâu nhất. 

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

Ví dụ

Hãy để chúng tôi xem cách triển khai sau để xem việc xóa trong cây nhị phân - 

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

Đầu ra

Đoạn mã trên sẽ tạo ra kết quả sau - 

Inorder traversal before deletion : 9 13 14 12 17 11 10
Inorder traversal after deletion : 9 10 14 12 17 11