©2020-2024 ioDraw All rights reserved,
Privacy Policy
* 当要删除的结点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); //此时又回到了前面两种情况，则进行递归 } }