实现始终通过查看左子树并查找最右侧子节点来查找有序前驱

计算机科学中最常用和讨论最多的数据结构之一是二叉搜索树。这通常是引入的第一个具有非线性插入算法的数据结构。二叉搜索树类似于双链表，每个节点包含一些数据，以及两个指向其他节点的指针；它们在这些节点彼此相关联的方式上有所不同。二叉搜索树节点的指针通常被称为“左”和“右”，用来指示与当前值相关的子树。这种节点的简单　ＪａｖａＳｃｒｉｐｔ　实现如下：

ｖａｒ　ｎｏｄｅ　＝　｛
　　　　ｖａｌｕｅ：　１２５，
　　　　ｌｅｆｔ：　ｎｕｌｌ，
　　　　ｒｉｇｈｔ：　ｎｕｌｌ
｝；

从名称中可以看出，二叉搜索树被组织成分层的树状结构。第一个项目成为根节点，每个附加值作为该根的祖先添加到树中。但是，二叉搜索树节点上的值是唯一的，根据它们包含的值进行排序：作为节点左子树的值总是小于节点的值，右子树中的值都是大于节点的值。通过这种方式，在二叉搜索树中查找值变得非常简单，只要你要查找的值小于正在处理的节点则向左，如果值更大，则向右移动。二叉搜索树中不能有重复项，因为重复会破坏这种关系。下图表示一个简单的二叉搜索树。

上图表示一个二叉搜索树，其根的值为　８。当添加值　３　时，它成为根的左子节点，因为　３　小于　８。当添加值　１　时，它成为　３　的左子节点，因为　１　小于　８（所以向左）然后　１　小于３（再向左）。当添加值　１０　时，它成为跟的右子节点，因为　１０　大于　８。不断用此过程继续处理值　６，４，７，１４　和　１３。此二叉搜索树的深度为　３，表示距离根最远的节点是三个节点。

二叉搜索树以自然排序的顺序结束，因此可用于快速查找数据，因为你可以立即消除每个步骤的可能性。通过限制需要查找的节点数量，可以更快地进行搜索。假设你要在上面的树中找到值　６。从根开始，确定　６　小于　８，因此前往根的左子节点。由于　６　大于　３，因此你将前往右侧节点。你就能找到正确的值。所以你只需访问三个而不是九个节点来查找这个值。

要在　ＪａｖａＳｃｒｉｐｔ　中实现二叉搜索树，第一步要先定义基本接口：

ｆｕｎｃｔｉｏｎ　ＢｉｎａｒｙＳｅａｒｃｈＴｒｅｅ（）　｛
　　　　ｔｈｉｓ．＿ｒｏｏｔ　＝　ｎｕｌｌ；
｝
ＢｉｎａｒｙＳｅａｒｃｈＴｒｅｅ．ｐｒｏｔｏｔｙｐｅ　＝　｛
　　　　／／ｒｅｓｔｏｒｅ　ｃｏｎｓｔｒｕｃｔｏｒ
　　　　ｃｏｎｓｔｒｕｃｔｏｒ：　ＢｉｎａｒｙＳｅａｒｃｈＴｒｅｅ，
　　　　ａｄｄ：　ｆｕｎｃｔｉｏｎ　（ｖａｌｕｅ）｛
　　　　｝，
　　　　ｃｏｎｔａｉｎｓ：　ｆｕｎｃｔｉｏｎ（ｖａｌｕｅ）｛
　　　　｝，
　　　　ｒｅｍｏｖｅ：　ｆｕｎｃｔｉｏｎ（ｖａｌｕｅ）｛
　　　　｝，
　　　　ｓｉｚｅ：　ｆｕｎｃｔｉｏｎ（）｛
　　　　｝，
　　　　ｔｏＡｒｒａｙ：　ｆｕｎｃｔｉｏｎ（）｛
　　　　｝，
　　　　ｔｏＳｔｒｉｎｇ：　ｆｕｎｃｔｉｏｎ（）｛
　　　　｝
｝；

基本接与其他数据结构类似，有添加和删除值的方法。我还添加了一些方便的方法，ｓｉｚｅ（），ｔｏＡｒｒａｙ（）和ｔｏＳｔｒｉｎｇ（），它们对　ＪａｖａＳｃｒｉｐｔ　很有用。

要掌握使用二叉搜索树的方法，最好从　ｃｏｎｔａｉｎｓ（）　方法开始。　ｃｏｎｔａｉｎｓ（）　方法接受一个值作为参数，如果值存在于树中则返回　ｔｒｕｅ，否则返回　ｆａｌｓｅ。此方法遵循基本的二叉搜索算法来确定该值是否存在：

ＢｉｎａｒｙＳｅａｒｃｈＴｒｅｅ．ｐｒｏｔｏｔｙｐｅ　＝　｛
　　　　／／ｍｏｒｅ　ｃｏｄｅ
　　　　ｃｏｎｔａｉｎｓ：　ｆｕｎｃｔｉｏｎ（ｖａｌｕｅ）｛
　　　　　　　　ｖａｒ　ｆｏｕｎｄ　　　　　　　＝　ｆａｌｓｅ，
　　　　　　　　　　　　ｃｕｒｒｅｎｔ　　　　　＝　ｔｈｉｓ．＿ｒｏｏｔ
　　　　　　　　／／ｍａｋｅ　ｓｕｒｅ　ｔｈｅｒｅ＇ｓ　ａ　ｎｏｄｅ　ｔｏ　ｓｅａｒｃｈ
　　　　　　　　ｗｈｉｌｅ（！ｆｏｕｎｄ　＆＆　ｃｕｒｒｅｎｔ）｛
　　　　　　　　　　　　／／ｉｆ　ｔｈｅ　ｖａｌｕｅ　ｉｓ　ｌｅｓｓ　ｔｈａｎ　ｔｈｅ　ｃｕｒｒｅｎｔ　ｎｏｄｅ＇ｓ，　ｇｏ　ｌｅｆｔ
　　　　　　　　　　　　ｉｆ　（ｖａｌｕｅ　＜　ｃｕｒｒｅｎｔ．ｖａｌｕｅ）｛
　　　　　　　　　　　　　　　　ｃｕｒｒｅｎｔ　＝　ｃｕｒｒｅｎｔ．ｌｅｆｔ；
　　　　　　　　　　　　／／ｉｆ　ｔｈｅ　ｖａｌｕｅ　ｉｓ　ｇｒｅａｔｅｒ　ｔｈａｎ　ｔｈｅ　ｃｕｒｒｅｎｔ　ｎｏｄｅ＇ｓ，　ｇｏ　ｒｉｇｈｔ
　　　　　　　　　　　　｝　ｅｌｓｅ　ｉｆ　（ｖａｌｕｅ　＞　ｃｕｒｒｅｎｔ．ｖａｌｕｅ）｛
　　　　　　　　　　　　　　　　ｃｕｒｒｅｎｔ　＝　ｃｕｒｒｅｎｔ．ｒｉｇｈｔ；
　　　　　　　　　　　　／／ｖａｌｕｅｓ　ａｒｅ　ｅｑｕａｌ，　ｆｏｕｎｄ　ｉｔ！
　　　　　　　　　　　　｝　ｅｌｓｅ　｛
　　　　　　　　　　　　　　　　ｆｏｕｎｄ　＝　ｔｒｕｅ；
　　　　　　　　　　　　｝
　　　　　　　　｝
　　　　　　　　／／ｏｎｌｙ　ｐｒｏｃｅｅｄ　ｉｆ　ｔｈｅ　ｎｏｄｅ　ｗａｓ　ｆｏｕｎｄ
　　　　　　　　ｒｅｔｕｒｎ　ｆｏｕｎｄ；
　　　　｝，
　　　　／／ｍｏｒｅ　ｃｏｄｅ
｝；

