-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(log n) の代わりに O(n) ルックアップにツリーを使用する理由、つまり二分探索ツリーを使用しない理由があると確信しているので、それについては質問しません:)

問題を解決するには、関数に 3 番目のパラメーターを追加して、パスを維持します。以下は、非常に単純で非効率的な解決策です。

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後で使用できるように、ノードを見つけたときに他の変数に値をコピーします。

于 2013-10-23T17:52:38.093 に答える