我正在学习 Python 3 中的算法和数据结构类(class),我的讲师最近向我们介绍了二叉搜索树。但是,我无法理解删除算法。下面是我们学到的实现,但是当我最初编写自己的演绎版时,我没有包含“基本案例”但它仍然有效:
def remove(self, data):
if self.root:
self.root = self.remove_node(data, self.root)
def remove_node(self, data, node):
if node is None:
return node
if data < node.data:
node.leftChild = self.remove_node(data, node.leftChild)
elif data > node.data:
node.rightChild = self.remove_node(data, node.rightChild)
else:
if not node.rightChild and not node.leftChild:
print('removing leaf node')
del node
return None
if not node.leftChild:
print('removing node with single right child')
tempNode = node.rightChild
del node
return tempNode
elif not node.rightChild:
print('removing node with single left child')
tempNode = node.leftChild
del node
return tempNode
print('removing node with two children')
tempNode = self.get_predecessor(node.leftChild)
node.data = tempNode.data
node.leftChild = self.remove_node(tempNode.data, node.leftChild)
return node
现在,除了下面的声明之外,所有这些对我来说都是有意义的:
if node is None:
return node
当我们之前了解基本案例时,我们被告知它们本质上是我们算法的导出点。但是,我不明白给定代码中的情况如何。首先,我不明白一个节点怎么可能是空的,即使它是空的,我们为什么要返回一个空节点?据我所知,此检查在整个递归中没有任何作用,因为我们似乎没有像在任何其他递归函数中那样“向它递归”。非常感谢您的解释!
最佳答案
一般情况下,基本案例服务于一个或多个目的,这些包括;
- 防止函数无限递归
- 防止函数在极端情况下抛出错误
- 计算/返回一个值/结果给递归树中更高层的调用者
对于树删除,第一点并不是真正的问题(因为递归树将只有有限数量的节点 - 与您递归的树相同)。您将在这里关注第 2 点和第 3 点。
在你的函数中,你确实有一个基本情况——事实上,你有两个(感谢@user2357112)——
未找到值部分,由
指定if node is None: return node
和,
找到值的部分,由您在
else
语句中的代码指定,执行实际删除。
为了使行为与递归情况保持一致,未找到值的基本情况返回 None
。如您所见,第一个基本案例是一致的,执行上述通用基本案例的第二个功能,而第二个基本案例执行第三个功能。
关于python - 二叉搜索树删除中基本情况的目的,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48879229/