我正在使用python中的二叉树。我需要创建一种搜索树并返回可以插入新值的最佳节点的方法。但是我很难从这个递归函数中返回一个值。我是python的新手。
def return_key(self, val, node):
if(val < node.v):
if(node.l != None):
self.return_key(val, node.l)
else:
print node.v
return node
else:
if(node.r != None):
#print node.v
self.return_key(val, node.r)
else:
print node.v
return node
打印会node.v
打印节点值,但是当我打印返回的节点时:
print ((tree.return_key(6, tree.getRoot().v)))
它打印
没有
结果。
您需要返回递归调用的结果。您在这里忽略它:
if(node.l != None):
self.return_key(val, node.l)
和
if(node.r != None):
self.return_key(val, node.r)
递归调用与其他函数调用没有什么不同,如果有返回值,您仍然需要处理返回值。使用一条return
语句:
if(node.l != None):
return self.return_key(val, node.l)
# ...
if(node.r != None):
return self.return_key(val, node.r)
请注意,由于None
是单例值,因此您可以并且应该is not None
在此处使用该值来测试是否不存在:
if node.l is not None:
return self.return_key(val, node.l)
# ...
if node.r is not None:
return self.return_key(val, node.r)
我怀疑您将错误的论点传递给了电话,但从此开始;如果第二个参数是节点,则不要传入节点值:
print(tree.return_key(6, tree.getRoot())) # drop the .v
另外,如果所有node
类都具有相同的方法,则可以递归到该方法,而不是使用self.return_value()
;。在Tree
公正的做:
print tree.return_key(6)
其中Tree.return_key()
代表根节点:
def return_key(self, val):
root = tree.getRoot()
if root is not None:
return tree.getRoot().return_key(val)
并Node.return_key()
变成:
def return_key(self, val):
if val < self.v:
if self.l is not None:
return self.l.return_key(val)
elif val > self.v:
if self.r is not None:
return self.r.return_key(val)
# val == self.v or child node is None
return self
我val
也在这里更新了测试逻辑;如果val < self.v
(或val < node.v
在您的代码中)为假,则不要认为这val > self.v
是真的;val
可以相等。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句