Python(19)二分木を出力する部分をwhile文で書く

前の関連記事：Python(18)リストから二分木を生成する

前回はリストから二分木を生成する部分をwhile文にしましたが、今度はその生成した二分木を木の形で出力する部分をwhile文にします。

まずスタックになにを入れるのかを調べる

    def __repr__(self, level=0, indent="    "):  # repr(このクラスのインスタンス)で呼び出されたときに文字列を返す特殊メソッド。repr(ノード)でそのノードから葉まで出力する。levelは木の階層（根を0階層とする）、indentは出力するときのインデント。
        s = level*indent + repr(self.label)  # ノードの値を階層に応じたインデントをつけて出力する。sが出力する文字列になる。
        if self.left:  # 左の枝につながるノードがあるとき。
            s = s + "\n" + self.left.__repr__(level+1, indent)  # 左の枝につながるノードについて階層を一つ加えて出力する。
        if self.right:  # 右の枝につながるノードがあるとき。
            s = s + "\n" + self.right.__repr__(level+1, indent)  # 右の枝につながるノードについて階層を一つ加えて出力する。
        return s  # repr(ノード)のノードについてpreorder(行きかけ順）(出力、左の枝、右の枝の順に処理したから）にそのノードから葉まで出力することになる。

これが前回の最後にでてきたプログラムの木の構造を出力する部分です。

10行目と12行目で__repr__()を再帰的に呼び出しています。

2行目のrepr()の引数の型はノードオブジェクトではなくそれのインスタンス変数である文字列self.labelなので__repr__()とは違います。

repr(文字列)は文字列と同じなのでrepr()はなくても文字列がそのまま出力(たとえば「N」）されるだけです。

repr(文字列)は引数がそのままの形で出力されるので、'文字列'、（たとえば「'N'」）というように引用符がついてきます。

さらに再帰を除去するのにスタックになにをいれたらよいのか考えやすいように変数sをやめてそれぞれの戻り値を変数にいれてまとめて計算します。

    def __repr__(self, level=0, indent="    "):  # repr(このクラスのインスタンス)で呼び出されたときに文字列を返す特殊メソッド。repr(ノード)でそのノードから葉まで出力する。levelは木の階層（根を0階層とする）、indentは出力するときのインデント。
        label = level*indent +self.label # ノードの値を階層に応じたインデントをつけてノードインスタンスの値を取得。
        left, right = "", ""  # 左右のノードインスタンスの値を入れる変数。
        level += 1  # 階層を1加える。
        if self.left:  # 左の枝につながるノードがあるとき。
            left = "\n" + self.left.__repr__(level, indent)  # 左の枝につながるノードの値をleftに取得。
        if self.right:  # 右の枝につながるノードがあるとき。
            right = "\n" + self.right.__repr__(level, indent)  # 左の枝につながるノードの値をrightに取得。
        return label + left + right  # repr(ノード)のノードについてpreorder(行きかけ順）(出力、左の枝、右の枝の順に処理したから）にそのノードから葉まで出力することになる。

とりあえず前回同様に使っている変数を最後から抜き出してスタックにいれてみます。

indentは変更されることがない定数ですのでスタックには入れません。

[label, self.right, level, self.left, level]

15行目から12行目の1回目の再帰呼び出しまで遡るとこうなりますが、labelとself.right、self.leftはすべてselfがあれば計算できるので結局スタックにいれるのは[self, level]の二つだけでよいとわかります。

これでスタックの変化をシミュレートしてみます。

[ノードN, 0]
[ノードN, 0, ノードG, 1]
[ノードN, 0, ノードG, 1, ノードD, 2]
[ノードN, 0, ノードG, 1, ノードD, 2, ノードB, 3]
[ノードN, 0, ノードG, 1, ノードD, 2, ノードB, 3, ノードA, 4]
[ノードN, 0, ノードG, 1, ノードD, 2, ノードB, 3, ノードC, 4]
[ノードN, 0, ノードG, 1, ノードD, 2, ノードF, 3]
[ノードN, 0, ノードG, 1, ノードD, 2, ノードF, 3, ノードE, 4]
[ノードN, 0, ノードG, 1, ノードD, 2, ノードF, 3, ノード , 4]
[ノードN, 0, ノードG, 1, ノードK, 2]
[ノードN, 0, ノードU, 1]

とりあえず右半分だけしてみました。

ノードFの左は空白のラベルなので「ノード」と書いています。

各ノードについて左右共にノードをもっていないか、左右とも子ノードがスタックに追加されたらスタックから親ノードを削除すればよいとわかります。

特殊メソッドrepr()のデバッグはrepr()以外でやる

__repr__()をwhile文で書き直してPyCharmでデバッグしてみたら、ブレークポイントに行く前にループが止まらなくなってしまって、1度もStep Overボタンが押せません。

何が起こっているのか把握するまで戸惑いましたが、原因がわかりました。

__repr__()はDebuggerタブでVariablesの表示に使われているのが原因でした。

デバッガ画面で実行される__repr__()にはブレークポイントが効きません。

なので__repr__()にバグがあるとデバッガが動きません。

ということで__repr__()のデバッグをするときは__repr__()以外に関数を用意してそこでやらないといけません。

そこでdbg_repr()という関数を用意してそれでデバッグすることにしました。

__repr__()は元のままでは木構造が出力されてしまって、デバッグ画面では見にくいのでノードの値のみ返すようにしました。

python19.py

これを実行すると以下が出力されます。

12行目のコメントアウトをはずすとスタックの変化がわかります。

[N, 0]
[N, 0, G, 1]
[N, 0, G, 1, D, 2]
[N, 0, G, 1, D, 2, B, 3]
[N, 0, G, 1, D, 2, B, 3, A, 4]
[N, 0, G, 1, D, 2, B, 3]
[N, 0, G, 1, D, 2, C, 4]
[N, 0, G, 1, D, 2]
[N, 0, G, 1, F, 3]
[N, 0, G, 1, F, 3, E, 4]
[N, 0, G, 1, F, 3]
[N, 0, G, 1, , 4]
[N, 0, G, 1]
[N, 0, K, 2]
[N, 0, K, 2, I, 3]
[N, 0, K, 2, I, 3, H, 4]
[N, 0, K, 2, I, 3]
[N, 0, K, 2, J, 4]
[N, 0, K, 2]
[N, 0, M, 3]
[N, 0, M, 3, L, 4]
[N, 0, M, 3]
[N, 0, , 4]
[N, 0]
[U, 1]
[U, 1, R, 2]
[U, 1, R, 2, P, 3]
[U, 1, R, 2, P, 3, O, 4]
[U, 1, R, 2, P, 3]
[U, 1, R, 2, Q, 4]
[U, 1, R, 2]
[U, 1, T, 3]
[U, 1, T, 3, S, 4]
[U, 1, T, 3]
[U, 1, , 4]
[U, 1]
[X, 2]
[X, 2, W, 3]
[X, 2, W, 3, V, 4]
[X, 2, W, 3]
[X, 2, , 4]
[X, 2]
[Z, 3]
[Z, 3, Y, 4]
[Z, 3]
[, 4]

シミュレートしたのとだいたい同じになっていますね。

右の枝のノードをとりにいくときに一旦親ノードが出現する点がシミュレートしたときと異なります。

バグがなくこれ以上修正することがなければdbg_repr()を__repr__()にします。

python19.py

p--q