1

(バイナリ) ツリーのルートから各リーフまでのすべてのパスを出力するアルゴリズムを Python で記述しようとしています。これが私のコードです：

def fb_problem(node, curr_trav):
    curr_trav = curr_trav + [node]

    if node.left is None and node.right is None:
        for path_node in curr_trav:
            print path_node.data 
        print "XXX"

    if node.left is not None:
        fb_problem(node.left, curr_trav)
    if node.right is not None:
        fb_problem(node.right, curr_trav)

fb_problem(root, [])

現在のトラバーサルでノードのリストを保持し、リーフに到達したらリストを出力します。ただし、Pythonがオブジェクトを渡す方法について誤解しています。各再帰呼び出しが完了してスタックからポップされると、元の変数は再帰呼び出しの影響を受けないだろうと考えました。curr_travしかし、それはまるでラインのようです

curr_trav += [node]

元のリストを変更しています。+=演算子は、元のオブジェクトを実際に変更する とは対照的に、新しいリストを返します.append()。この呼び出しは、元のオブジェクトを変更するのではなく、関数内のオブジェクトに与えられた名前を再割り当てするだけであってはなりませんか? 行を次のように変更すると

t_trav = curr_trav += [node]

すべて正常に動作しますが、元の行の問題が何であったかわかりません。私の質問が不明な場合はお知らせください。

4

2 に答える 2

4

Python では、値でも参照でもありません。これは両方の組み合わせであり、関数に渡されるオブジェクトのタイプによって異なります。たとえば、 のような変更可能な型dict, list etcが渡された場合、参照が渡されます。一方、 a などの不変型strでは、値によるものになります。このテーマについては、Jeff Knuppによる優れた読み物があります。

元のコードの問題curr_trav += [node]は、の値を追加[node]しcurr_trav、新しいリストへの参照を設定していることです。参照を渡すため、curr_trav後続の反復ごとに変更されます。

于 2016-03-31T19:01:50.523 に答える
1

あなたの理解+=は完全に正しくありません。Python のすべての演算子は、実際には単なるショートカットです。たとえば、a + bis a.__add__(b)ifaには__add__メソッドがあります。そうaでない場合は、ですb.__radd__(a)。bそのメソッドがない場合、エラーが発生します。通常、a += bは とまったく同じように動作しますa = a + bが、可変オブジェクトの場合、通常はそうではありません。それはa += bifa.__iadd__(b)がaメソッドを持っている__iadd__からです。そうaでない場合は と同じa = a.__add__(b)です。それもなければa、 と同じa = b.__radd__(a)です。リストにはメソッドがあるため__iadd__、 を再定義する代わりに、実際のリスト オブジェクトが変更されますcurr_trav。

于 2016-03-31T19:18:44.090 に答える