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

Question

抱歉，如果这是一个非常基本的问题，但我不明白为什么根。左或根。是分配给递归调用的吗?

我提到了我不懂的行。完整的代码供参考。

谢谢你的帮助!

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

这个赋值是必须的。

看这个:

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

现在假设rootNode.leftChild恰好是需要删除的节点(因为它的值是nodeValue)。那么rootNode.leftChild肯定不能保持不变，对吗?它需要分配一个新的节点引用。递归调用不能进行这个赋值，因为它不知道rootNode是什么。因此，递归调用只会返回将取代被删除节点的节点，并且由调用者将其分配回应该存储的位置。这就是这里发生的事情。

Answer 2

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