我有一棵数字树。每个节点可以有一个左子节点和一个右子节点。数字不能重复,但它们可以在树上的任何地方。我需要在树上搜索一个数字,然后打印它到树根的路径。在
我想不出一种方法让一个节点跟踪谁是它的父节点,这样我就可以把它们打印回根节点。我怎么能做到这一点?在
代码如下:
# The Tree class holds a value and left and right childs
class Tree:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
# recursive function that searches the tree for a node
# and alerts when the node is found
def searchNode(tree, node):
if tree == None:
return
else:
searchNode(tree.left,node)
searchNode(tree.right,node)
if tree.value == node:
print "Node " + str(node) + " found!"
# manually creating a tree with its subtrees
tree1 = Tree(1,Tree(40,Tree(33,left=Tree(204)),
Tree(21,left=Tree(12,right=Tree(2,left=Tree(32))))),
Tree(7,Tree(46),Tree(11,Tree(3),Tree(1000))))
# searching tree
searchNode(tree1, 46)
我相信你有自己的理由用树来进行O(n)查找而不是O(logn),也就是说,不使用二叉搜索树,所以我不会质疑这一点:)
要解决问题,可以向函数中添加第三个参数来维护路径。以下是一个非常简单和低效的解决方案。在
您将使用空路径调用函数:
searchNode(tree1, 46, [])
请注意,
path
中的值即使在找到元素之后也会继续变化,因为没有什么可以阻止函数进一步遍历树。通过防止这种情况,可以使代码更高效。如果您不想这样做,请在找到节点时将path
中的值复制到其他变量中,以便以后可以使用它。在相关问题 更多 >
编程相关推荐