平成15年秋期試験問題 午前問12

2分木の走査の方法には,その順序によって次の三つがある。
  • 前順:節点,左部分木,右部分木の順に走査する。
  • 間順:左部分木,節点,右部分木の順に走査する。
  • 後順:左部分木,右部分木,節点の順に走査する。
 図に示す2分木に対して前順に走査を行い,節の値を出力した結果はどれか。
12.png

  • abchidefjgk
  • abechidfjgk
  • hcibdajfegk
  • hicdbjfkgea
正解 問題へ
分野 :テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
解説
前順走査なので、節点 → 左部分木 → 右部分木の順に見ていきます。
まず、節点とその子に着目します。

 a → b → e

したがって、出力順は

a → b(を節点とする部分木) → e(を節点とする部分木)

なので、はじめにaが出力されます。
次に、左側のbを節点とする部分木は、

 b → c → d

したがって、出力順は

 b → c(を節点とする部分木) → d

なので、bが出力されます。
次に、cを節点とする部分木は、

 c → h → i

なので、cが出力されます。ここまでに出力されたのは

 a → b → c

したがって、正解は「ア」です。

※前順走査ではまず左部分木の節点をすべて走査し終わってから、右部分木の走査に移ります。
12a.png

Pagetop