搜索从树的根开始。如果没有添加数据，则可能没有根，所以必须要进行检查。遍历树遵循前面讨论的简单算法：如果要查找的值小于当前节点则向左移动，如果值更大则向右移动。每次都会覆盖　ｃｕｒｒｅｎｔ　指针，直到找到要找的值（在这种情况下　ｆｏｕｎｄ　设置为　ｔｒｕｅ）或者在那个方向上没有更多的节点了（在这种情况下，值不在树上）。

在　ｃｏｎｔａｉｎｓ（）　中使用的方法也可用于在树中插入新值。主要区别在于你要寻找放置新值的位置，而不是在树中查找值：

ＢｉｎａｒｙＳｅａｒｃｈＴｒｅｅ．ｐｒｏｔｏｔｙｐｅ　＝　｛
　　　　／／ｍｏｒｅ　ｃｏｄｅ
　　　　ａｄｄ：　ｆｕｎｃｔｉｏｎ（ｖａｌｕｅ）｛
　　　　　　　　／／ｃｒｅａｔｅ　ａ　ｎｅｗ　ｉｔｅｍ　ｏｂｊｅｃｔ，　ｐｌａｃｅ　ｄａｔａ　ｉｎ
　　　　　　　　ｖａｒ　ｎｏｄｅ　＝　｛
　　　　　　　　　　　　　　　　ｖａｌｕｅ：　ｖａｌｕｅ，
　　　　　　　　　　　　　　　　ｌｅｆｔ：　ｎｕｌｌ，
　　　　　　　　　　　　　　　　ｒｉｇｈｔ：　ｎｕｌｌ
　　　　　　　　　　　　｝，
　　　　　　　　　　　　／／ｕｓｅｄ　ｔｏ　ｔｒａｖｅｒｓｅ　ｔｈｅ　ｓｔｒｕｃｔｕｒｅ
　　　　　　　　　　　　ｃｕｒｒｅｎｔ；
　　　　　　　　／／ｓｐｅｃｉａｌ　ｃａｓｅ：　ｎｏ　ｉｔｅｍｓ　ｉｎ　ｔｈｅ　ｔｒｅｅ　ｙｅｔ
　　　　　　　　ｉｆ　（ｔｈｉｓ．＿ｒｏｏｔ　＝＝＝　ｎｕｌｌ）｛
　　　　　　　　　　　　ｔｈｉｓ．＿ｒｏｏｔ　＝　ｎｏｄｅ；
　　　　　　　　｝　ｅｌｓｅ　｛
　　　　　　　　　　　　ｃｕｒｒｅｎｔ　＝　ｔｈｉｓ．＿ｒｏｏｔ；
　　　　　　　　　　　　ｗｈｉｌｅ（ｔｒｕｅ）｛
　　　　　　　　　　　　　　　　／／ｉｆ　ｔｈｅ　ｎｅｗ　ｖａｌｕｅ　ｉｓ　ｌｅｓｓ　ｔｈａｎ　ｔｈｉｓ　ｎｏｄｅ＇ｓ　ｖａｌｕｅ，　ｇｏ　ｌｅｆｔ
　　　　　　　　　　　　　　　　ｉｆ　（ｖａｌｕｅ　＜　ｃｕｒｒｅｎｔ．ｖａｌｕｅ）｛
　　　　　　　　　　　　　　　　　　　　／／ｉｆ　ｔｈｅｒｅ＇ｓ　ｎｏ　ｌｅｆｔ，　ｔｈｅｎ　ｔｈｅ　ｎｅｗ　ｎｏｄｅ　ｂｅｌｏｎｇｓ　ｔｈｅｒｅ
　　　　　　　　　　　　　　　　　　　　ｉｆ　（ｃｕｒｒｅｎｔ．ｌｅｆｔ　＝＝＝　ｎｕｌｌ）｛
　　　　　　　　　　　　　　　　　　　　　　　　ｃｕｒｒｅｎｔ．ｌｅｆｔ　＝　ｎｏｄｅ；
　　　　　　　　　　　　　　　　　　　　　　　　ｂｒｅａｋ；
　　　　　　　　　　　　　　　　　　　　｝　ｅｌｓｅ　｛
　　　　　　　　　　　　　　　　　　　　　　　　ｃｕｒｒｅｎｔ　＝　ｃｕｒｒｅｎｔ．ｌｅｆｔ；
　　　　　　　　　　　　　　　　　　　　｝
　　　　　　　　　　　　　　　　／／ｉｆ　ｔｈｅ　ｎｅｗ　ｖａｌｕｅ　ｉｓ　ｇｒｅａｔｅｒ　ｔｈａｎ　ｔｈｉｓ　ｎｏｄｅ＇ｓ　ｖａｌｕｅ，　ｇｏ　ｒｉｇｈｔ
　　　　　　　　　　　　　　　　｝　ｅｌｓｅ　ｉｆ　（ｖａｌｕｅ　＞　ｃｕｒｒｅｎｔ．ｖａｌｕｅ）｛
　　　　　　　　　　　　　　　　　　　　／／ｉｆ　ｔｈｅｒｅ＇ｓ　ｎｏ　ｒｉｇｈｔ，　ｔｈｅｎ　ｔｈｅ　ｎｅｗ　ｎｏｄｅ　ｂｅｌｏｎｇｓ　ｔｈｅｒｅ
　　　　　　　　　　　　　　　　　　　　ｉｆ　（ｃｕｒｒｅｎｔ．ｒｉｇｈｔ　＝＝＝　ｎｕｌｌ）｛
　　　　　　　　　　　　　　　　　　　　　　　　ｃｕｒｒｅｎｔ．ｒｉｇｈｔ　＝　ｎｏｄｅ；
　　　　　　　　　　　　　　　　　　　　　　　　ｂｒｅａｋ；
　　　　　　　　　　　　　　　　　　　　｝　ｅｌｓｅ　｛
　　　　　　　　　　　　　　　　　　　　　　　　ｃｕｒｒｅｎｔ　＝　ｃｕｒｒｅｎｔ．ｒｉｇｈｔ；
　　　　　　　　　　　　　　　　　　　　｝　　　　　　　
　　　　　　　　　　　　　　　　／／ｉｆ　ｔｈｅ　ｎｅｗ　ｖａｌｕｅ　ｉｓ　ｅｑｕａｌ　ｔｏ　ｔｈｅ　ｃｕｒｒｅｎｔ　ｏｎｅ，　ｊｕｓｔ　ｉｇｎｏｒｅ
　　　　　　　　　　　　　　　　｝　ｅｌｓｅ　｛
　　　　　　　　　　　　　　　　　　　　ｂｒｅａｋ；
　　　　　　　　　　　　　　　　｝
　　　　　　　　　　　　｝
　　　　　　　　｝
　　　　｝，
　　　　／／ｍｏｒｅ　ｃｏｄｅ
｝；

