当前位置 博文首页 > xiexiexiexieqing的博客：二叉搜索树的删除（c程序 干货满满）
?
目录
分析
代码实现
总结
?删除二叉树分的话可以分成很多类 当然也要熟悉二叉树的遍历
（删除节点没有子节点，存在一个子节点，存在两个子节点? 然后存在的话又要分类）
很繁琐 所以这套方法可以分两类。
1.删除节点的子节点都存在
2.删除节点的子节点最多存在一个
?
假设在这样一个搜索树中 删除如图红色节点
删除这个红色的节点存在两个子节点
然后我们去找红色节点的 左边最大 的节点或者 右边最小?的节点
（两个方法都可以 我们用左边最大）
?
用蓝色代表 左边最大
然后将蓝色节点里面的 数据 赋给红色节点里的数据
?
?
赋完值后 存在两个数据为45的节点 但是 搜索树是不可以存在两个相同数据的节点
所以要删除蓝色节点，蓝色节点的子节点只可能是一个或者没有（因为找 左边的最大 相当于找左子树的最右边 蓝色节点 一定在最右边所以没有右节点 但是蓝色节点的右节点不确定）?
所以在定义一个 绿色节点 把蓝色节点的?子节点? 赋给这个?绿色节点
?
然后把 蓝色节点的父节点 连接?这个绿色节点?
最后把蓝色节点 释放掉就ok了
?
//删除
void del(struct node*root,int data)
{
struct node*pnode=root;
struct node*pnodeparent;
while(pnode!=NULL && pnode->data!=data) //先找到这个节点
{
pnodeparent=pnode; //父节点必须在子节点上面
if(data>pnode->data)
pnode=pnode->right;
else
pnode=pnode->left;
}
if(pnode==NULL) //当pnode为空 意思是把这颗树都找遍了 还是没有
{
printf("没有"); //所以 返回时 要有一个提示
return ;
}
if(pnode->left!=NULL&&pnode->right!=NULL) //删除节点的子节点都存在
{
struct node*pmove=pnode->left; //找左边的最大节点
struct node*pmoveparent;
while(pmove->right!=NULL)
{
pmoveparent=pmove;
pmove=pmove->right;
}
pnode->data=pmove->data; //把这个最大节点的值赋给 删除节点
pnode=pmove; //现在相当于删除这个 最大节点
pnodeparent=pmoveparent;
}
struct node*snode; //定义一个节点
if(pnode->left!=NULL) //获取 最大节点的子节点
snode=pnode->left;
else //不存在子节点就赋值NULL
snode=NULL;
if(pnodeparent==NULL) //如果父节点为空那么就是 空树 还是把获取到的节点给它
pnodeparent=snode;
else if(pnodeparent->right==pnode)
pnodeparent->right=snode;
else
pnodeparent->left=snode;
free(pnode);
} ?
1.删除节点的子节点都存在
就直接去找 它的左边最大 或者 右边最小 用 两者之一 在释放 这个最值节点
?
2.删除节点的子节点最多存在一个
直接让删除节点的父节点?连接?删除节点的子节点? 释放删除节点
?
?
?
cs