本を読む

読書やコンピュータなどに関するメモ

再帰も外部データ構造も使わずにtree traversalする

 2進木などのツリー構造の巡回(tree traversal)を、再帰も、スタックなどの外部データ構造も使わずに実現する方法について考えてみます。

再帰を使う場合

 ツリーを巡回するのに、いちばんシンプルな方法は、再帰的に辿る方法です。Scheme(Gauche)で素直に書くとこんな(↓)感じ。Schemeよくわかってませんが。

 実行。

$ gosh traverse-tree1.scm
3
5
7
11

データ構造を使ってループにする場合

 大きなツリー構造だったり、再帰の深さ制限がキツ目の言語(処理系)だったりすると、再帰を使わずに済ませたいところです。

 そういうときには、外部データ構造を使ってループにするのが定石かと思います。深さ優先ならスタック、幅優先ならキューとか。

 外部データ構造ではありませんが、ツリーのノードに項目を追加できるなら、親ノードや次の行き先などを持たせておく方法などもよく使われます。

コンスセルのツリーをループで巡回する場合

 再帰を使わず、外部データ構造も使わず、ノードはLispのコンスセル、という条件でtree traversalする方法もあります。ちょっと乱暴な方法ですが。

 考え方は「ノードを通るたびに、そのノードを120度回転する」というものです。

  1. コンスセルのcarを元のcdrの値に、コンスセルのcdrを参照元に変更
  2. 元のcarの値がコンスセルならそのコンスセルに移って1.に、コンスセルでなければそのまま1.に

 ツリーを破壊しまくって巡回しますが、一巡すると元の構造に戻ります。

 Scheme(Gauche)で書くとこんな(↓)感じ。名前付きletの末尾再帰はループということで。最後にtreeを表示しているのは、元に戻っていることを確認するためです。

 実行。

$ gosh traverse-tree2.scm
3
5
7
11
((3 (5 (7)) 11))

 めでたしめでたし。

ネタ元は?

 この方法は、大昔に雑誌のインタビューだかエッセイだかで見たアイデアを思い出して、実装してみたものです。大学のコンピュータサイエンスの授業とかで普通に話してそうですが、受けたことないのでわかりません。ネタ元をご存知の方、よろしければ教えてください。

コメント

コメントの投稿

管理者にだけ表示を許可する

トラックバック

http://emasaka.blog65.fc2.com/tb.php/797-3fd7409f

 | HOME | 

Categories

Recent Entries

Recent Comments

Recent Trackbacks

Appendix

emasaka

emasaka

フリーター。
連絡先はこのへん

Monthly


FC2Ad