在二叉搜索树中添加值时，特殊情况是在没有根的情况。在这种情况下，只需将根设置为新值即可轻松完成工作。对于其他情况，基本算法与　ｃｏｎｔａｉｎｓ（）　中使用的基本算法完全相同：新值小于当前节点向左，如果值更大则向右。主要区别在于，当你无法继续前进时，这就是新值的位置。所以如果你需要向左移动但没有左侧节点，则新值将成为左侧节点（与右侧节点相同）。由于不存在重复项，因此如果找到具有相同值的节点，则操作将停止。

在继续讨论　ｓｉｚｅ（）　方法之前，我想深入讨论树遍历。为了计算二叉搜索树的大小，必须要访问树中的每个节点。二叉搜索树通常会有不同类型的遍历方法，最常用的是有序遍历。通过处理左子树，然后是节点本身，然后是右子树，在每个节点上执行有序遍历。由于二叉搜索树以这种方式排序，从左到右，结果是节点以正确的排序顺序处理。对于　ｓｉｚｅ（）　方法，节点遍历的顺序实际上并不重要，但它对　ｔｏＡｒｒａｙ（）　方法很重要。由于两种方法都需要执行遍历，我决定添加一个可以通用的　ｔｒａｖｅｒｓｅ（）　方法：

ＢｉｎａｒｙＳｅａｒｃｈＴｒｅｅ．ｐｒｏｔｏｔｙｐｅ　＝　｛
　　　　／／ｍｏｒｅ　ｃｏｄｅ
　　　　ｔｒａｖｅｒｓｅ：　ｆｕｎｃｔｉｏｎ（ｐｒｏｃｅｓｓ）｛
　　　　　　　　／／ｈｅｌｐｅｒ　ｆｕｎｃｔｉｏｎ
　　　　　　　　ｆｕｎｃｔｉｏｎ　ｉｎＯｒｄｅｒ（ｎｏｄｅ）｛
　　　　　　　　　　　　ｉｆ　（ｎｏｄｅ）｛
　　　　　　　　　　　　　　　　／／ｔｒａｖｅｒｓｅ　ｔｈｅ　ｌｅｆｔ　ｓｕｂｔｒｅｅ
　　　　　　　　　　　　　　　　ｉｆ　（ｎｏｄｅ．ｌｅｆｔ　！＝＝　ｎｕｌｌ）｛
　　　　　　　　　　　　　　　　　　　　ｉｎＯｒｄｅｒ（ｎｏｄｅ．ｌｅｆｔ）；
　　　　　　　　　　　　　　　　｝　　　　　　　　　　　　
　　　　　　　　　　　　　　　　／／ｃａｌｌ　ｔｈｅ　ｐｒｏｃｅｓｓ　ｍｅｔｈｏｄ　ｏｎ　ｔｈｉｓ　ｎｏｄｅ
　　　　　　　　　　　　　　　　ｐｒｏｃｅｓｓ．ｃａｌｌ（ｔｈｉｓ，　ｎｏｄｅ）；
　　　　　　　　　　　　　　　　／／ｔｒａｖｅｒｓｅ　ｔｈｅ　ｒｉｇｈｔ　ｓｕｂｔｒｅｅ
　　　　　　　　　　　　　　　　ｉｆ　（ｎｏｄｅ．ｒｉｇｈｔ　！＝＝　ｎｕｌｌ）｛
　　　　　　　　　　　　　　　　　　　　ｉｎＯｒｄｅｒ（ｎｏｄｅ．ｒｉｇｈｔ）；
　　　　　　　　　　　　　　　　｝
　　　　　　　　　　　　｝
　　　　　　　　｝
　　　　　　　　／／ｓｔａｒｔ　ｗｉｔｈ　ｔｈｅ　ｒｏｏｔ
　　　　　　　　ｉｎＯｒｄｅｒ（ｔｈｉｓ．＿ｒｏｏｔ）；
　　　　｝，
　　　　／／ｍｏｒｅ　ｃｏｄｅ
｝；

此方法接受一个参数　ｐｒｏｃｅｓｓ，这是一个应该在树中的每个节点上运行的函数。该方法定义了一个名为　ｉｎＯｒｄｅｒ（）　的辅助函数用于递归遍历树。注意，如果当前节点存在，则递归仅左右移动（以避免多次处理　ｎｕｌｌ　）。然后　ｔｒａｖｅｒｓｅ（）　方法从根节点开始按顺序遍历，ｐｒｏｃｅｓｓ（）　函数处理每个节点。然后可以使用此方法实现ｓｉｚｅ（）、ｔｏＡｒｒａｙ（）、ｔｏＳｔｒｉｎｇ（）：

