파이썬에서 트리 노드의 부모 추적하기

Question

나는 수의 나무가있다. 각 노드는 왼쪽 및 오른쪽 자식 노드를 가질 수 있습니다. 숫자는 반복 될 수 없지만 트리의 아무 곳에 나있을 수 있습니다. 트리에서 숫자를 검색 한 다음 트리의 루트까지 경로를 인쇄해야합니다.

노드를 부모가 누구인지 추적하여 루트로 다시 인쇄 할 수있는 방법을 생각할 수 없습니다. 내가 어떻게 이걸 이룰 수 있니?

코드는 다음과 같이

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

Answer 1

난 당신이 (n)이 O를 위해 나무를 사용에 대한 이유가 확신 즉, 이진 검색 트리를 사용하지 않는, (로그 n) 대신 O의 업을 보면, 그래서 그 질문하지 않습니다 :)

문제를 해결하려면 경로를 유지하기 위해 함수에 세 번째 매개 변수를 추가 할 수 있습니다. 다음은 매우 간단하고 비효율적 인 솔루션입니다.

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의 값이, 당신이 요소를 발견 한 후에도 변경에 계속됩니다

주 더욱이. 이를 방지함으로써 코드를보다 효율적으로 만들 수 있습니다. 그렇게하고 싶지 않다면 노드를 찾을 때 path의 값을 다른 변수에 복사하면 나중에 사용할 수 있습니다.