回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>这是在Python中为BST实现添加和删除函数的一种可能方法。它有点类似于我在C++中对BST的想法。正如删除代码一样,我想删除一个节点,因为在C++中缺少Python的引用,所以我不能这么做。除了<code>del currNode</code>(这不起作用)之外,删除节点的另一种好方法是什么。我还有一个问题要澄清我在Python中关于引用传递的想法,当使用<code>add</code>函数添加节点时,当递归调用add时,它仍然“附加”到根节点。但是,当删除节点时,它不会与根节点“分离”。为什么会这样</p>
<pre><code>class node(object):
def __init__(self, data = None):
self.data = data
self.left = None
self.right = None
class bst(object):
def __init__(self):
self.root = None
def add(self, value):
def _add(self, currNode, value):
if value < currNode.data:
if currNode.left == None:
currNode.left = node(value)
else:
_add(self, currNode.left, value)
elif value > currNode.data:
if currNode.right == None:
currNode.right = node(value)
else:
_add(self, currNode.right, value)
else:
print("Duplicate found")
if self.root == None:
self.root = node(value)
else:
_add(self, self.root, value)
def printBST(self):
def _printBST(self, currNode):
if currNode!= None:
_printBST(self, currNode.left)
print(currNode.data, end = " ")
_printBST(self, currNode.right)
if self.root != None:
_printBST(self,self.root)
def minBST(self,currNode):
def _minBST(self, currNode):
if currNode.left == None:
return currNode.data
else: return _minBST(self, currNode.left)
if currNode != None:
return _minBST(self, currNode)
else:
return -10000
def deleteValue(self, val):
def deleteNode(self, currNode, value):
if currNode == None:
return
elif value > currNode.data:
return deleteNode(self, currNode.right, value)
elif value < currNode.data:
return deleteNode(self, currNode.left, value)
else:
if currNode.left == None and currNode.right == None:
#del currNode
currNode.data = None
elif currNode.right == None:
currNode.data = None
#The address of currNode does not change
#as it happens in C++
#currNode = currNode.left
elif currNode.left == None:
currNode.data = None
#The address of currNode does not change
#currNode = currNode.right
else:
minV = self.minBST(currNode.right)
currNode.data = minV
return deleteNode(self, currNode.right, minV)
deleteNode(self, self.root, val)
if __name__ == '__main__':
b = bst()
b.add(50)
b.add(60)
b.add(40)
b.add(30)
b.add(45)
b.add(55)
b.add(100)
b.printBST()
b.deleteValue(100)
print("")
b.printBST()
</code></pre>