社区讨论

CE求助

P5076【深基16.例7】普通二叉树(简化版)参与者 2已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@m0ax7019
此快照首次捕获于
2024/08/26 19:33
2 年前
此快照最后确认于
2025/11/04 22:21
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
struct Node{
	int ltree,rtree;
	int p;
	bool t=false;
}tree[10001];
void treeinsert(int x,int k){
	if(tree[k].t==false){
		tree[k].t=true;
		tree[k].p=x;
	}else{
		if(x<tree[k].p){
			if(tree[k*2].t==false) tree[k].ltree=x;
			treeinsert(x,k*2);
		}else{
			if(tree[k*2+1].t==false) tree[k].rtree=x;
			treeinsert(x,k*2+1);
		}
	}
	return;
}
int treeq(int x,int k){
	if(tree[k].t==false) return -2147483647; 
    if(tree[k].p<x) {
        int temp=treeq(x,k*2+1);
        if(temp==-1||tree[k].p>temp) {
            return tree[k].p;
        }else{
            return temp;
        }
    }else{
    	return treeq(x,k*2);
    }
}
int treeh(int x, int k) {
    if(tree[k].t == false) return 2147483647; 
    int temp = 2147483647;
    if (tree[k].p>x) {
        temp=tree[k].p;
        int leftResult = treeh(x, k * 2);
        if(leftResult>x&&leftResult<temp) temp = leftResult;
    }else{
        int rightResult=treeh(x,k*2+1);
        if(rightResult>x&&(rightResult<temp||temp<=x)) temp=rightResult;
    }
    if(temp <= x) return 2147483647;
    return temp;
}
int treecpx(int x, int k) {
    if(tree[k].t == false) return 0;
    if(tree[k].p <= x) return 1+treecpx(x,k*2)+treecpx(x,k*2+1);
    else return treecpx(x,k*2);
}
int treexcp(int x,int k){
    if(tree[k].t == false) return -2147483647;
    int leftCount=treecpx(tree[k].p-1,1);
    if(x==leftCount+1) return tree[k].p;
    else if (x <= leftCount) return treexcp(x, k*2);
    else return treexcp(x-leftCount-1, k*2+1);
}
int main(){
    int q;
    cin >> q;
    while(q--){
    	int opt,x;
    	cin >> opt >> x;
    	if(opt==5){
    		treeinsert(x,1);
		}else if(opt==4){
			cout << treeh(x) << endl;
		}else if(opt==3){
			cout << treeq(x) << endl; 
		}else if(opt==2){
			cout << treexcp(x) << endl;
		}else{
			cout << treecpx(x)+1 << endl;
		}
	}
    return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...