难点主要在于删除部分
| 题目描述487： | |
| 二叉排序树的插入删除和查找 pre: 前序遍历 输出： 样例输入： 样例输出： 31 15 9 5 4 2 7 8 50 42 注意：在样例中，先把15删除掉了，然后再插入15，观察最开始的三个遍历，和最后的三次遍历，遍历结果是有区别的。 |
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,f;
int l[N],r[N];
int a[N],fa[N];//fa[i]为编号i的父节点
int idx = 1,root = 1;//给每个值编号
void dfs(int u, int x)//建树过程
{
if(l[u]==0 && a[u]>x)
{
fa[idx] = u;//记录父节点
l[u] = idx; //左孩子为空则先给左孩子
return ;
}
if(r[u]==0 && a[u]<x)
{
fa[idx] = u;//记录父节点
r[u] = idx; //有孩子为空，赋给右孩子
return ;
}
if(a[u] > x) dfs(l[u], x);//u节点大于x 递归左边
if(a[u] < x) dfs(r[u], x);//u节点小于x 递归右边
}
void insert(int x)//插入
{
if(idx != 1)//寻找父节点
dfs(root, x);
a[idx++] = x;//给新节点编号
}
void pre(int u)//前序输出
{
if(a[u] == 0) return ;
cout<<a[u]<<" ";
pre(l[u]);
pre(r[u]);
}
void in(int u)//中序输出
{
if(a[u] == 0) return ;
in(l[u]);
cout<<a[u]<<" ";
in(r[u]);
}
void post(int u)//后序输出
{
if(a[u] == 0) return ;
post(l[u]);
post(r[u]);
cout<<a[u]<<" ";
}
int dfs1(int u)
{
if(r[u] == 0) return u;
dfs1(r[u]);
}
int dfs2(int u)
{
if(l[u] == 0) return u;
dfs2(l[u]);
}
void del(int u, int x)
{
if(a[u] == 0) return ;
if(a[u] == x)
{
cout<<"TRUE"<<endl;
f = 1; //标记为0时说明没找到x
if(l[u])
{
int u1 = dfs1(l[u]);//找左子树中最大元素
if(u == root) root = u1;//换根
if(r[fa[u1]] == u1) r[fa[u1]] = 0;//删除u1父节点存的自己
fa[u1] = fa[u];//将u的父节点赋给u1
if(l[fa[u]] == u) l[fa[u]] = u1;//u为父亲的左孩子，u2替换u
if(r[fa[u]] == u) r[fa[u]] = u1;//u为父亲的右孩子，u2替换u
if(l[u] != u1) l[u1] = l[u];//当u的左节点不为u1时，u1继承u的左孩子
r[u1] = r[u],fa[r[u]] = u1;//u1继承u的右孩子
return ;
}
if(r[u])//无左孩子时
{
int u2 = dfs2(r[u]);//找右子树中最小元素
if(u == root) root = u2;//换根
if(l[fa[u2]] == u2) l[fa[u2]] = 0;//删除u2父节点存的自己
fa[u2] = fa[u];//将u的父节点赋给u2
if(l[fa[u]] == u) l[fa[u]] = u2;//若u为父亲的左儿子，u2替换u
if(r[fa[u]] == u) r[fa[u]] = u2;//若u为父亲的右儿子，u2替换u
if(r[u] != u2) r[u2] = r[u];//当u的右节点不为u2时，u2继承u的右孩子
l[u2] = l[u],fa[l[u]] = u2;//u2继承u的左孩子
return ;
}
//左右孩子都没有
if(l[fa[u]] == u) l[fa[u]] = 0;//若x为父亲的左儿子，删除自己
if(r[fa[u]] == u) r[fa[u]] = 0;//若x为父亲的右儿子，删除自己
return ;
}
if(a[u] > x)del(l[u], x);//u节点大于x 递归左边
if(a[u] < x)del(r[u], x);//u节点小于x 递归右边
}
void search(int u, int x)
{
if(a[u] == 0) return ;
if(a[u] == x)
{
cout<<"YES"<<endl;
f = 1;
return ;
}
if(a[u] > x)search(l[u], x);//u节点大于x 递归左边
if(a[u] < x)search(r[u], x);//u节点小于x 递归右边
}
int main()
{
cin>>n;
while(n--)
{
int x;
cin>>x;
insert(x);
}
while(1)
{
string s;
cin>>s;
if(s == "pre") pre(root),cout<<endl;
if(s == "in") in(root),cout<<endl;
if(s == "post") post(root),cout<<endl;
if(s == "insert")
{
int x;
cin>>x;
insert(x);
}
if(s == "delete")
{
int x;
cin>>x;
del(root, x);
if(f ==0) cout<<"FALSE"<<endl;
f = 0;
}
if(s == "search")
{
int x;
cin>>x;
search(root, x);
if(f == 0) cout<<"NO"<<endl;
f = 0;
}
if(s == "exit") break;
}
}