ＢｉｎａｒｙＳｅａｒｃｈＴｒｅｅ．ｐｒｏｔｏｔｙｐｅ　＝　｛
　　　　／／ｍｏｒｅ　ｃｏｄｅ
　　　　ｓｉｚｅ：　ｆｕｎｃｔｉｏｎ（）｛
　　　　　　　　ｖａｒ　ｌｅｎｇｔｈ　＝　０；
　　　　　　　　ｔｈｉｓ．ｔｒａｖｅｒｓｅ（ｆｕｎｃｔｉｏｎ（ｎｏｄｅ）｛
　　　　　　　　　　　　ｌｅｎｇｔｈ＋＋；
　　　　　　　　｝）；
　　　　　　　　ｒｅｔｕｒｎ　ｌｅｎｇｔｈ；
　　　　｝，
　　　　ｔｏＡｒｒａｙ：　ｆｕｎｃｔｉｏｎ（）｛
　　　　　　　　ｖａｒ　ｒｅｓｕｌｔ　＝　［］；
　　　　　　　　ｔｈｉｓ．ｔｒａｖｅｒｓｅ（ｆｕｎｃｔｉｏｎ（ｎｏｄｅ）｛
　　　　　　　　　　　　ｒｅｓｕｌｔ．ｐｕｓｈ（ｎｏｄｅ．ｖａｌｕｅ）；
　　　　　　　　｝）；
　　　　　　　　ｒｅｔｕｒｎ　ｒｅｓｕｌｔ；
　　　　｝，
　　　　ｔｏＳｔｒｉｎｇ：　ｆｕｎｃｔｉｏｎ（）｛
　　　　　　　　ｒｅｔｕｒｎ　ｔｈｉｓ．ｔｏＡｒｒａｙ（）．ｔｏＳｔｒｉｎｇ（）；
　　　　｝，
　　　　／／ｍｏｒｅ　ｃｏｄｅ
｝；

ｓｉｚｅ（）　和　ｔｏＡｒｒａｙ（）　都调用　ｔｒａｖｅｒｓｅ（）　方法并传入一个函数来在每个节点上运行。在使用　ｓｉｚｅ（）的情况下，函数只是递增长度变量，而　ｔｏＡｒｒａｙ（）　使用函数将节点的值添加到数组中。　ｔｏＳｔｒｉｎｇ（）方法在调用　ｔｏＡｒｒａｙ（）　之前把返回的数组转换为字符串，并返回　　。

删除节点时，你需要确定它是否为根节点。根节点的处理方式与其他节点类似，但明显的例外是根节点需要在结尾处设置为不同的值。为简单起见，这将被视为　ＪａｖａＳｃｒｉｐｔ　代码中的一个特例。

删除节点的第一步是确定节点是否存在：

ＢｉｎａｒｙＳｅａｒｃｈＴｒｅｅ．ｐｒｏｔｏｔｙｐｅ　＝　｛
　　　　／／ｍｏｒｅ　ｃｏｄｅ　ｈｅｒｅ
　　　　ｒｅｍｏｖｅ：　ｆｕｎｃｔｉｏｎ（ｖａｌｕｅ）｛
　　　　　　　　ｖａｒ　ｆｏｕｎｄ　　　　　　　＝　ｆａｌｓｅ，
　　　　　　　　　　　　ｐａｒｅｎｔ　　　　　　＝　ｎｕｌｌ，
　　　　　　　　　　　　ｃｕｒｒｅｎｔ　　　　　＝　ｔｈｉｓ．＿ｒｏｏｔ，
　　　　　　　　　　　　ｃｈｉｌｄＣｏｕｎｔ，
　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔ，
　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔＰａｒｅｎｔ；
　　　　　　　　／／ｍａｋｅ　ｓｕｒｅ　ｔｈｅｒｅ＇ｓ　ａ　ｎｏｄｅ　ｔｏ　ｓｅａｒｃｈ
　　　　　　　　ｗｈｉｌｅ（！ｆｏｕｎｄ　＆＆　ｃｕｒｒｅｎｔ）｛
　　　　　　　　　　　　／／ｉｆ　ｔｈｅ　ｖａｌｕｅ　ｉｓ　ｌｅｓｓ　ｔｈａｎ　ｔｈｅ　ｃｕｒｒｅｎｔ　ｎｏｄｅ＇ｓ，　ｇｏ　ｌｅｆｔ
　　　　　　　　　　　　ｉｆ　（ｖａｌｕｅ　＜　ｃｕｒｒｅｎｔ．ｖａｌｕｅ）｛
　　　　　　　　　　　　　　　　ｐａｒｅｎｔ　＝　ｃｕｒｒｅｎｔ；
　　　　　　　　　　　　　　　　ｃｕｒｒｅｎｔ　＝　ｃｕｒｒｅｎｔ．ｌｅｆｔ；
　　　　　　　　　　　　／／ｉｆ　ｔｈｅ　ｖａｌｕｅ　ｉｓ　ｇｒｅａｔｅｒ　ｔｈａｎ　ｔｈｅ　ｃｕｒｒｅｎｔ　ｎｏｄｅ＇ｓ，　ｇｏ　ｒｉｇｈｔ
　　　　　　　　　　　　｝　ｅｌｓｅ　ｉｆ　（ｖａｌｕｅ　＞　ｃｕｒｒｅｎｔ．ｖａｌｕｅ）｛
　　　　　　　　　　　　　　　　ｐａｒｅｎｔ　＝　ｃｕｒｒｅｎｔ；
　　　　　　　　　　　　　　　　ｃｕｒｒｅｎｔ　＝　ｃｕｒｒｅｎｔ．ｒｉｇｈｔ；
　　　　　　　　　　　　／／ｖａｌｕｅｓ　ａｒｅ　ｅｑｕａｌ，　ｆｏｕｎｄ　ｉｔ！
　　　　　　　　　　　　｝　ｅｌｓｅ　｛
　　　　　　　　　　　　　　　　ｆｏｕｎｄ　＝　ｔｒｕｅ；
　　　　　　　　　　　　｝
　　　　　　　　｝
　　　　　　　　／／ｏｎｌｙ　ｐｒｏｃｅｅｄ　ｉｆ　ｔｈｅ　ｎｏｄｅ　ｗａｓ　ｆｏｕｎｄ
　　　　　　　　ｉｆ　（ｆｏｕｎｄ）｛
　　　　　　　　　　　　／／ｃｏｎｔｉｎｕｅ
　　　　　　　　｝
　　　　｝，
　　　　／／ｍｏｒｅ　ｃｏｄｅ　ｈｅｒｅ
｝；

ｒｅｍｏｖｅ（）方法的第一部分是用二叉搜索定位要被删除的节点，如果值小于当前节点的话则向左移动，如果值大于当前节点则向右移动。当遍历时还会跟踪　ｐａｒｅｎｔ　节点，因为你最终需要从其父节点中删除该节点。当　ｆｏｕｎｄ　等于　ｔｒｕｅ　时，ｃｕｒｒｅｎｔ　的值是要删除的节点。

