二叉搜索树

1.二叉搜索树的建树

用插入的方法建树

void build(int root,int x){
	if(tree[root]==-1){//空的 
		tree[root]=x;
		return;
	}
	if(tree[root]>=x){//往左 
		build(root*2,x); 
	}
	else{//往右 
		build(root*2+1,x);
	}
}

2.二叉搜索树的查找

首先和根节点比,如果比根节点小,就往左边查,如果比根节点大,就往右边查,直到找到或完全找不到为止

bool search(int root int x){
	while(tree[root]!=-1){
		if(tree[root]==x) return true;//找到了
		else if(tree[root]>x) root*=2;
		else if(tree[root]<x) root=root*2+1; 
	}
	return false;
}

3.二叉搜索树的遍历 前序遍历

void pre_read(int root){
	if(tree[root]==-1) return ;
	cout<<tree[root];
	pre_read(root*2);
	pre_read(root*2+1);
}

中序遍历

void in_read(int root){//中序遍历 
	if(tree[root]==-1) return;
	else{
		in_read(root*2);
		cout<<tree[root];
		in_read(root*2+1);	
	}
}

后序遍历

void post_read(int root){
	if(tree[root]==-1) return;
	else{
	post_read(root*2);
	post_read(root*2+1);
	cout<<tree[root];	
	}
}

二叉搜索树的删除 1.找最小值(后面要用)

int findmin(int root ){//找最小值 
	if(tree[root*2]!=-1){
		findmin(root*2);
	}
	return tree[root*2];
} 

2.删除 *** 作

看要删除的节点有没有子节点,如果没有就直接将值设置为-1，如果有一个子节点就将该子节点的值赋给要删的节点，然后删除子节点,如果有两个子节点,就找右子树最小的节点替换要删除的节点，然后删除右子树最小的节点

int Delete(int root,int x){
	if(x<tree[root]){
		Delete(root*2,x);//往左边找 
	}
	else if(x>tree[root]){
		Delete(root*2+1,x);//往右边找 
	}
	else{
		if(tree[root*2]==-1&&tree[root*2+1]==-1){
			tree[root]=-1;
		}
		else if(tree[root*2]!=-1&&tree[root*2+1]!=-1){
			int key=findmin(root*2+1);//用右子树最小的值替换该值 
			tree[root]=key;
			Delete(root*2+1,key);//删除这个最小值所对应的节点 
		}
		else{
			if(tree[root*2]==-1){
				tree[root]=tree[root*2+1];
				Delete(root*2+1,tree[root*2+1]);
			}
			else if(tree[root*2+1]==-1){
				tree[root]=tree[root*2];
				Delete(root*2,tree[root*2]);
			}
		}
	}
}

L2-004 这是二叉搜索树吗？

#include
using namespace std;
int pre[2000];
vector<int>v;
int flag=0;//为0是查找二叉搜索树,为1查找镜像二叉搜索树 
void find(int l,int r){
	if(l>r) return;
	int l1=l+1;
	int r1=r;
	if(!flag){
		while(l1<=r&&pre[l1]<pre[l]) l1++;//左子树的比根节点小 
		while(r1>l&&pre[r1]>=pre[l]) r1--;//右子树比根节点大,l是根 
	}
	else{
		while(l1<=r&&pre[l1]>=pre[l]) l1++;//镜像左子树的比根节点大 
		while(r1>l&&pre[r1]<pre[l]) r1--;//镜像右子树比根节点小,l是根 
	}
	if(l1-r1!=1) return;//不符合前序遍历要求 
	find(l+1,r1);//看左子树是否符合 
	find(l1,r);//看右子树是否符合 
	v.push_back(pre[l]);
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>pre[i]; 
	}
	find(0,n-1);//验证0~n-1;
	if(v.size()!=n){
		flag=1;
		v.clear();
		find(0,n-1);
	}
	if(v.size()!=n) cout<<"NO"<<endl;
	else{
		cout<<"YES"<<endl;
		cout<<v[0];
		for(int i=1;i<n;i++){
			cout<<" "<<v[i];
		}
	}
}