[悬2关]二叉搜索树求调
查看原帖
[悬2关]二叉搜索树求调
373198
WhileTrueRP楼主2023/11/16 20:56
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;
int a[N];
struct node{
	int key;
	node* left;
	node* right;
	int size;
};
bool search(node* root,int val){
	if(root == nullptr){
		return false;
	}
	if(root->key < val){
		return search(root->right,val);
	}else if(root->key > val){
		return search(root->left,val);
	}else{
		return true;
	}
}
node* insert(node* root,int val){
	if(root == nullptr){
		node* x = new node;
		x->key = val;
		return x;
	}
	root->size ++;
	if(root->key > val){
		root->left = insert(root->left,val);
	}else if(root->key < val){
		root->right = insert(root->right,val);
	}
	return root;
}
int querykth(node* root,int k){
	if(root->left){
		if(root->left->size >= k){
			return querykth(root->left,k);
		}
	}else if(k == 1){
		return root->key;
	}else{
		return querykth(root->right,k-(root->left?root->left->size:0)-1);
	}
}
int main(){
	int n,k;
	node* root = new node;
	scanf("%d%d",&n,&k);
	scanf("%d",&a[1]);
	root->key = a[1];
	for(int i=2;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=2;i<=n;i++){
		if(search(root,a[i]) == false){
			cout<<a[i]<<' ';
			insert(root,a[i]);
		}
//		puts("+"); 
	}
	printf("%d",querykth(root,k));
}
2023/11/16 20:56
加载中...