删除节点时需要注意三个条件：

１、叶子节点

２、只有一个孩子的节点

３、有两个孩子的节点

从二叉搜索树中删除除了叶节点之外的内容意味着必须移动值来对树正确的排序。前两个实现起来相对简单，只删除了一个叶子节点，删除了一个带有一个子节点的节点并用其子节点替换。最后一种情况有点复杂，以便稍后访问。

在了解如何删除节点之前，你需要知道节点上究竟存在多少个子节点。一旦知道了，你必须确定节点是否为根节点，留下一个相当简单的决策树：

ＢｉｎａｒｙＳｅａｒｃｈＴｒｅｅ．ｐｒｏｔｏｔｙｐｅ　＝　｛
　　　　／／ｍｏｒｅ　ｃｏｄｅ　ｈｅｒｅ
　　　　ｒｅｍｏｖｅ：　ｆｕｎｃｔｉｏｎ（ｖａｌｕｅ）｛
　　　　　　　　ｖａｒ　ｆｏｕｎｄ　　　　　　　＝　ｆａｌｓｅ，
　　　　　　　　　　　　ｐａｒｅｎｔ　　　　　　＝　ｎｕｌｌ，
　　　　　　　　　　　　ｃｕｒｒｅｎｔ　　　　　＝　ｔｈｉｓ．＿ｒｏｏｔ，
　　　　　　　　　　　　ｃｈｉｌｄＣｏｕｎｔ，
　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔ，
　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔＰａｒｅｎｔ；
　　　　　　　　／／ｆｉｎｄ　ｔｈｅ　ｎｏｄｅ　（ｒｅｍｏｖｅｄ　ｆｏｒ　ｓｐａｃｅ）
　　　　　　　　／／ｏｎｌｙ　ｐｒｏｃｅｅｄ　ｉｆ　ｔｈｅ　ｎｏｄｅ　ｗａｓ　ｆｏｕｎｄ
　　　　　　　　ｉｆ　（ｆｏｕｎｄ）｛
　　　　　　　　　　　　／／ｆｉｇｕｒｅ　ｏｕｔ　ｈｏｗ　ｍａｎｙ　ｃｈｉｌｄｒｅｎ
　　　　　　　　　　　　ｃｈｉｌｄＣｏｕｎｔ　＝　（ｃｕｒｒｅｎｔ．ｌｅｆｔ　！＝＝　ｎｕｌｌ　？　１　：　０）　＋　
　　　　　　　　　　　　　　　　　　　　　　　　　（ｃｕｒｒｅｎｔ．ｒｉｇｈｔ　！＝＝　ｎｕｌｌ　？　１　：　０）；
　　　　　　　　　　　　／／ｓｐｅｃｉａｌ　ｃａｓｅ：　ｔｈｅ　ｖａｌｕｅ　ｉｓ　ａｔ　ｔｈｅ　ｒｏｏｔ
　　　　　　　　　　　　ｉｆ　（ｃｕｒｒｅｎｔ　＝＝＝　ｔｈｉｓ．＿ｒｏｏｔ）｛
　　　　　　　　　　　　　　　　ｓｗｉｔｃｈ（ｃｈｉｌｄＣｏｕｎｔ）｛
　　　　　　　　　　　　　　　　　　　　／／ｎｏ　ｃｈｉｌｄｒｅｎ，　ｊｕｓｔ　ｅｒａｓｅ　ｔｈｅ　ｒｏｏｔ
　　　　　　　　　　　　　　　　　　　　ｃａｓｅ　０：
　　　　　　　　　　　　　　　　　　　　　　　　ｔｈｉｓ．＿ｒｏｏｔ　＝　ｎｕｌｌ；
　　　　　　　　　　　　　　　　　　　　　　　　ｂｒｅａｋ；
　　　　　　　　　　　　　　　　　　　　／／ｏｎｅ　ｃｈｉｌｄ，　ｕｓｅ　ｏｎｅ　ａｓ　ｔｈｅ　ｒｏｏｔ
　　　　　　　　　　　　　　　　　　　　ｃａｓｅ　１：
　　　　　　　　　　　　　　　　　　　　　　　　ｔｈｉｓ．＿ｒｏｏｔ　＝　（ｃｕｒｒｅｎｔ．ｒｉｇｈｔ　＝＝＝　ｎｕｌｌ　？　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｃｕｒｒｅｎｔ．ｌｅｆｔ　：　ｃｕｒｒｅｎｔ．ｒｉｇｈｔ）；
　　　　　　　　　　　　　　　　　　　　　　　　ｂｒｅａｋ；
　　　　　　　　　　　　　　　　　　　　／／ｔｗｏ　ｃｈｉｌｄｒｅｎ，　ｌｉｔｔｌｅ　ｗｏｒｋ　ｔｏ　ｄｏ
　　　　　　　　　　　　　　　　　　　　ｃａｓｅ　２：
　　　　　　　　　　　　　　　　　　　　　　　　／／ＴＯＤＯ
　　　　　　　　　　　　　　　　　　　　／／ｎｏ　ｄｅｆａｕｌｔ
　　　　　　　　　　　　　　　　｝　　　　　　　　
　　　　　　　　　　　　／／ｎｏｎ－ｒｏｏｔ　ｖａｌｕｅｓ
　　　　　　　　　　　　｝　ｅｌｓｅ　｛
　　　　　　　　　　　　　　　　ｓｗｉｔｃｈ　（ｃｈｉｌｄＣｏｕｎｔ）｛
　　　　　　　　　　　　　　　　　　　　／／ｎｏ　ｃｈｉｌｄｒｅｎ，　ｊｕｓｔ　ｒｅｍｏｖｅ　ｉｔ　ｆｒｏｍ　ｔｈｅ　ｐａｒｅｎｔ
　　　　　　　　　　　　　　　　　　　　ｃａｓｅ　０：
　　　　　　　　　　　　　　　　　　　　　　　　／／ｉｆ　ｔｈｅ　ｃｕｒｒｅｎｔ　ｖａｌｕｅ　ｉｓ　ｌｅｓｓ　ｔｈａｎ　ｉｔｓ　
　　　　　　　　　　　　　　　　　　　　　　　　／／ｐａｒｅｎｔ＇ｓ，　ｎｕｌｌ　ｏｕｔ　ｔｈｅ　ｌｅｆｔ　ｐｏｉｎｔｅｒ
　　　　　　　　　　　　　　　　　　　　　　　　ｉｆ　（ｃｕｒｒｅｎｔ．ｖａｌｕｅ　＜　ｐａｒｅｎｔ．ｖａｌｕｅ）｛
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｐａｒｅｎｔ．ｌｅｆｔ　＝　ｎｕｌｌ；
　　　　　　　　　　　　　　　　　　　　　　　　／／ｉｆ　ｔｈｅ　ｃｕｒｒｅｎｔ　ｖａｌｕｅ　ｉｓ　ｇｒｅａｔｅｒ　ｔｈａｎ　ｉｔｓ
　　　　　　　　　　　　　　　　　　　　　　　　／／ｐａｒｅｎｔ＇ｓ，　ｎｕｌｌ　ｏｕｔ　ｔｈｅ　ｒｉｇｈｔ　ｐｏｉｎｔｅｒ
　　　　　　　　　　　　　　　　　　　　　　　　｝　ｅｌｓｅ　｛
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｐａｒｅｎｔ．ｒｉｇｈｔ　＝　ｎｕｌｌ；
　　　　　　　　　　　　　　　　　　　　　　　　｝
　　　　　　　　　　　　　　　　　　　　　　　　ｂｒｅａｋ；
　　　　　　　　　　　　　　　　　　　　／／ｏｎｅ　ｃｈｉｌｄ，　ｊｕｓｔ　ｒｅａｓｓｉｇｎ　ｔｏ　ｐａｒｅｎｔ
　　　　　　　　　　　　　　　　　　　　ｃａｓｅ　１：
　　　　　　　　　　　　　　　　　　　　　　　　／／ｉｆ　ｔｈｅ　ｃｕｒｒｅｎｔ　ｖａｌｕｅ　ｉｓ　ｌｅｓｓ　ｔｈａｎ　ｉｔｓ　
　　　　　　　　　　　　　　　　　　　　　　　　／／ｐａｒｅｎｔ＇ｓ，　ｒｅｓｅｔ　ｔｈｅ　ｌｅｆｔ　ｐｏｉｎｔｅｒ
　　　　　　　　　　　　　　　　　　　　　　　　ｉｆ　（ｃｕｒｒｅｎｔ．ｖａｌｕｅ　＜　ｐａｒｅｎｔ．ｖａｌｕｅ）｛
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｐａｒｅｎｔ．ｌｅｆｔ　＝　（ｃｕｒｒｅｎｔ．ｌｅｆｔ　＝＝＝　ｎｕｌｌ　？　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｃｕｒｒｅｎｔ．ｒｉｇｈｔ　：　ｃｕｒｒｅｎｔ．ｌｅｆｔ）；
　　　　　　　　　　　　　　　　　　　　　　　　／／ｉｆ　ｔｈｅ　ｃｕｒｒｅｎｔ　ｖａｌｕｅ　ｉｓ　ｇｒｅａｔｅｒ　ｔｈａｎ　ｉｔｓ　
　　　　　　　　　　　　　　　　　　　　　　　　／／ｐａｒｅｎｔ＇ｓ，　ｒｅｓｅｔ　ｔｈｅ　ｒｉｇｈｔ　ｐｏｉｎｔｅｒ
　　　　　　　　　　　　　　　　　　　　　　　　｝　ｅｌｓｅ　｛
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｐａｒｅｎｔ．ｒｉｇｈｔ　＝　（ｃｕｒｒｅｎｔ．ｌｅｆｔ　＝＝＝　ｎｕｌｌ　？　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｃｕｒｒｅｎｔ．ｒｉｇｈｔ　：　ｃｕｒｒｅｎｔ．ｌｅｆｔ）；
　　　　　　　　　　　　　　　　　　　　　　　　｝
　　　　　　　　　　　　　　　　　　　　　　　　ｂｒｅａｋ；　　　　
　　　　　　　　　　　　　　　　　　　　／／ｔｗｏ　ｃｈｉｌｄｒｅｎ，　ａ　ｂｉｔ　ｍｏｒｅ　ｃｏｍｐｌｉｃａｔｅｄ
　　　　　　　　　　　　　　　　　　　　ｃａｓｅ　２：
　　　　　　　　　　　　　　　　　　　　　　　　／／ＴＯＤＯ　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　／／ｎｏ　ｄｅｆａｕｌｔ
　　　　　　　　　　　　　　　　｝
　　　　　　　　　　　　｝
　　　　　　　　｝
　　　　｝，
　　　　／／ｍｏｒｅ　ｃｏｄｅ　ｈｅｒｅ
｝；

