我这个树还有救的可能性吗……
查看原帖
我这个树还有救的可能性吗……
902704
wjx38223楼主2024/10/17 08:08

辛辛苦苦建树一晚上,T了六个点(雾),大佬帮我看看还有改的可能吗

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f; // 用来代指x
string s;
int m, q;

// 定义节点结构体
struct node{
    int l, r; // 左右值
    char symbol; // 节点符号
    node* t, *f; // 指向真和假子树的指针
    node(){
        l = r = 0; // 初始化左右值为0
        symbol = '0'; // 初始化符号为'0'
        t = f = NULL; // 初始化子树指针为NULL
    }
};

// 三目表达式,建树
int cnt = -1; // 计数器,用于遍历字符串
inline node* build(){
    node* root = new node(); // 创建新节点
    bool pass = false; // 标记是否已经读取到符号
    for(cnt++; cnt<s.size(); cnt++){ // 遍历字符串
        if(s[cnt]=='>'||s[cnt]=='<'){ // 如果是符号
            root->symbol = s[cnt]; // 设置节点符号
            pass = true; // 更新标记
        }else if(s[cnt]>='0'&&s[cnt]<='9'){ // 如果是数字
            if(pass){ // 如果已经读取到符号
                root->r = root->r * 10 + s[cnt] - '0'; // 更新右值
            }else{
                root->l = root->l * 10 + s[cnt] - '0'; // 更新左值
            }
        }else if(s[cnt]=='x'){ // 如果是'x'
            if(pass){
                root->r = inf; // 设置右值为无穷大
            }else{
                root->l = inf; // 设置左值为无穷大
            }
        }else if(s[cnt]=='?'||s[cnt]==':'){ // 如果是三目运算符
            if(s[cnt]=='?'){ // 如果是问号
                root->t = build(); // 构建真子树
                root->f = build(); // 构建假子树
                return root; // 返回当前节点
            }else{
                return root; // 返回当前节点
            }
        }
    }
    return root; // 返回构建的树根节点
}

inline int check(node* root, int x){ // 检查给定值 x
    if(root->symbol == '0'){ // 是叶子节点,返回值
        return root->l;
    }
    if(root->l == inf){ // 如果左值为x
        if(root->symbol == '>' && x>root->r || root->symbol == '<' && x<root->r){
            return check(root->t, x); // 根据符号判断返回真子树的结果
        }else{
            return check(root->f, x); // 返回假子树的结果
        }
    }else if(root->r == inf){ // 如果右值为x
        if(root->symbol == '<' && x>root->l || root->symbol == '>' && x<root->l){
            return check(root->t, x); // 返回真子树的结果
        }else{
            return check(root->f, x); // 返回假子树的结果
        }
    }else{ // 如果左右值都有效
        if(root->symbol == '>' && root->l>root->r || root->symbol == '<' && root->l<root->r){
            return check(root->t, x); // 返回真子树的结果
        }else{
            return check(root->f, x); // 返回假子树的结果
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> q;
    cin >> s;
    node* root = build(); // 构建树
    while(q--){
        int x;
        cin >> x;
        cout << check(root, x) << "\n";
    }
    return 0;
}

2024/10/17 08:08
加载中...