社区讨论
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 条回复,欢迎继续交流。
正在加载回复...