嗯...就是贴个板子
#include <bits/stdc++.h>
using namespace std;
struct node{
int num;
node *p, *l, *r;
};
node *root, *null;
int n, xx;
string str;
void p_inorder(node *x){ // 中序遍历
if(x == null) return ;
p_inorder(x -> l);
printf(" %d", x -> num);
p_inorder(x -> r);
return ;
}
void p_preorder(node *x){ // 前序遍历
if(x == null) return ;
printf(" %d", x -> num);
p_preorder(x -> l);
p_preorder(x -> r);
return ;
}
bool find(int a){ // 查询
node *x = root;
while(x != null){
if(x -> num == a) return true;
if(a > x -> num) x = x -> r;
else x = x -> l;
}
return false;
}
void insert(int a){ // 插入
node *x = root, *y = null;
node *z = new node();
z -> num = a;
z -> l = null; z -> r = null;
while(x != null){
y = x;
if(z -> num < x -> num) x = x -> l;
else x = x -> r;
}
z -> p = y;
if(y == null) root = z;
else{
if(z -> num < y -> num) y -> l = z;
else y -> r = z;
}
return ;
}
void del(int x){
node *p = root , *par;
while(p -> num != x){
if(p -> num > x){
par = p;
p = p -> l;
}
else{
par = p;
p = p -> r;
}
}
if(p -> l == null && p -> r == null){
if(par -> l == p) par -> l = null;
else if(par -> r == p) par -> r = null;
delete p;
return ;
}
if(p -> l != null && p -> r == null){
if(p == root) root = p -> l;
else if(par -> l == p) par -> l = p -> l;
else if(par -> r == p) par -> r = p -> l;
delete p;
return ;
}
else if(p -> l == null && p -> r != null){
if(p == root) root = p -> r;
else if(par -> l == p) par -> l = p -> r;
else if(par -> r == p) par -> r = p -> r;
delete p;
return ;
}
else if(p -> l != null && p -> r != null){
node *left = p -> r;
par = p;
while(left -> l){
par = left;
left = left -> l;
}
p -> num = left -> num;
if(par -> l == left) par -> l = left -> r;
else if(par -> r == left) par -> r = left -> r;
delete left;
return ;
}
}
int main()
{
scanf("%d", &n);
for(int i=0;i<n;i++){
cin>>str;
if(str == "insert"){
scanf("%d", &xx);
insert(xx);
}
else if(str == "find"){
scanf("%d", &xx);
if(find(xx)) puts("yes");
else puts("no");
}
else if(str == "delete"){
scanf("%d", &xx);
del(xx);
}
else{
p_inorder(root);
puts("");
p_preorder(root);
puts("");
}
}
return 0;
}