Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
3.2 kB
2
Indexable
Never
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

class BinTree {
private:
    class Point {
    public:
        int num;
        Point *left;
        Point *right;

        Point(int num) {
            this->num = num;
            this->left = nullptr;
            this->right = nullptr;
        }

        Point(int num, Point *left, Point *right) {
            this->num = num;
            this->left = left;
            this->right = right;
        }

        Point() {
            this->num = 0;
            this->left = nullptr;
            this->right = nullptr;
        }
    };

    Point *Root;

    Point *buildTree(vector<int> nums, int start, int end) {
        if (start > end) {
            return nullptr;
        }
        int mid = (start + end) / 2;
        Point *root = new Point(nums[mid]);
        root->left = buildTree(nums, start, mid - 1);
        root->right = buildTree(nums, mid + 1, end);
        return root;
    }

public:
    BinTree(vector<int> nums) {
        this->Root = buildTree(nums, 0, nums.size() - 1);
    }

    ~BinTree() {
        delete Root;
    }

    bool in_array(int num) {
        Point *cur = Root;
        while (cur != nullptr) {
            cout << cur->num << endl;
            if (cur->num == num) {
                return true;
            } else if (cur->num > num) {
                cur = cur->left;
            } else {
                cur = cur->right;
            }
        }
        return false;
    }

    void insert(int num) {
        Point *cur = Root;
        while (cur != nullptr) {
            if (cur->num == num) {
                return;
            } else if (cur->num > num) {
                if (cur->left == nullptr) {
                    cur->left = new Point(num);
                    return;
                }
                cur = cur->left;
            } else {
                if (cur->right == nullptr) {
                    cur->right = new Point(num);
                    return;
                }
                cur = cur->right;
            }
        }
    }

    int get_min(int num){
        if (this->in_array(num)){
            Point *cur = Root;
            while (cur->left != nullptr) {
                cur = cur->left;
            }
            return cur->num;
        }
        return -1;
    }

    int get_max(int num){
        if (this->in_array(num)){
            Point *cur = Root;
            while (cur->right != nullptr) {
                cur = cur->right;
            }
            return cur->num;
        }
        return -1;
    }
};

int main() {
    const int N = 10000;
    srand(time(nullptr));
    set<int> tmp;
    for (int i = 0; i < N; i++) {
        tmp.insert(rand());
    }
    vector<int> nums(tmp.begin(), tmp.end());
    sort(nums.begin(), nums.end());
    BinTree tree(nums);
//    for (int num : nums) {
//        cout << num << ' ';
//    }
//    cout << endl;
    cout << tree.in_array(22222) << endl;
    tree.insert(22222);
    cout << tree.in_array(22222) << endl;
    return 0;
}
Leave a Comment