数の木があります。各ノードは、左右の子ノードを持つことができます。数字は繰り返すことはできませんが、ツリーのどこにでもある可能性があります。ツリーで番号を検索し、ツリーのルートへの経路を出力する必要があります。
ノードに親を追跡させる方法がわからないので、それらをルートに戻すことができます。どうすればこれを達成できますか?
次のようにコードします。
# 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)