0

挿入の各ステップの後に、バイナリ検索ツリーの各ステージを印刷しようとしています。ただし、私のコードによって生成された出力は、最初のルート データ挿入ステップを見逃しているようで、特定の段階も繰り返します。これを行うためのクリーンで簡単な方法が必要です。を使用してそれを行う方法はありますか__dict__.values()。

私のコード:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def addNode(self, data):
        if data < self.data:
            if self.left is None:
                self.left = Node(data)
            else:
                self.left.addNode(data)  # recursively calling addNode method
        else:
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.addNode(data)

        if not self.left is None and not self.right is None:
            print self.left.data, self.data, self.right.data
        elif self.left is None and not self.right is None:
            print None, self.data, self.right.data
        elif not self.left is None and self.right is None:
            print self.left.data, self.data, None

if __name__ == '__main__':
    n = Node(5)
    #print n.__dict__.values()
    n.addNode(3)
    n.addNode(2)
    n.addNode(8)
    n.addNode(4)

生成される出力:

3 5 None
2 3 None
3 5 None
3 5 8
2 3 4
3 5 8

期待される出力:

None 5 None
3 5 None
2 3 None
3 5 8
2 3 4
4

2 に答える 2

1

これを設計した方法により、印刷ステップは、内側から外側への各再帰ステップで発生します。ですから、それをより理解するために、これを見ていきましょう。n.addNode(3)私たちに与えてくれるあなた

3 5 None

驚く様な事じゃない。しかし、あなたが期待していると言うとき：

2 3 None

両方を取得しますが、

2 3 None
3 5 None

これn.addNode(2)は、最初のレベル ( 3 5 None) を調べてから、下位レベル (data属性 =を持つノード) を調べるため3です。したがって、「裏返しに」印刷すると、2 3 None(新しいサブツリー) が得られ、最初のレベルが再び取得され3 5 Noneます。期待するときと同じ理由で、

2 3 4

代わりに、

2 3 4
3 5 8

最初のツリー (期待される場所None 5 None) が印刷されないという事実は、別の問題です。属性を初期化してdataいて、 を呼び出さないため、印刷部分に到達しないからですaddNone。

考えられる解決策 (構造を維持する) は、ノードをツリー構造に追加したときにのみ印刷し、最初のサブツリーを手動で印刷することです。たぶん、次のように書きます。

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def addNode(self, data):
        if data < self.data:
            if self.left is None:
                self.left = Node(data)
                self.printSubtree()
            else:
                self.left.addNode(data)  # recursively calling addNode method
        else:
            if self.right is None:
                self.right = Node(data)
                self.printSubtree()
            else:
                self.right.addNode(data)

    def printSubtree(self):
        if not self.left is None and not self.right is None:
            print self.left.data, self.data, self.right.data
        elif self.left is None and not self.right is None:
            print None, self.data, self.right.data
        elif not self.left is None and self.right is None:
            print self.left.data, self.data, None
        else:
            print None, self.data, None

if __name__ == '__main__':
    n = Node(5)
    n.printSubtree()
    n.addNode(3)
    n.addNode(2)
    n.addNode(8)
    n.addNode(4)
于 2013-03-29T04:29:29.507 に答える
0

1-ノードを追加した後に印刷したため、期待どおりにNone、Number、Noneの要素が見つかりません（ノードを追加する前に、この部分を移動してみてください）。2-印刷時に3つの可能性しか考慮していませんでしたが、別の可能性があります。左右のノードが両方ともNoneの場合、これを追加してみてください。

于 2013-03-29T03:44:40.407 に答える