二叉排序树的节点删除可能要面临的问题：删除某个节点后相应的树可能散架。为此必须考虑在子树存在的情况下用子树来填补被删除节点的空间。二叉排序树的节点删除有以下两种方法：

　　(1)标志位法：给节点添加一个标志位flag，0表示此节点可用；1表示此节点已被删除。在做插入运算时此节点继续运用，但在遍历和查询时此节点不参与运算。这种方法的优点是简单，适用于只会发生少量刷除的情况。但多次删除会在集合中留下大量冗余数据。此种方法只需在删除时找到此节点并修改标志位(0改为1)，在遍历时加个判断，标志位为0才能显示。方法图解如下。

　　程序代码：

　　运行结果：

　　练习１：用列表[10,6,15,9,3,13,7,16,8]构建二叉排序树，用标志位法（伪删除法）删除6和15节点，然后用四种遍历方法遍历。

　　(2)节点删除法：从集合中硬删除，此节点在原树中不复存在。此种删除需考虑如下三种情况：①被删除的节点是叶子节点。②被删除的节点只有左子树或者只有右子树。③被删除的节点既有左子树，也有右子树。这种方法虽然比较复杂，但树中无冗余数据，也不用修改树的遍历方法。

　　另外，以上三种情况必须同时考虑被删除节点是否是根节点。下面对这三种情况分别进行讨论。

　　情况1：由于要删除的节点p既无左子树，又无右子树，因此删除节点p之后不会破坏二叉排序树结构的完整性，只要将其父节点原来指向被删除节点p的指针改为指向空即可(如果是根节点，根节点指针置空)，如下图所示。

　　情祝2：要删除的节点p只有左子树PL或者右子树PR，这时只要将p的左子树PL或p的右子树PR直接作为其父节点的相应左子树或右子树即可（如果是根节点，根节点指针指向PL或PR），如下图所示。

　　情祝3：要删除的节点p既有左子树PL也有右子树PR(左、右指针均不为空)，节点只可用它的子树中的节点替代，不可删除。根据二叉排序树的特点，这个节点的值要比左树中的值都大，比右树中的值都小，所以只能用右树中的最小值替代。因此，这种情况需要进行两步操作：

    ①首先找到待删除节点右子树中最小的那个值，也就是右子树中位于最左方的那个节点，然后将这个节点的值的父节点记录下来，并且将该节点的值赋给要删除的节点，也就是覆盖。

    ②然后将右子树中最小的那个节点进行删除，该节点肯定符合上述两步中的某一步，要么是叶子节点，按步骤①进行删除；要么是只含有右子树的节点，按步骤②进行删除，如下图所示。

　　程序代码：

　　运行结果：

　　练习２：用列表[10,6,15,9,3,13,7,16,8]构建二叉排序树，用节点删除法删除6和15节点，然后用四种遍历方法遍历，对比练习１看看有何不同。提示：上例中，导入FlagSortTree，把RemoveSortTree(SortTree)改为RemoveSortTree(FlagSortTree)，即可获得标志位法和节点删除法功能，以及四种遍历功能。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社