
先看一个简单的树图
删除节点是分以下几种情况:
1.待删节点为叶子节点:此种情况下直接删除叶子节点即可
2.待删节点只有左子树,或只有右子树,那么将左子树或右子树的根节点替换该节点即可
3.待删节点既有左子树,又有右子树,那么就需要先找到该节点的后继节点,用后继节点替换该节点。
head为树的根节点,详细情况请看下一个文章
void trytree::del(int data){//删除节点
node * n=head;
node * parent;
while(n!=NULL){//寻找待删除节点
if(data>n->data){//向右找
parent=n;
n=n->right;
}else if(data<n->data){//向左找
parent=n;
n=n->left;
}else{//相等即待除节点
if(n->left!=NULL&&n->right==NULL){//左节点不为空右节点为空
if(parent->left==n){
parent->left=n->left;
delete(n);
return;
}else{
parent->right=n->left;
delete(n);
return;
}
}else if(n->left==NULL&&n->right!=NULL){//右节点不为空左节点为空
if(parent->left==n){
parent->left=n->right;
delete(n);
return;
}else{
parent->right=n->right;
delete(n);
return;
}
}else if(n->left==NULL&&n->right==NULL){//待删除的节点为叶子节点
if(parent->left==n){
parent->left=NULL;
delete(n);
return;
}else{
parent->right=NULL;
delete(n);
return;
}
}else{//左右孩子节点都不为空
node * sub=n->right;
if(sub->left==NULL){//sub为后继节点
sub->left=n->left;
if(parent->left==n){
parent->left=sub;
delete(n);
return;
}else{
parent->right=sub;
delete(n);
return;
}
}else{
node * p=sub;//后继节点的父节点
while(sub->left!=NULL){//寻找后继节点
p=sub;
sub=sub->left;
}
p->left=NULL;
if(parent->left==n){
sub->left=n->left;
sub->right=n->right;
parent->left=sub;
delete(n);
return;
}else{
sub->left=n->left;
sub->right=n->right;
parent->right=sub;
delete(n);
return;
}
}
}
}
}
cout<<"没有找到"<<endl;
return;
}