忍者ブログ

GREサブジェクトテストCS分野問題第7問。2分木(binary tree)に関する問題。



まず、「木(tree)」とは何か、ってことから説明しようかな。あ、でも、その前に、どういうのが木なのか?ってのを実際に例示しといた方が話が早いか。つわけで、どん。

http://www.ehmtm.com/image/Binary_tree.png

ま、これ見てもらえれば直感的に、「あ、なるほど」だとは思うんだけど、一応くだくだしく言うと、

  1. 「根(root)」と呼ばれる点が1つある(この図だと、1が根)
  2. ある点と点が結ばれているとき、根に近い方を「親(parent)」、遠い方を「子(child)」と呼ぶ(たとえば、上の図で171が親で7が子)。
  3. 根は親を持たない。
  4. 子は1つの親しか持たない。
  5. 子のない点を「葉(leaf)」と呼ぶ(たとえば、2とか5とかが葉)。

って感じ。

で、2分木ってのは、上記の木の定義に「各点について、たかだか最大2つの子しか持たない」という制約を加えたもの。上の図は、もうまさに2分木。

さて、こうした2分木ってのは、その各点にデータが保持されていて、それを順々に取り出す、って使われ方をしたりするんだけど、そういう「順々に」各点を訪れるやり方ってのがまあ色々あって、ここでは「プレオーダ・トラヴァーサルpreorder traversal」、「インオーダ・トラヴァーサルinorder traversal」「ポストオーダ・トラヴァーサルpostorder traversal」というのを説明。

ほんじゃ、ちょっと次のコードを見てもらいましょ。

visit(node)

    /* preorder */
if node.left  != null then visit(node.left)
/* inorder */
if node.right != null then visit(node.right)
/* postorder */

で、このコードの/* preorder */の部分にprint node.valueを代入したものがプレオーダ・トラヴァーサルのアルゴリズム、/* inorder */の部分に……って感じなんだけど、うーん、これだけじゃよう分からんだろうから、上の図を例に、コードを追ってみよう。


プレオーダ・トラヴァーサルの場合

  1. 最初のvisit(node)で根を訪れる。
  2. 次に、/* preorder */にはprint node.value代入されているわけだから、その根の値、つまり1を出力(print)する。
  3. 3行目ではまず、今いる点の左に子がいるかどうかを検査する(if node.left != null)。子がいる場合、その子を「根」として、再帰的にvisit(node)を実行する(上記の図の場合、根に子7がいるわけだから、visit(7)が実行される)。
  4. visit(7)では、まず7が出力され、次に7の左に子がいるかどうか検査される。この場合、7には子2がいるから、visite(2)が実行される。
  5. visit(2)では、まず2が出力され、2の左に子がいるかどうか検査されるが、この場合いないので、次のラインで2の右に子がいるかどうか検査される。2には右にも子がいないので、このvisit(2)ルーチンはここで終了。
  6. さて、visit(2)は工程4のif node.left != null then visit(node.left)で呼び出されていたのだから、その次、つまりvisit(7)のif node.right != null then visit(node.right)に処理が戻る。つまり、7の右に子がいるかどうかが検査され、子がいる場合、その子を元にvisit(node)が呼び出される。上図の場合、7の右には子6がいるから、visit(6)が呼び出される。
  7. ……



という具合に、結局上図の場合、このコードの出力は、「1,7,2,6,5,11,3,9,4」となる。

そして、インオーダの場合は「2,7,5,6,11,1,3,4,9」、ポストオーダの場合は「2,5,11,6,7,4,9,3,1」って具合。



まあ、話を聞いただけじゃ分かんないだろうから(って、お前の説明が下手くそなんじゃ!と言われれば、何とも言い返せないけど)、是非上記のコードの挙動を、紙に書き下ろしてみたりしてください。そうすりゃ、何となく分かってくる、と思います。

PR
この記事にコメントする
お名前
メールアドレス
URL
コメント
この記事へのトラックバック
この記事にトラックバックする:
カレンダー
09 2017/10 11
S M T W T F S
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
最新コメント
[10/17 american express career login]
[10/17 Serovital hgh]
[10/17 韓国 偽ブランド]
[10/17 ロレックス 時計 コピー]
[10/17 mom]
[10/17 mom]
[10/17 PatrickHek]
[10/17 ブランド激安市場タグ・ホイヤー]
[10/16 エルメスコピー]
[10/16 シャネル時計]
最新トラックバック
メール
ブログ作成者(はやし)に直接訴えたいことがある、という場合は、下のアドレスにメールをどうぞ。

thayashi#ucalgary.ca
(#を@に置換してください)

ブログ内検索
Google
WWW を検索 このブログ内を検索

はやしのブログ内で紹介された
 書籍の検索はこちら
 音盤の検索はこちら
ランダムおすすめ
(忍者ブログに引越してから、うまくうごかなくなってしまいました。いつか、直します)
Randombook
このブログで紹介したことのある本をランダム表示。
Randomusic
このブログで紹介したことのある音をランダム表示。
自分がらみのリンク
はやしのブログ書籍一覧
このブログで言及された書籍の一覧。
はやしのブログ音盤一覧
このブログで言及された音盤の一覧。
最近のおすすめ本
最近のおすすめ音

Copyright © [ はやしのブログ ]
No right reserved except those which belong to someone else.
Special Template : 忍者ブログ de テンプレート and ブログアクセスアップ
Special Thanks : 忍者ブログ
Commercial message : [PR]