3

この本で説明されている二分木を使用して、 アルゴリズムとデータ構造で問題を解決しています

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

次のように定義された preorder traversal メソッドが既にあります。

def preorder(tree):
    if tree:
        print(tree.self.key)
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())

訪問したノードのリストの戻り値を追加したいだけです。だから私は次のようなことができます

for i in preorder(tree):
    etc...

再帰メソッドからリストを返すのに問題があります。「リターン」に到達するとすぐに再帰が停止します

return [tree.self.key] + preorder()

または

yield ...

何か案は？

4

4 に答える 4

5

印刷するときtree.self.keyだけでなく、本当にしたいですか？tree.key

yield fromそれ以外の場合、 (Python 3.3+)を使用したソリューション:

def preorder(tree):
    if tree:
        yield tree
        yield from preorder(tree.getLeftChild())
        yield from preorder(tree.getRightChild())

またはシンプルでyield：

def preorder(tree):
    if tree:
        yield tree
        for e in preorder(tree.getLeftChild()):
            yield e
        for e in preorder(tree.getRightChild()):
            yield e

関数をジェネレーター関数yieldに使用またはyield from変換することに注意してください。特に、実際のリストが必要な場合 (たとえば、インデックス作成、スライス、または表示用)、明示的に作成する必要があります: .list(preorder(tree))

さまざまな数の子供がいる場合は、簡単に適応できます。

def preorder(tree):
    if tree:
        yield tree
        for child in tree.children:
            yield from preorder(child)
于 2015-04-18T14:54:07.383 に答える
2

再帰関数から実際に値を返す必要があります (現在は値を出力するだけです)。そして、次のようにリストを作成し、コードを少しクリーンアップする必要があります。

def preorder(tree):
    if not tree:
        return []
    # optionally, you can print the key in this line: print(self.key)
    return [tree.key] + preorder(tree.leftChild) + preorder(tree.rightChild)
于 2015-04-18T14:52:18.427 に答える
1

preorder次のように、関数に2番目の引数を追加できます

def preorder(tree, visnodes):
    if tree:
        visnodes.append(tree.self.key)
        print(tree.self.key)
        preorder(tree.getLeftChild(), visnodes)
        preorder(tree.getRightChild(), visnodes)

...
vn = []
preorder(tree, vn)
于 2015-04-18T14:52:21.017 に答える
0

現在のキー、左側のサブツリー、右側のサブツリーを組み合わせた再帰呼び出しごとに連結リストを返すだけです。

def preorder(tree):
        if tree:
            return ([tree.key] + preorder(tree.getLeftChild()) +
                    preorder(tree.getRightChild()))
        return []

n 分木の場合:

def preorder(tree):
    if tree:
        lst = [tree.key]
        for child in tree.children:
            lst.extend(preorder(child))
        return lst
    return []
于 2015-04-18T19:35:09.843 に答える