二叉搜索树系列

本文主要是介绍二叉搜索树系列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include <bits/stdc++.h>

inline int read() {
    int res = 0, tag = 1;
    char c = getchar();
    while (c < 48 || c > 57) {
        if (c == '-') tag = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57) {
        res = (res << 3) + (res << 1) + (c ^ 48); 
        c = getchar();
    }
    return res * tag;
}
inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}


const int MX = 1e6;

struct node {
    int val, l, r;
};
int tot;
struct node a[MX];

int build(std::string s) {
    std::vector<int> stk(s.size());
    int k = 0, f = 0, t = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (isdigit(s[i])) k = (k << 1) + (k << 3) + (s[i] ^ 48);
        else {
            if (k) {
                a[++tot] = {k, -1, -1};
                if (f == 1) a[stk[t]].l = tot;
                if (f == 2) a[stk[t]].r = tot;   
                k = 0;             
            }
            if (s[i] == '(') {
                stk[++t] = tot;
                f = 1;
            } else if (s[i] == ',') {
                f = 2;
            } else if (s[i] == ')') {
                --t;
            }
        }
    }
    return stk[1];
}

int find(int rot, int x){
    if (rot == -1) return 0;
    else if (a[rot].val > x) return find(a[rot].l, x);
    else if (a[rot].val < x) return find(a[rot].r, x);
    return rot;
}

void insert(int &rot, int x) {
    if (rot == -1) {
        a[++tot] = {x, -1, -1};
        rot = tot;
    } else if (a[rot].val > x) {
        insert(a[rot].l, x);
    } else if (a[rot].val < x) {
        insert(a[rot].r, x);
    }
}

void print(int rot) {
    if (rot == -1) return;
    write(a[rot].val);
    if (a[rot].l == -1 && a[rot].r == -1) return;
    putchar('(');
    print(a[rot].l);
    putchar(',');
    print(a[rot].r);
    putchar(')');
}

std::vector<int> ans;
void inorder(int rot) {
    if (rot == -1) return;
    inorder(a[rot].l);
    ans.push_back(a[rot].val);
    inorder(a[rot].r);
}
bool judge() {
    inorder(1);
    for (int i = 1; i < ans.size(); ++i) 
        if (ans[i] <= ans [i - 1]) return false;
    return true;
}

signed main() {
    std::string s;
    std::cin >> s;
    int rot = build(s);
    puts(judge() ? "yes" : "no");

    return 0;
}

这篇关于二叉搜索树系列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！