置，然后根据节点分以下情况：
1452
删除它
451
图SEQ图ARABIC2
情况一，该节点是叶节点叶节点没有非空子节点的节点，直接把节点删除即可。情况一叶节点情况二，链节点只有一个非空子节点的节点，为了删除这个节点而不影响它的子树，情况二该节点是链节点链节点需要把它的子节点代替它的位置，然后把它删除。如图2所示，删除节点2时，需要把它的左子节点代替它的位置。情况三，该节点有两个非空子节点。由于情况比较复杂，一般的策略是用它右子树的最小值情况三来代替它，然后把它删除。如图3所示，删除节点2时，在它的右子树中找到最小的节点3，该节点一定为待删除节点的后继后继。删除节点3它可能是叶节点或者链节点，然后把节点2后继的值改为3。实际上在实现的时候，情况一和情况二是可以一样对待的，因为用叶节点的子节点代替它本身，就是用空节点代替了它，等同于删除。对待情况三除了可以用后继代替本身以外，我们还可以使用它的前驱左子树的最大值代替它本身。
删除它
126745
f3136754
图SEQ图ARABIC3
牵涉到的查找最小值的问题，章节三44有详细讨论。基本方法就是从子树的根节点开始，如果左子节点不为空，那么就访问左子节点，直到左子节点为空，当前节点就是该子树的最小值节点。删除它只需用它的右子节点代替它本身。代码5给出了在一个给定的二叉查找树中删除值2的完整代码。BST_Noderooti
tFi
d_DeleteMi
BST_NodeP返回子树的最小值并删除节点指针要传递引用返回子树的最小值并删除ifPleft如果已经没有左子节点删除它如果已经没有左子节点，如果已经没有左子节点，BST_NodetPi
trPvaluePPrightdeletetretur
relseretur
Fi
d_DeleteMi
Pleft如果还有左子节点访问左子节点如果还有左子节点，如果还有左子节点，voidBST_DeleteBST_NodePi
tvalue节点指针要传递引用节点指针要传递引用ifPretur
查找失败BST中不存在要删除的节点查找失败，查找失败，ifPvaluevalue查找成功对其删除查找成功，查找成功，ifPleftPrightPvalueFi
d_DeleteMi
PrightelseBST_NodetPifPleftPPleft
felsePPrightdeletetelseifvaluePvalueBST_DeletePleftvalue在左子树中查找在左子树中查找elseBST_DeletePrightvalue在右子树中查找在右子树中查找
i
tmai
BST_Deleteroot2在BST中删除值中删除值2在retur
0
代码5
3二叉查找树的平衡性问题讨论
二叉查找树的效果究竟如何？事实上，随机的进行NNr