题目描述
给出一个数据序列，建立二叉排序树，并实现删除功能
对二叉排序树进行中序遍历，可以得到有序的数据序列
输入
第一行输入t，表示有t个数据序列
第二行输入n，表示首个序列包含n个数据
第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开
第四行输入m，表示要删除m个数据
从第五行起，输入m行，每行一个要删除的数据，都是自然数
以此类推输入下一个示例
输出
第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到
从第二行起，输出删除第m个数据后的有序序列，输出m行
以此类推输出下一个示例的结果
输入样例1
1 6 22 33 55 66 11 44 3 66 22 77
输出样例1
11 22 33 44 55 66 11 22 33 44 55 11 33 44 55 11 33 44 55
AC代码
代码语言：javascript复制#include <iostream>
using namespace std;
struct Node{
int data;
Node*left=NULL;
Node*right=NULL;
};
class BST{
Node*root=NULL;
public:
void Insert(int&data){
Node*newOne=new Node();
newOne->data=data;
if(root==NULL){
root=newOne;
return;
}
Node*current=root;
while(current){
if(current->data>data){
if(current->left)
current=current->left;
else{
current->left=newOne;
return;
}
}
else{
if(current->right)
current=current->right;
else{
current->right=newOne;
return;
}
}
}
}
void Delete(int&data){
Node*current=root,*parent=root;
string kind;
while(current){
if(current->data==data){
if(current->left==NULL&¤t->right==NULL){
delete current;
if(kind=="left")
parent->left=NULL;
else if(kind=="right")
parent->right=NULL;
return;
}else if(current->left&¤t->right==NULL){
if(current==root){
root=current->left;
delete current;
return;
}
if(kind=="left")
parent->left=current->left;
else
parent->right=current->left;
delete current;
return;
}else if(current->right&¤t->left==NULL){
if(current==root){
root=current->right;
delete current;
return;
}
if(kind=="left")
parent->left=current->right;
else
parent->right=current->right;
delete current;
return;
}else{
if(current->left->right==NULL){
current->left->right=current->right;
if(current==root){
root=current->left;
delete current;
return;
}
if(kind=="left")
parent->left=current->left;
else
parent->right=current->left;
delete current;
return;
}else{
Node*right=current->left->right,*temp;
while(right->right){
temp=right;
right=right->right;
if(right->right==NULL)
temp->right=NULL;
}
if(right->left==NULL){
right->left=current->left;
right->right=current->right;
if(current==root){
root=right;
delete current;
return;
}
if(kind=="left")
parent->left=right;
else
parent->right=right;
delete current;
return;
}else{
temp->right=right->left;
right->left=current->left;
right->right=current->right;
if(current==root){
root=right;
delete current;
return;
}
if(kind=="left")
parent->left=right;
else
parent->right=right;
delete current;
return;
}
}
}
}
else if(current->data>data){
kind="left";
parent=current;
current=current->left;
}else{
kind="right";
parent=current;
current=current->right;
}
}
}
void Traverse(Node*current){
if(current==NULL)
return;
Traverse(current->left);
cout<<current->data<<' ';
Traverse(current->right);
}
void Show(){
Traverse(root);
cout<<endl;
}
};
int main() {
int t,n,m,temp;
cin>>t;
while(t--){
BST test;
cin>>n;
while(n--){
cin>>temp;
test.Insert(temp);
}
test.Show();
cin>>m;
while(m--){
cin>>temp;
test.Delete(temp);
test.Show();
}
}
return 0;
}
