用插入的方法建树
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];
}
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)