在Python中迭代删除二叉搜索树中的值

Question

我目前正在学习数据结构和算法以及 BST 的课程。我已经让代码可以工作并理解其中的大部分内容，但我有一个关于删除功能的问题。这就是我的代码的样子：class BST:    def __init__(self, value):        self.value = value        self.left = None        self.right = None    def insert(self, value):        currentNode = self        while True:            if value < currentNode.value:                if currentNode.left is None:                    currentNode.left = BST(value)                    break                else:                    currentNode = currentNode.left            else:                if currentNode.right is None:                    currentNode.right = BST(value)                    break                else:                    currentNode = currentNode.right        return self    def contains(self, value):        currentNode = self        while currentNode is not None:            if value < currentNode.value:                currentNode = currentNode.left            elif value > currentNode.value:                currentNode = currentNode.right            else:                return True        return False    def remove(self, value, parentNode = None):        currentNode = self        while currentNode is not None:            if value < currentNode.value:                parentNode = currentNode                currentNode = currentNode.left              elif value > currentNode.value:                parentNode = currentNode                currentNode = currentNode.right            #Found the node据我了解，对于删除功能：循环while将迭代每个节点并运行，直到没有更多的节点第一个if和elif用于查找您要删除的节点。适用else于实际删除，有 3 个不同的选项：要么currentNode有两个子节点，要么将其替换为右侧节点的最左侧值，然后从右侧节点中删除该最左侧值。另一种情况是parentNode没有父节点，这将是根节点的情况。currentNode最后一种情况是，当您只有一个子节点时，您所要做的就是更改其左节点或右节点的值（取决于它有哪一个）。我不清楚的是条件背后的逻辑，以及当我们想要删除节点时它是如何工作的root。代码不是应该也运行第一个条件，即两个子节点的条件吗？我几乎可以肯定这不应该发生，并且该条件应该只适用于其特殊情况。我看了一遍又一遍的视频解释，但我就是无法掌握其中的窍门。

Answer 1

当我们想要删除根节点时。代码不是应该也运行第一个条件，即两个子节点的条件吗？

即使必须删除根节点，它实际上也会评估第一个条件。如果根节点同时具有左子节点和右子节点，则“选项 1”适用于它：第一个选项可以很好地处理具有两个子节点的任何节点，无论它是否是根节点。在此选项中不需要区分根节点或非根节点。

其他两个选项仅适用于没有两个子节点的节点。您似乎建议（也在代码注释中）只有选项 3 可以处理这种情况，但选项 2 也可以。选项2适用于当节点node没有两个子节点并且它是根节点时。如果根有 2 个孩子，则将被视为选项 1。