data-structures - 从二维二叉搜索树中删除节点

Question

我想知道是否有人可以提供一些关于从二维二叉搜索树中删除节点的有用见解。

我知道有四种情况，我已经完成了第一种情况：

1. 删除没有子节点（叶子）的节点，很简单，只需将指向该节点的指针设置为 null。
2. 删除左节点有一个子节点且右节点为空的节点。
3. 删除右节点有一个子节点且左节点为空的节点。
4. 删除具有左右两个子节点的节点。

我不确定如何准确地执行 2,3 和 4。我尝试迭代地执行它，但是，这似乎不起作用。我假设这必须递归完成。有人可以详细说明如何做到这一点。这是在java中，不过没关系:)

Answer 1

在二维树中，所有值都存储在叶节点中。内部节点仅用作定位叶节点的路径。具体来说，内部节点定义了包含底层数据的半平面。我们只处理数据；我们不修改数据结构本身的结构元素。因此，只有上述情况 1 成立。其他的都无关紧要。