编辑代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

struct tree{
	int key;
	tree* left;
	tree* right;
	int height;
};

vector<int> ans;

int height(tree* node){
	if(node==nullptr)return 0;
	return node->height;
}

tree* ll_rotate(tree* y){//LL型 
	tree* x=y->left;
	y->left=x->right;
	x->right=y;
	y->height=max(height(y->left),height(y->right))+1;
	x->height=max(height(x->left),height(x->right))+1;
	return x; 
}

tree* rr_rotate(tree* y){//RR型 
	tree* x=y->right;
	y->right=x->left;
	x->left=y;
	y->height=max(height(y->left),height(y->right))+1;
	x->height=max(height(x->left),height(x->right))+1;
	return x;
}

int getBalance(tree* node){
    if(node==nullptr)return 0;
    return height(node->left)-height(node->right);
}

tree* insert(tree* node,int key){
	if(node==nullptr){
		tree* leaf=new tree();
		leaf->key=key;
		leaf->height=1;
		return leaf;
	}
	if(node->key>key)node->left=insert(node->left,key);
	else if(node->key<key)node->right=insert(node->right,key);
	else return node;
	
	node->height=max(height(node->left),height(node->right))+1;
	int balance=getBalance(node);
	
	if(balance>1&&node->left->key>key)//LL 
		return ll_rotate(node);
	else if(balance<-1&&node->right->key<key)//RR
		return rr_rotate(node);
	else if(balance>1&&node->left->key<key){//LR
		node->left=rr_rotate(node->left);
		return ll_rotate(node);
	}
	else if(balance<-1&&node->right->key>key){//RL
		node->right=ll_rotate(node->right);
		return rr_rotate(node);
	}
	return node;
}

tree* imNext(tree* node){
    tree* temp=node;
    while(temp->left){
        temp=temp->left;
    }
    return temp;
}

tree* deleteNode(tree* node,int key){
    if(node==nullptr)return node;
    if(node->key>key)node->left=deleteNode(node->left,key);
    else if(node->key<key)node->right=deleteNode(node->right,key);
    else{
        if(!node->left&&!node->right){
            delete(node);
            return nullptr;
        }
        else if(node->left&&!node->right)*node=*(node->left);
        else if(!node->left&&node->right)*node=*(node->right);
        else{
            tree* next=imNext(node->right);
            node->key=next->key;
            node->right=deleteNode(node->right,next->key);
        }
    }

    node->height=max(height(node->left),height(node->right))+1;
    int balance=height(node->left)-height(node->right);
    if(balance>1&&getBalance(node->left)>=0)//左子树的左子树最高，LL
    	return ll_rotate(node);
    else if(balance<-1&&getBalance(node->right)<=0)//右子树的右子树最高，RR
    	return rr_rotate(node);
    else if(balance>1&&getBalance(node->left)<0){//左子树的右子树最高，LR
        node->left=rr_rotate(node->left);
        return ll_rotate(node);
    }
    else if(balance<-1&&getBalance(node->right)>0){//右子树的左子树最高，RL
        node->right=ll_rotate(node->right);
        return rr_rotate(node);
    }
    return node;
}

void preOrder(tree* node){
	if(node){
		ans.push_back(node->key);
		preOrder(node->left);
		preOrder(node->right);
	}
}

void print(tree* node){
    ans.clear();
    preOrder(node);
    for(int i=0;i<ans.size()-1;i++)
    	cout<<ans[i]<<" ";
    cout<<ans[ans.size()-1]<<endl;
}

int main(){
	tree* root=nullptr;
	int n,k,j;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>k;
		root=insert(root,k);
	}
    print(root);
    cin>>j;
	root=deleteNode(root,j);
    print(root);

    return 0;
}