处理根节点时，这是一个覆盖它的简单过程。对于非根节点，必须根据要删除的节点的值设置　ｐａｒｅｎｔ　上的相应指针：如果删除的值小于父节点，则　ｌｅｆｔ　指针必须重置为　ｎｕｌｌ　（对于没有子节点的节点）或删除节点的　ｌｅｆｔ　指针；如果删除的值大于父级，则必须将　ｒｉｇｈｔ　指针重置为　ｎｕｌｌ　或删除的节点的　ｒｉｇｈｔ指针。

如前所述，删除具有两个子节点的节点是最复杂的操作。考虑二元搜索树的以下表示。

根为　８，左子为　３，如果　３　被删除会发生什么？有两种可能性：１（３　左边的孩子，称为有序前身）或４（右子树的最左边的孩子，称为有序继承者）都可以取代　３。

这两个选项中的任何一个都是合适的。要查找有序前驱，即删除值之前的值，请检查要删除的节点的左子树，并选择最右侧的子节点；找到有序后继，在删除值后立即出现的值，反转进程并检查最左侧的右子树。其中每个都需要另一次遍历树来完成操作：

ＢｉｎａｒｙＳｅａｒｃｈＴｒｅｅ．ｐｒｏｔｏｔｙｐｅ　＝　｛
　　　　／／ｍｏｒｅ　ｃｏｄｅ　ｈｅｒｅ
　　　　ｒｅｍｏｖｅ：　ｆｕｎｃｔｉｏｎ（ｖａｌｕｅ）｛
　　　　　　　　ｖａｒ　ｆｏｕｎｄ　　　　　　　＝　ｆａｌｓｅ，
　　　　　　　　　　　　ｐａｒｅｎｔ　　　　　　＝　ｎｕｌｌ，
　　　　　　　　　　　　ｃｕｒｒｅｎｔ　　　　　＝　ｔｈｉｓ．＿ｒｏｏｔ，
　　　　　　　　　　　　ｃｈｉｌｄＣｏｕｎｔ，
　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔ，
　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔＰａｒｅｎｔ；
　　　　　　　　／／ｆｉｎｄ　ｔｈｅ　ｎｏｄｅ　（ｒｅｍｏｖｅｄ　ｆｏｒ　ｓｐａｃｅ）
　　　　　　　　／／ｏｎｌｙ　ｐｒｏｃｅｅｄ　ｉｆ　ｔｈｅ　ｎｏｄｅ　ｗａｓ　ｆｏｕｎｄ
　　　　　　　　ｉｆ　（ｆｏｕｎｄ）｛
　　　　　　　　　　　　／／ｆｉｇｕｒｅ　ｏｕｔ　ｈｏｗ　ｍａｎｙ　ｃｈｉｌｄｒｅｎ
　　　　　　　　　　　　ｃｈｉｌｄＣｏｕｎｔ　＝　（ｃｕｒｒｅｎｔ．ｌｅｆｔ　！＝＝　ｎｕｌｌ　？　１　：　０）　＋　
　　　　　　　　　　　　　　　　　　　　　　　　　（ｃｕｒｒｅｎｔ．ｒｉｇｈｔ　！＝＝　ｎｕｌｌ　？　１　：　０）；
　　　　　　　　　　　　／／ｓｐｅｃｉａｌ　ｃａｓｅ：　ｔｈｅ　ｖａｌｕｅ　ｉｓ　ａｔ　ｔｈｅ　ｒｏｏｔ
　　　　　　　　　　　　ｉｆ　（ｃｕｒｒｅｎｔ　＝＝＝　ｔｈｉｓ．＿ｒｏｏｔ）｛
　　　　　　　　　　　　　　　　ｓｗｉｔｃｈ（ｃｈｉｌｄＣｏｕｎｔ）｛
　　　　　　　　　　　　　　　　　　　　／／ｏｔｈｅｒ　ｃａｓｅｓ　ｒｅｍｏｖｅｄ　ｔｏ　ｓａｖｅ　ｓｐａｃｅ
　　　　　　　　　　　　　　　　　　　　／／ｔｗｏ　ｃｈｉｌｄｒｅｎ，　ｌｉｔｔｌｅ　ｗｏｒｋ　ｔｏ　ｄｏ
　　　　　　　　　　　　　　　　　　　　ｃａｓｅ　２：
　　　　　　　　　　　　　　　　　　　　　　　　／／ｎｅｗ　ｒｏｏｔ　ｗｉｌｌ　ｂｅ　ｔｈｅ　ｏｌｄ　ｒｏｏｔ＇ｓ　ｌｅｆｔ　ｃｈｉｌｄ
　　　　　　　　　　　　　　　　　　　　　　　　／／．．．ｍａｙｂｅ
　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔ　＝　ｔｈｉｓ．＿ｒｏｏｔ．ｌｅｆｔ；
　　　　　　　　　　　　　　　　　　　　　　　　／／ｆｉｎｄ　ｔｈｅ　ｒｉｇｈｔ－ｍｏｓｔ　ｌｅａｆ　ｎｏｄｅ　ｔｏ　ｂｅ　
　　　　　　　　　　　　　　　　　　　　　　　　／／ｔｈｅ　ｒｅａｌ　ｎｅｗ　ｒｏｏｔ
　　　　　　　　　　　　　　　　　　　　　　　　ｗｈｉｌｅ　（ｒｅｐｌａｃｅｍｅｎｔ．ｒｉｇｈｔ　！＝＝　ｎｕｌｌ）｛
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔＰａｒｅｎｔ　＝　ｒｅｐｌａｃｅｍｅｎｔ；
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔ　＝　ｒｅｐｌａｃｅｍｅｎｔ．ｒｉｇｈｔ；
　　　　　　　　　　　　　　　　　　　　　　　　｝
　　　　　　　　　　　　　　　　　　　　　　　　／／ｉｔ＇ｓ　ｎｏｔ　ｔｈｅ　ｆｉｒｓｔ　ｎｏｄｅ　ｏｎ　ｔｈｅ　ｌｅｆｔ
　　　　　　　　　　　　　　　　　　　　　　　　ｉｆ　（ｒｅｐｌａｃｅｍｅｎｔＰａｒｅｎｔ　！＝＝　ｎｕｌｌ）｛
　　　　　　　　　　　　　　　　　　　　　　　　　　　　／／ｒｅｍｏｖｅ　ｔｈｅ　ｎｅｗ　ｒｏｏｔ　ｆｒｏｍ　ｉｔ＇ｓ　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　／／ｐｒｅｖｉｏｕｓ　ｐｏｓｉｔｉｏｎ
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔＰａｒｅｎｔ．ｒｉｇｈｔ　＝　ｒｅｐｌａｃｅｍｅｎｔ．ｌｅｆｔ；
　　　　　　　　　　　　　　　　　　　　　　　　　　　　／／ｇｉｖｅ　ｔｈｅ　ｎｅｗ　ｒｏｏｔ　ａｌｌ　ｏｆ　ｔｈｅ　ｏｌｄ　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　／／ｒｏｏｔ＇ｓ　ｃｈｉｌｄｒｅｎ
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔ．ｒｉｇｈｔ　＝　ｔｈｉｓ．＿ｒｏｏｔ．ｒｉｇｈｔ；
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔ．ｌｅｆｔ　＝　ｔｈｉｓ．＿ｒｏｏｔ．ｌｅｆｔ；
　　　　　　　　　　　　　　　　　　　　　　　　｝　ｅｌｓｅ　｛
　　　　　　　　　　　　　　　　　　　　　　　　　　　　／／ｊｕｓｔ　ａｓｓｉｇｎ　ｔｈｅ　ｃｈｉｌｄｒｅｎ
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔ．ｒｉｇｈｔ　＝　ｔｈｉｓ．＿ｒｏｏｔ．ｒｉｇｈｔ；
　　　　　　　　　　　　　　　　　　　　　　　　｝
　　　　　　　　　　　　　　　　　　　　　　　　／／ｏｆｆｉｃｉａｌｌｙ　ａｓｓｉｇｎ　ｎｅｗ　ｒｏｏｔ
　　　　　　　　　　　　　　　　　　　　　　　　ｔｈｉｓ．＿ｒｏｏｔ　＝　ｒｅｐｌａｃｅｍｅｎｔ；
　　　　　　　　　　　　　　　　　　　　／／ｎｏ　ｄｅｆａｕｌｔ
　　　　　　　　　　　　　　　　｝　　　　　　　　
　　　　　　　　　　　　／／ｎｏｎ－ｒｏｏｔ　ｖａｌｕｅｓ
　　　　　　　　　　　　｝　ｅｌｓｅ　｛
　　　　　　　　　　　　　　　　ｓｗｉｔｃｈ　（ｃｈｉｌｄＣｏｕｎｔ）｛
　　　　　　　　　　　　　　　　　　　　／／ｏｔｈｅｒ　ｃａｓｅｓ　ｒｅｍｏｖｅｄ　ｔｏ　ｓａｖｅ　ｓｐａｃｅ　
　　　　　　　　　　　　　　　　　　　　／／ｔｗｏ　ｃｈｉｌｄｒｅｎ，　ａ　ｂｉｔ　ｍｏｒｅ　ｃｏｍｐｌｉｃａｔｅｄ
　　　　　　　　　　　　　　　　　　　　ｃａｓｅ　２：
　　　　　　　　　　　　　　　　　　　　　　　　／／ｒｅｓｅｔ　ｐｏｉｎｔｅｒｓ　ｆｏｒ　ｎｅｗ　ｔｒａｖｅｒｓａｌ
　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔ　＝　ｃｕｒｒｅｎｔ．ｌｅｆｔ；
　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔＰａｒｅｎｔ　＝　ｃｕｒｒｅｎｔ；
　　　　　　　　　　　　　　　　　　　　　　　　／／ｆｉｎｄ　ｔｈｅ　ｒｉｇｈｔ－ｍｏｓｔ　ｎｏｄｅ
　　　　　　　　　　　　　　　　　　　　　　　　ｗｈｉｌｅ（ｒｅｐｌａｃｅｍｅｎｔ．ｒｉｇｈｔ　！＝＝　ｎｕｌｌ）｛
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔＰａｒｅｎｔ　＝　ｒｅｐｌａｃｅｍｅｎｔ；
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔ　＝　ｒｅｐｌａｃｅｍｅｎｔ．ｒｉｇｈｔ；
　　　　　　　　　　　　　　　　　　　　　　　　｝
　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔＰａｒｅｎｔ．ｒｉｇｈｔ　＝　ｒｅｐｌａｃｅｍｅｎｔ．ｌｅｆｔ；
　　　　　　　　　　　　　　　　　　　　　　　　／／ａｓｓｉｇｎ　ｃｈｉｌｄｒｅｎ　ｔｏ　ｔｈｅ　ｒｅｐｌａｃｅｍｅｎｔ
　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔ．ｒｉｇｈｔ　＝　ｃｕｒｒｅｎｔ．ｒｉｇｈｔ；
　　　　　　　　　　　　　　　　　　　　　　　　ｒｅｐｌａｃｅｍｅｎｔ．ｌｅｆｔ　＝　ｃｕｒｒｅｎｔ．ｌｅｆｔ；
　　　　　　　　　　　　　　　　　　　　　　　　／／ｐｌａｃｅ　ｔｈｅ　ｒｅｐｌａｃｅｍｅｎｔ　ｉｎ　ｔｈｅ　ｒｉｇｈｔ　ｓｐｏｔ
　　　　　　　　　　　　　　　　　　　　　　　　ｉｆ　（ｃｕｒｒｅｎｔ．ｖａｌｕｅ　＜　ｐａｒｅｎｔ．ｖａｌｕｅ）｛
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｐａｒｅｎｔ．ｌｅｆｔ　＝　ｒｅｐｌａｃｅｍｅｎｔ；
　　　　　　　　　　　　　　　　　　　　　　　　｝　ｅｌｓｅ　｛
　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｐａｒｅｎｔ．ｒｉｇｈｔ　＝　ｒｅｐｌａｃｅｍｅｎｔ；
　　　　　　　　　　　　　　　　　　　　　　　　｝　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　／／ｎｏ　ｄｅｆａｕｌｔ
　　　　　　　　　　　　　　　　｝
　　　　　　　　　　　　｝
　　　　　　　　｝
　　　　｝，
　　　　／／ｍｏｒｅ　ｃｏｄｅ　ｈｅｒｅ
｝；

