1

この質問は学校（宿題）に関するものなので、私はコードを求めていません。コードは必要ありません。ただのアイデアです。葉のリストと二分木の内部ノードのリストの2つのリストを返す関数を作成する必要があります。私のアルゴリズムは次のとおりです。

1）左右両方のサブツリーがNoneの場合、それは葉であるため、葉のリストに追加します。

2）そうでない場合は、それを内部リストに追加し、左側のサブツリーで関数を呼び出し、存在する場合は右側で関数を呼び出します。

これは私が書いたコードです：

def leaves_and_internals(self):
    leaves = []
    internals = []

    if self.left is None and self.right is None:
        leaves.append(self.item)
    else:     
        internals.append(self.item)
        if self.left != None:
            leaves_and_internals(self.left)
        else:
            leaves_and_internals(self.right)
    return internals, leaves

アルゴリズムは正しいと確信していますが、ノードで再帰するたびに、リストがリセットされると思います。どうすればこれを回避できますか？

どんな助けでも大歓迎です。ありがとう

4

1 に答える 1

1

私はあなたのコードのアルゴリズムを調べていません. andを引数として再帰関数に渡すleavesと、それらの内容が再帰呼び出し間で保持されます。internals

Python ではmutable object、関数/メソッドに a を渡すと、関数/メソッドはオブジェクトへの参照を取得します。したがって、それを同じ変更可能なオブジェクトとして扱う限り (つまり、パラメーターに他の何かを直接割り当てない)、オブジェクトに加えた変更は呼び出し元にも表示されます。listは であるため、mutable typeこの動作は関心のあるケースに非常に役立ちます。

また、外部から関数を[]呼び出す前に、必ずリストを初期化してください。leaves_and_internals

def leaves_and_internals(self, leaves, internals):
    if self.left is None and self.right is None:
        leaves.append(self.item)
    else:
        internals.append(self.item)
        if self.left != None:
            leaves_and_internals(self.left, leaves, internals)
        else:
            leaves_and_internals(self.right, leaves, internals)
    return


 # Somewhere outside
 leaves = []
 internals = []
 myobj.leaves_and_internals(leaves, internals)

アップデート：

OPはメソッドのシグネチャを変更したりインスタンス変数を使用したりできないと述べているため、これは私が考えることができる代替ソリューションであり、葉と内部を呼び出し元に返します。ところで、ツリー内のいくつかのノードは左右の両方を持つことができると想定しているため、両方をチェックする必要があります (つまりif、 の代わりに2 つの個別を使用しますif...else)。

def leaves_and_internals(self):
    leaves = []
    internals = []
    if self.left is None and self.right is None:
        leaves = [ self.item ]
    else:
        if self.left != None:
            leaves, internals = leaves_and_internals(self.left)
        if self.right != None:
            templeaves, tempinternals = leaves_and_internals(self.right)
            leaves += templeaves
            internals += tempinternals
        internals.append(self.item)
    return leaves, internals
于 2013-03-08T06:01:10.507 に答える