Tìm các phần tử trong cây nhị phân bị ô nhiễm trong C ++

Giả sử chúng ta có một cây nhị phân. Quy tắc của cây đó như sau -

• root.val ==0

• Nếu treeNode.val là x và treeNode.left không phải là null, thì treeNode.left.val =2 * x + 1

• Nếu treeNode.val là x và treeNode.right không phải là null thì treeNode.right.val =2 * x + 2

Bây giờ khi cây nhị phân bị ô nhiễm. Điều này cho thấy tất cả các giá trị của nút cây đã được thay đổi thành -1. Đầu tiên chúng ta phải khôi phục cây nhị phân và sau đó triển khai lớp FindElements như sau -

• FindElements (TreeNode * root) Khởi tạo đối tượng bằng cây nhị phân bị nhiễm bẩn, trước tiên chúng ta phải khôi phục nó.

• bool find (int target). Điều này sẽ trả về nếu giá trị đích tồn tại trong cây nhị phân được khôi phục.

Vì vậy, nếu cây như -

Vì vậy, sau khi khôi phục, nếu chúng ta cố gắng tìm 1, 3 và 5, thì kết quả sẽ là true, true và false.

Để 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 tập hợp

• Định nghĩa một phương thức dfs (), phương thức này sẽ lấy root và rootVal. rootVal ban đầu là -1

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

• nếu rootVal là -1, thì hãy đặt giá trị của root là 0, nếu không thì đặt nó là rootVal

• chèn giá trị của root vào một

• gọi dfs (bên trái của gốc, 2 * giá trị của gốc + 1), dfs (bên phải của gốc, 2 * giá trị của gốc + 2)

• Đối với quá trình khởi tạo, (hoặc xây dựng lại), chúng ta sẽ gọi dfs (root, -1)

• Để tìm một số phần tử, hãy kiểm tra xem phần tử đó có ở đó hay không, nếu có thì trả về giá trị, nếu không thì là false.

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

Ví dụ

#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;
}
class FindElements {
   public:
   set <int> a;
   void dfs(TreeNode* root,int rootVal=-1){
      if(!root)return;
      root->val = rootVal == -1?0:rootVal;
      a.insert(root->val);
      dfs(root->left,2*root->val + 1);
      dfs(root->right, 2*root->val + 2);
   }
   FindElements(TreeNode* root) {
      dfs(root);
   }
   bool find(int t) {
      return a.find(t)!=a.end();
   }
};
main(){
   vector<int> v = {-1,-1,-1,-1,-1};
   TreeNode *root = make_tree(v);
   FindElements ob(root);
   cout << (ob.find(1)) << endl;
   cout << (ob.find(3)) << endl;
   cout << (ob.find(5)) << endl;
}

Đầu vào

Initialize the tree with [-1,-1,-1,-1,-1], then call find(1), find(3) and find(5)

Đầu ra

1
1
0