前の関連記事：Python(6)WSGIサーバの例をいじっていろいろPythonのお勉強
二分木はもう20年以上前に大学の情報科学の授業で習いました。当時はコンパイラやインタプリタはおろかパソコンにすら触れられる機会がなかったので理解できているのかできていないのか全然わかりませんでしたが、やっぱり全然理解できていませんでした、、、
生成した二分木を視覚的に確認できるPythonの例がほしい
二分木がなんであるのかと部位の名称についてはコーディングに役立つ！ アルゴリズムの基本（2）：データ構造の選択次第で天国と地獄の差 (3/3) - ＠ITがわかりやすかったです。
値をもっているのノード（節）、根源になるノードをルート（根）、逆に末端にくるノードをリーフ（葉）、そしてこれらすべてを含めてツリー(木)というのだと思います。
ノードのことをルートと同義のように解説しているページもあってわかりにくかったです。
二分木を作成するPythonの例もいくつか見つけたのですが、その生成した木の構造を視覚的に出力してくれる例をなかなかみつけられませんでした。
何ができているのかが理解できないのでどうやって扱うのかがわからないのですよね。
木の各ノードの値を取得する順番でpreorder(行きかけ順）やinorder（通りがけ順）、postorder（帰りがけ順）の3種類あることがわかりましたが、もとの木の構造が理解できていないので意味がつかめないのです。
ネットをみてもよくわからなかったので本屋に行ってきました。
Pythonで書いたアルゴリズム集がほしかったのですがCの例のものばかりでようやくJavaScriptで書いたこの本を見つけて買いました。
122ページの薄い本なので早速全部読みました。
基本的なことが網羅してあってとても勉強になりましたが、またJavaScriptを使うときに読み直すことにします。
とくに第6章の文字処理のところが面白いな、と思ったのと再帰関数を使うには数列の感覚を思い出さないといけないと思いました。
昔授業で使ったのはPascalの例が載った「データ構造とアルゴリズム」という黄色と白のカバーのついた本だったのですがもう捨ててしまっていました。
preorder(行きかけ順）やinorder（通りがけ順）、postorder（帰りがけ順）の3種類についてはData Structures Notes: Binary tree traversal: Preorder, Inorder, and Postorderがわかりやすかったです。
同じ解説が載っている本も本屋でみかけましたがどの本かわからなくなってしまって買えませんでした。
2時間もあれこれ読んで探して回って疲れてしまいました。
ツリー構造を出力する機能もついたPythonの例をPython 3.3.3 ドキュメントで発見
結局意外なところでほしかった例をみつけました。
Python のライブラリに含まれているテストスイート Lib/test/test_generators.py には、ほかにも興味深い例が数多く入っています。これは二分木の通りがけ順 (in-order) 探索を再帰で実装したジェネレータです。
ジェネレータ (generator)
ほうほう。私が使っているLibreOffice4.2のバンドル版Python3.3.3インタプリタには付属していませんでしたがtestライブラリに二分木の例があるというのでそれを見てみました。
cpython: 1a3f2d0ced35 Lib/test/test_generators.py
これの228行目から295行目です。
コンソールでの入力が書いてあるようでこのままコピペしても動きませんのでちょっと書き直さないといけません。
書き直して使ってみるとツリーの出力ができました。
これをいじって二分木の勉強をします。
参考にしたサイト
コーディングに役立つ！ アルゴリズムの基本（2）：データ構造の選択次第で天国と地獄の差 (3/3) - ＠IT
二分木の基本の解説。
Data Structures Notes: Binary tree traversal: Preorder, Inorder, and Postorder
preorder(行きかけ順）やinorder（通りがけ順）、postorder（帰りがけ順）の比較がわかりやすいです。
Binary tree
最後に載っているExercisesの下にあるリンクに例があります。新規ノードをルート直下に挿入しています。
Algorithms with Python / 二分木, ヒープ
日本語で詳しく解説されています。
cpython: 1a3f2d0ced35 Lib/test/test_generators.py
この228行目から295行目が二分木のPythonの例です。ツリーの出力機能もあります。
0 件のコメント:
コメントを投稿