前の関連記事：Python(17)再帰関数の例を非再帰にする:まとめ編
Python(7)二分木(Binary Tree)の勉強資料を求めて本屋へを書いているときに見つけたGuido's binary tree exampleはジェネレータ (generator)の例として紹介されているものです。リストから二分木を生成しています。再帰や特殊メソッドがてんこ盛りで理解するのに苦労しました。
Guido's binary tree example:二分木を生成して二分木の構造を出力する例
二分木からのデータの取り出し方についてはpreorder(行きかけ順）やinorder（通りがけ順）、postorder（帰りがけ順）の3種類がある(Data Structures Notes: Binary tree traversal: Preorder, Inorder, and Postorder)というのはわかったのですが、その取り出すもととなる二分木のデータの用意の仕方がよくわかりませんでした。
cpython: 1a3f2d0ced35 Lib/test/test_generators.pyの228行目から295行目にあるGuido's binary tree example二分木のPythonの例では、文字列"ABCDEFGHIJKLMNOPQRSTUVWXYZ"から二分木を生成してその構造を出力しています。
# -*- coding: utf-8 -*-
class Tree: # これのインスタンスが二分木のノードとなる。
def __init__(self, label, left=None, right=None): # インスタンス化のときの第一引数をノードの値に、第二引数を左の枝につながるノードに、第3引数を右の枝につながるノードにする。
self.label = label # ノードの値を設定。
self.left = left # 左の枝につながるノードを設定。
self.right = right # 右の枝につながるノードを設定。
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(行きかけ順）(出力、左の枝、右の枝の順に処理したから）にそのノードから葉まで出力することになる。
def tree(list): # 引数のリストから二分木を作成する関数。
n = len(list) # リストの要素数を取得。
if n == 0: # リストの要素数が0のとき。
return [] # 空のリストを返す。
i = n // 2 # リスト要素数が0ではないときリストのi番目の要素を値とするとノードを生成する。
return Tree(list[i], tree(list[:i]), tree(list[i+1:])) # i番目の要素を値に持つノードインスタンスを生成。
t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ") # 引数のリストから二分木を生成してその根をtに取得。
print(repr(t)) # 根tについてpreorder(行きかけ順）に出力。
特殊メソッドobject.__repr__(self)を7行目で使っています。repr(インスタンス)で呼び出されたときに返す文字列を定義します。
これを定義してあるとPyChramのデバッグ画面でも、インスタンスの中身が定義したとおりにみれるのでデバッグしやすいですね。
木構造というのはそれぞれのノードインスタンスが根となるノードインスタンスからそのメンバー変数としてつながっている構造になっています。
ということでノードの数だけTreeクラスのインスタンスが生成されることになりますが、一番最初に生成したノード（つまり根）インスタンスからたどっていけばすべてのノードインスタンスを扱えることになります。
それぞれのノードは葉の方向へつながるノードの情報はもっていても、根の方向へ向かうノードの情報は持っていないのですべてのノードにアクセスできるのは根だけとなります。
なので20行目で根のtを取得すればあとはこれからすべてのノードにアクセスできます。
print(repr(t))の結果以下が出力されます。
'N'
'G'
'D'
'B'
'A'
'C'
'F'
'E'
'K'
'I'
'H'
'J'
'M'
'L'
'U'
'R'
'P'
'O'
'Q'
'T'
'S'
'X'
'W'
'V'
'Z'
'Y'
このままではちょっとわかりにくいのですが、これは二分木を反転して上に左がきた状態で出力されています。
元の図を鉛直軸で反転して反時計周りに90度回しています。
普通の二分木の図のように出力したいのですが、それは難しいのでせめて枝だけでも付けてみようと思います。
再帰関数への手の入れ方が私にはいまいち理解できないのでまずはwhile文に書き直します。
while文で二分木を生成する。ノードの階層を考慮する必要あり。
まずはリストから二分木を生成する14行目のtree()関数をwhile文で書き換えます。
ノードをインスタンス化Treeクラスのインスタンス化の引数になっている19行目の再帰部分を再帰とはっきりわかるように引数をそろえます。
16行目のリストの要素数が0個のとき空のリストを返して、ノードの枝に使っていますがこれはNoneを返しているのと同じことなのでリストの要素が存在しないときは何もしないようにしています。
python18.py
Python(17)再帰関数の例を非再帰にする:まとめ編でやっている手法と同じようにして再帰を除去します。
まずはwhile stack:にしたときにstack（スタック）に何をいれるのかを考えます。
再帰関数tree()から値が返ってくるのはNoneかクラスTree()のインスタンスです。
これは再帰で呼び出されたtree()から値が返ってきたときにまた使う値になりますので、
再帰関数tree()から値が返ってくるのは引数のリストの要素がないときのNoneか24行目で返されるクラスTree()のインスタンスです。
それが返ってきたときまでに保持しておかないといけないものがスタックに入れないといけないものです。
21行目にある1回目の再帰の値が返ってきたあとに使うのは22行目のlst2と24行目のlabelと1回目の再帰の戻り値のleftの3つです。
23行目にある2回目の再帰の値が返ってきたあとに使うのは24行目のlabelと1回目の再帰の戻り値のleftと2回目の再帰の戻り値の3つです。
ということで1回の再帰を回すのに3個の値をスタックに保持すればよいとわかります。
最初に使うのはlst1で次にlst2最後にlabelを使います。
なのでスタックへは使う逆順にいれるのでスタックの初期値は[label, lst2, lst1]となります。
あとは戻り値で置き換えていき、スタックがなくなれば計算終了となります。
ためしに具体的にスタックの中身を書き出してみます。
N, OPQRSTUVWXYZ, ABCDEFGHIJKLM N, OPQRSTUVWXYZ, G, HIJKLM, ABCDEF N, OPQRSTUVWXYZ, G, HIJKLM, D, EF, ABC N, OPQRSTUVWXYZ, G, HIJKLM, D, EF, B, C, A N, OPQRSTUVWXYZ, G, HIJKLM, D, EF, B, C, A, [], [] N, OPQRSTUVWXYZ, G, HIJKLM, D, EF, B, C, A, [], None N, OPQRSTUVWXYZ, G, HIJKLM, D, EF, B, C, A, None, None N, OPQRSTUVWXYZ, G, HIJKLM, D, EF, B, C, ノードA N, OPQRSTUVWXYZ, G, HIJKLM, D, EF, B, C, [], [], ノードA N, OPQRSTUVWXYZ, G, HIJKLM, D, EF, B, C, [], None, ノードA N, OPQRSTUVWXYZ, G, HIJKLM, D, EF, B, C, None, None, ノードA N, OPQRSTUVWXYZ, G, HIJKLM, D, EF, B, ノードC, ノードA N, OPQRSTUVWXYZ, G, HIJKLM, D, EF, ノードB N, OPQRSTUVWXYZ, G, HIJKLM, D, F, [], E, ノードB N, OPQRSTUVWXYZ, G, HIJKLM, D, F, [], E, [], [], ノードB N, OPQRSTUVWXYZ, G, HIJKLM, D, F, [], E, [], None, ノードB N, OPQRSTUVWXYZ, G, HIJKLM, D, F, [], E, None, None, ノードB N, OPQRSTUVWXYZ, G, HIJKLM, D, F, [], ノードE, ノードB N, OPQRSTUVWXYZ, G, HIJKLM, D, F, None, ノードE, ノードB N, OPQRSTUVWXYZ, G, HIJKLM, D, ノードF, ノードB N, OPQRSTUVWXYZ, G, HIJKLM, ノードD N, OPQRSTUVWXYZ, G, K, LM, HIJ, ノードD N, OPQRSTUVWXYZ, G, K, LM, I, J, H, ノードD N, OPQRSTUVWXYZ, G, K, LM, I, J, H, [], [], ノードD N, OPQRSTUVWXYZ, G, K, LM, I, J, H, [], None, ノードD N, OPQRSTUVWXYZ, G, K, LM, I, J, H, None, None, ノードD N, OPQRSTUVWXYZ, G, K, LM, I, J, ノードH, ノードD N, OPQRSTUVWXYZ, G, K, LM, I, J, [], [], ノードH, ノードD N, OPQRSTUVWXYZ, G, K, LM, I, J, [], None, ノードH, ノードD N, OPQRSTUVWXYZ, G, K, LM, I, J, None, None, ノードH, ノードD N, OPQRSTUVWXYZ, G, K, LM, I, ノードJ, ノードH, ノードD N, OPQRSTUVWXYZ, G, K, LM, ノードI, ノードD N, OPQRSTUVWXYZ, G, K, M, [], L, ノードI, ノードD N, OPQRSTUVWXYZ, G, K, M, [], L, [], [], ノードI, ノードD N, OPQRSTUVWXYZ, G, K, M, [], L, [], None, ノードI, ノードD N, OPQRSTUVWXYZ, G, K, M, [], L, None, None, ノードI, ノードD N, OPQRSTUVWXYZ, G, K, M, [], ノードL, ノードI, ノードD N, OPQRSTUVWXYZ, G, K, ノードM, ノードI, ノードD N, OPQRSTUVWXYZ, G, ノードK, ノードD N, OPQRSTUVWXYZ, ノードGとりあえず左半分だけやってみました。
どうでしょう？規則性を見出せるでしょうか？
単一文字に続くス2項目がノードがNoneになれば、その単一文字を値とするノードになる、と思ったのですが、27行目で規則違反になります。
N, OPQRSTUVWXYZ, G, K, LM, I, J, ノードH, ノードD規則に従うとここでノードJを作ることになりますがそうするとノードの階層がおかしくなります。
33行目も同じ規則違反となります。
なので階層が違うノード同士では新たなノードを作れないようにしないといけません。
さらに、値もインスタンスもすべて単一のスタックに収めるこの方法ですと、スタックからpop()した値がリストなのかインスタンスなのかの判定もしないといけないのでこれも改善しないといけません。
要素の階層を保存するスタックを別に作る。リストとインスタンスを別のスタックにする。
ということでノードの値をいれたリストと生成したノードインスタンスを収めるスタックを別に用意し、さらにそれぞれの階層を保持したスタックも用意することにしました。
python18.py
これでtree()の再帰の除去に成功しました。（と思ったらバグがありましたので下で修正しました。）
再帰のものと違って値をもたないノードのインスタンスも生成するようにして、左右がわかるようにしています。
これでできたと思ったら"ABCDEFGHIJKLMNOPQRSTUV"までtree()の引数を削るとうまくいきませんね。
公開から3日経ってようやく気づきました。
調べてみると28行目のifが成立しないときにノードのつながりが切れていました。
それを修正してからさらに削っていくと"ABCDEFGHIJKLMNOPQRS"でCとDが出力されません。
結局原因は28行目と29行目の入れ子のif文で逃している場合があるとわかりましたがのでこれらを一文にまとめました。
さらに最初に与えるリストの要素が2個以下のときにもノードがつながらないので最初に場合分けしました。
python18.py
これで抜けはないはずです。
場合分けの手間を考えると再帰関数の方が理論的で抜けがなくてよさそうですね。
このバグに気づくまでにこのコードを元に次の次の記事まで書いていたので全部修正しないといけません。
3個以下の要素をまとめて処理すれば結合するノードの階層は考えなくてよいようだ
これは大間違いでした。
階層のスタックは必要です。
最初に記事を書いたときは416個の要素で8階層で階層のスタックを省いて実行して問題がなかったのでいけると思ったのですが、問題は要素の数を減らしたときに発生していました。
"ABCDEFGHIJKLMNOPQRSTUV"を引数にして実効すると階層2のOと階層3のTが階層3のVの個ノードになってしまいます。
参考にしたサイト
cpython: 1a3f2d0ced35 Lib/test/test_generators.py
この228行目から295行目が二分木のPythonの例です。ツリーの出力機能もあります。
Data Structures Notes: Binary tree traversal: Preorder, Inorder, and Postorder
preorder(行きかけ順）やinorder（通りがけ順）、postorder（帰りがけ順）の比較がわかりやすいです。
Pythonの特殊メソッドの解説。Dive Into Python 3 (Books for Professionals by Professionals)
の日本語版。
の日本語版。
0 件のコメント:
コメントを投稿