二叉排序树的删除操作


* 当要删除的结点z是叶子结点的时候，可以直接删除（判断z的左右指针是否为空，若均为空则直接删除结点z）
*
当要删除的结点z只有左子树（右子树）的时候，将z的左子树（右子树）的结点与z进行互换（若该结点的左指针（右指针）不为空，则将左子树（右子树）的data值赋给z的data）
*
当要删除的结点z既有左子树，又有右子树时，令z的中序遍历的直接后继（直接前驱）替代z，也就是找到z的右子树（左子树）中值最小（最大）的结点与其进行替代，然后从二叉排序树中删去这个直接后继（前驱）结点，这样就转换成了第一或者第二种情况。
以下是第三种情况的一个举例

代码 typedef int elem; typedef struct tree{ int data; struct tree *left,*right;
}tree; tree BST_delete(tree &T,tree E){ tree *p,*q; if (p->left==NULL)
//被删除结点的左孩子为空 { q = p->right; p->data = p->right->data; delete(q); } else if (p
->right==NULL){ //被删除结点的右孩子为空 q = p->left; p->data = p->left->data; delete(q); }
else{ //被删除结点左右子树均存在 q = p->right; int a; //右子树中结点最小的值 p->data = a; BST_delete(T
,q); //此时又回到了前面两种情况，则进行递归 } }

技术
下载桌面版
GitHub
Microsoft Store
SourceForge
Gitee
百度网盘（提取码：draw）
云服务器优惠
华为云优惠券
京东云优惠券
腾讯云优惠券
阿里云优惠券
Vultr优惠券
站点信息
问题反馈
邮箱：[email protected]
吐槽一下
QQ群：766591547
关注微信
©2020-2025 ioDraw All rights reserved, Privacy Policy