爱华网对删除来说，我们考虑包含被删除元素的节点p 的三种情况：1) p 是树叶；2) p 只有一个
非空子树；3) p 有两个非空子树。
情况1) 可以用丢弃树叶节点的方法来处理。要删除图11-3b 所示树中的3 5，只要把其父节
点的左孩子域置为零，然后删除该节点即可，删除后结果如图 11-3a 所示。要从树中删除8 0，
只要把节点4 0的右孩子域置为零并丢弃节点8 0，其结果如图11-1b 所示。
接下来考察情况2 )。如果p 没有父节点（即p 是根节点） ，则将p 丢弃，p 的唯一子树的根
节点成为新的搜索树的根节点。如果p 有父节点p p，则修改pp 的指针，使得pp 指向p 的唯一孩
子，然后删除节点p。例如，如果希望从图11-3b 的树中删除关键值为5的元素，则修改该元素
父节点的左孩子域，使其指向关键值为2的节点。
最后，要删除一个左右子树都不为空的节点中的元素，只需将该元素替换为它的左子树中
的最大元素或右子树中的最小元素。假设希望删除图 11-4a 中关键值为4 0的元素，那么既可以
用它左子树中的最大元素( 3 5 )，也可以用它右子树中的最小元素（6 0）来替换它。如果选择右
子树中的最小元素，那么把关键值为6 0的元素移到4 0被删除的位置，再把原来的叶节点6 0删除
即可。结果如图11-4b 所示。
假定用左子树中的最大元素来代替被删除的元素4 0。左子树中的最大元素是3 5，且只有一
个子女，把3 5移到4 0的节点中，将其左孩子指向原来节点3 5的唯一子女，结果如图11-4c 所示。
再来看另一个例子，删除图11-4c 中的节点3 0。既可以用5，也可以用3 1来替换节点3 0。如
果选用5，而5是只有一个孩子的节点，那么只要把其左孩子域指向 5原来的唯一子女即可，结
3 2 4 第二部分 数 据 结 构
下载果如图11-4d 所示。如果选用3 1替换3 0，而原来的3 1是树叶节点，那么只需删除该树叶节点。
图11-4 二叉搜索树中元素的删除
注意， 必须确保右子树中的最小元素以及左子树中的最大元素既不会在没有子树的节点中，
也不会在只有一个子树的节点中。可以按下述方法来查找到左子树中的最大元素：首先移动到
子树的根，然后沿着各节点的右孩子指针移动，直到右孩子指针为 0为止。类似地，也可以找
到右子树中的最小元素：首先移动到子树的根，然后沿着各节点的左孩子指针移动，直到左孩
子指针为0为止。