具有两个子节点的根节点和非根节点的代码几乎相同。此实现始终通过查看左子树并查找最右侧子节点来查找有序前驱。遍历是使用　ｗｈｉｌｅ　循环中的　ｒｅｐｌａｃｅｍｅｎｔ　和　ｒｅｐｌａｃｅｍｅｎｔＰａｒｅｎｔ　变量完成的。

ｒｅｐｌａｃｅｍｅｎｔ中的节点最终成为替换　ｃｕｒｒｅｎｔ　的节点，因此通过将其父级的　ｒｉｇｈｔ　指针设置为替换的　ｌｅｆｔ　指针，将其从当前位置移除。

对于根节点，当　ｒｅｐｌａｃｅｍｅｎｔ　是根节点的直接子节点时，ｒｅｐｌａｃｅｍｅｎｔＰａｒｅｎｔ　将为　ｎｕｌｌ，因此　ｒｅｐｌａｃｅｍｅｎｔ　的　ｒｉｇｈｔ　指针只是设置为　ｒｏｏｔ　的　ｒｉｇｈｔ　指针。

最后一步是将替换节点分配到正确的位置。对于根节点，替换设置为新根；对于非根节点，替换被分配到原始　ｐａｒｅｎｔ　上的适当位置。

关于此实现的说明：始终用有序前驱替换节点可能导致不平衡树，其中大多数值会位于树的一侧。不平衡树意味着搜索效率较低，因此在实际场景中应该引起关注。在二叉搜索树实现中，要确定是用有序前驱还是有序后继以使树保持适当平衡（通常称为自平衡二叉搜索树）。

这个二叉搜索树实现的完整源代码可以在我的ＧｉｔＨｕｂ　中找到。对于替代实现，你还可以查看　Ｉｓａａｃ　Ｓｃｈｌｕｅｔｅｒ　的　ＧｉｔＨｕｂ　ｆｏｒｋ。

本文转载自：ｈｔｔｐｓ：／／ｓｅｇｍｅｎｔｆａｕｌｔ．ｃｏｍ／ａ／１１９０００００２００４４６５９

英文原文地址：ｈｔｔｐｓ：／／ｈｕｍａｎｗｈｏｃｏｄｅｓ．ｃｏｍ／ｂｌｏｇ／２００９／０６／０９／ｃｏｍｐｕｔｅｒ－ｓｃｉｅｎｃｅ－ｉｎ－ｊａｖａｓｃｒｉｐｔ－ｂｉｎａｒｙ－ｓｅａｒｃｈ－ｔｒｅｅ－ｐａｒｔ－１／

作者：Ｎｉｃｈｏｌａｓ　Ｃ．　Ｚａｋａｓ

推荐教程：《ＪａｖａＳｃｒｉｐｔ视频教程》