Khôi phục cây tìm kiếm nhị phân trong C ++

Giả sử chúng ta có một cây tìm kiếm nhị phân, bây giờ coi như hai phần tử của BST này được hoán đổi vị trí, vì vậy chúng ta phải khôi phục cây tìm kiếm nhị phân này.

Vì vậy, nếu cây đã cho giống như bên dưới (cây đầu tiên), cây phục hồi sẽ là (cây thứ hai) -

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một số tham chiếu trước, đầu tiên, thứ hai cho các nút

• Xác định một phương thức được gọi là findProblem (), phương thức này sẽ sử dụng nút

• nếu nút là null, thì trả về

• gọi findProblem (bên trái của nút)

• nếu giá trị của nút dựa trên giá trị của trước đó không phải là null và giá trị là giá trị của nút thì

  • nếu đầu tiên là null, thì đầu tiên =trước

  • thứ hai:=nút

• trước:=nút

• gọi findProblem (bên phải của nút)

• Từ phương thức chính, hãy làm như sau -

• khởi tạo trước trước, đầu tiên và thứ hai dưới dạng null, gọi findProblem (gốc) và hoán đổi các giá trị của nút đầu tiên và nút thứ hai

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      } else {
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      } else {
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
void tree_level_trav(TreeNode*root){
   if (root == NULL) return;
   cout << "[";
   queue q;
   TreeNode *curr;
   q.push(root);
   q.push(NULL);
   while (q.size() > 1) {
      curr = q.front();
      q.pop();
      if (curr == NULL){
         q.push(NULL);
      } else {
         if(curr->left)
            q.push(curr->left);
         if(curr->right)
            q.push(curr->right);
         if(curr == NULL || curr->val == 0){
            cout << "null" << ", ";
         }else{
            cout << curr->val << ", ";
         }
      }
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   TreeNode* prev;
   TreeNode* first;
   TreeNode* second;
   void swapValue(TreeNode* first, TreeNode* second){
      int x = first->val;
      first->val = second -> val;
      second->val = x;
   }
   void findProblem(TreeNode* node){
      if(!node || node->val == 0)return;
      findProblem(node->left);
      if((prev!=NULL && prev->val != 0) && prev->val> node->val){
         if(!first){
            first = prev;
         }
         second = node;
      }
      prev = node;
      findProblem(node->right);
   }
   void recoverTree(TreeNode* root) {
      prev = first = second = NULL;
      findProblem(root);
      swapValue(first, second);
   }
};
main(){
   vector<int> v = {1,3,NULL,NULL,2};
   TreeNode *root = make_tree(v);
   Solution ob;
   ob.recoverTree(root);
   tree_level_trav(root);
}

Đầu vào

{1,3,NULL,NULL,2}

Đầu ra

[3, 1, null, null, 2, ]