问题理解 python 从 BST 删除节点的代码

Question

抱歉，如果这是一个非常基本的问题，但我不明白为什么将 root.left 或 root.right 分配给递归调用？

我已经提到了我不理解的台词。完整代码供参考

感谢您的帮助！

def findMin(bstNode):
    currentNode = bstNode
    while currentNode.leftChild is not None:
        currentNode = currentNode.leftChild
    return currentNode


def deleteNode(rootNode, nodeValue):
    if rootNode is None:
        return rootNode

    # these two lines (root.left/right = deleteNode)
    if nodeValue < rootNode.data:
        rootNode.leftChild = deleteNode(rootNode.leftChild, nodeValue)
    elif nodeValue > rootNode.data:
        rootNode.rightChild = deleteNode(rootNode.rightChild, nodeValue)

    else:
        if not rootNode.leftChild and not rootNode.rightChild:
            rootNode = None
    
        elif not rootNode.leftChild:
            rootNode = rootNode.rightChild
        elif not rootNode.rightChild:
            rootNode = rootNode.leftChild

        else:
            # this else statement
            temp = findMin(rootNode.rightChild)
            rootNode.data = temp.data
            rootNode.rightChild = deleteNode(rootNode.rightChild, temp.data)

    return rootNode

Answer 1

算法需要遍历树才能找到要删除的节点。所以如果我们还没有找到这个节点，那么我们需要在它的子节点上递归调用删除节点来继续寻找它。

Answer 2

这项作业是必要的。

拿这个：

rootNode.leftChild = deleteNode(rootNode.leftChild, nodeValue)

现在假设rootNode.leftChild恰好是需要删除的节点（因为它的值为nodeValue）。那么rootNode.leftChild肯定不能保持不变吧？它需要分配一个新的节点引用。递归调用无法进行此赋值，因为它不知道 rootNode 是什么。所以递归调用只会 return 将取代已删除节点的节点，这取决于 caller将其分配回应存储的位置。这就是这里发生的事情。

问题理解 python 从 BST 删除节点的代码

problem understanding python code to delete a node from BST

python-3.x

tree

binary-search-tree