Cây tìm kiếm nhị phân duy nhất II trong C ++

Giả sử chúng ta có một số nguyên n, chúng ta phải tạo tất cả các cây tìm kiếm nhị phân có cấu trúc duy nhất lưu trữ các giá trị từ 1 đến n. Vì vậy, nếu đầu vào là 3, thì cây sẽ -

Để 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 hàm đệ quy được gọi là create (), hàm này sẽ có giá trị thấp và cao
• xác định một nút cây được gọi là tạm thời.
• nếu thấp> cao, sau đó chèn null vào tạm thời và trả về nhiệt độ
• cho tôi trong phạm vi từ thấp đến cao
  • left_subtree:=create (low, i - 1)
  • right_subtree:=create (i + 1, high)
  • hiện tại:=i
  • cho j trong phạm vi 0 đến kích thước của left_subtree
    • cho k trong phạm vi 0 đến kích thước của cây_ bên phải
      • curr_node:=tạo một nút cây có giá trị hiện tại
      • left of the curr_node:=left_subtree [j]
      • bên phải của curr_node:=right_subtree [k]
      • chèn curr_node vào nhiệt độ
• nhiệt độ trở lại.
• Ban đầu, hãy gọi hàm create () với các giá trị 1 và n để tạo ra tất cả các cây.

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để 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 = 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<TreeNode *> 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:
   vector<TreeNode*> generate(int low, int high) {
      vector <TreeNode*> temp;
      if(low > high){
         temp.push_back(NULL);
         return temp;
      }
      for(int i = low;i<=high;i++){
         vector <TreeNode*> leftSubtree = generate(low,i-1);
         vector <TreeNode*> rightSubtree = generate(i+1,high);
         int current = i;
         for(int j = 0;j<leftSubtree.size();j++){
            for(int k =0;k<rightSubtree.size();k++){
               TreeNode* currentNode = new TreeNode(current);
               currentNode->left = leftSubtree[j];
               currentNode->right = rightSubtree[k];
               temp.push_back(currentNode);
            }
         }
      }
      return temp;
   }
   vector<TreeNode*> generateTrees(int n) {
      if(!n){
         vector <TreeNode*> r;
         return r;
      }
      return generate(1,n) ;
   }
};
main(){
   Solution ob;
   vector<TreeNode*> v = ob.generateTrees(3);
   for(int i = 0; i<v.size(); i++)
      tree_level_trav(v[i]);
}

Đầu vào

3

Đầu ra

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