-1

我有一棵数字树。每个节点可以有一个左子节点和一个右子节点。数字不能重复，但它们可以在树上的任何地方。我需要在树上搜索一个数字，然后打印它到树根的路径。

我想不出办法让节点跟踪谁是它的父节点，所以我可以将它们打印回根目录。我怎么能做到这一点？

代码如下：

# 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)
4

1 回答 1

1

我相信您有理由使用树进行 O(n) 查找而不是 O(log n)，即不使用二叉搜索树，所以我不会质疑 :)

为了解决您的问题，您可以在函数中添加第三个参数来维护路径。以下是一个非常简单且低效的解决方案。

def searchNode(tree, node, path):
    if tree == None:
        return 
    else:
        #print tree.value
        path.append(tree.value) #add to path because we visited
        searchNode(tree.left,node, path)
        searchNode(tree.right,node, path)
        if tree.value == node:
            print "Node " + str(node) + " found!"
            print path
        else:
            path.pop()  #remove from path because we are going back

您将使用空路径调用您的函数：searchNode(tree1, 46, [])

请注意，path即使您找到了元素，in 的值也会继续变化，因为没有什么可以阻止您的函数进一步遍历树。通过防止这种情况，您可以使您的代码更高效。如果您不想这样做，请在path找到节点时将值复制到其他变量中，以便以后可以使用它。

于 2013-10-23T17:52:38.093 回答