2分木とは？

2分木の意味

各節（ノード）が子を最大2個まで持つ木構造。根から葉に向かって枝分かれし、階層的なデータの表現や探索に使う。FEでは走査（なぞる）順序である先行順・中間順・後行順の3つと、その出力列が頻出。

2分木の具体例

中間順（左部分木→自分→右部分木）で走査すると、2分探索木では値が昇順に並んで出力される。式を表す木を後行順で走査すると、そのまま逆ポーランド表記法の並びが得られる。

2分木は試験でどう引っ掛けられる？

3つの走査順は「自分をいつ出力するか」で決まる。先行順は自分が先、中間順は左右の間、後行順は最後。左を右より先にたどる点は3つとも共通なので、そこを変えて覚えないこと。

2分木と関連する用語

• 2分探索木
• 逆ポーランド表記法
• 連結リスト

2分木が出た過去問

• 2分探索木になっている2分木はどれか。

  正解：根17、左の子14（左の子10、右の子16）、右の子19（左の子18）。

  要点：2分探索木は左部分木＜節点＜右部分木が全節点で成立

  2分探索木は、任意の節点について左部分木のすべての値がその節点より小さく、右部分木のすべての値が大きいという条件を満たす木である。根17に対し左側が10・14・16、右側が18・19となり、さらに14の左が10・右が16、19の左が18と、どの節点でも条件が崩れていない木が正解となる。

  出典：平成28年度 秋期 基本情報技術者試験 午前 問6（IPA）

• 10個の節（ノード）から成る次の2分木の各節に，1から10までの値を一意に対応するように割り振ったとき，節a，bの値の組合せはどれになるか。ここで，各節に割り振…

  正解：a＝6，b＝7

  要点：2分探索木は左→節→右の順に走査すると値が昇順に並ぶ

  この条件は2分探索木の性質そのもので、木を左から順に（左部分木→自分→右部分木の順に）たどると値が1から10まで昇順に並ぶ。根が5なので左部分木の4個の節に1〜4、右部分木の5個の節に6〜10が入る。右部分木はaに左の子が無く右の子をもつ形なので、その順序ではaが最初に来て6、次にaの右の子の左の子であるbが7となる。

  出典：平成28年度 春期 基本情報技術者試験 午前 問5（IPA）

• 2分探索木になっている2分木はどれか。

  正解：イ：根17、左の子14（さらに左10・右16）、右の子19（さらに左18）

  要点：2分探索木は全節点で左部分木＜節点＜右部分木が成立する

  2分探索木は、任意の節点について左部分木の全要素がその節点より小さく、右部分木の全要素が大きいという条件を満たす木である。各木で節点ごとにこの大小関係を確認すると、条件を崩す節点が無いものは1つだけである。根より小さい値が右側にある、あるいは左の子より大きい値が左部分木にあるといった違反があれば2分探索木ではない。

  出典：令和4年度 s 基本情報技術者試験 kamokuA 問5（IPA）

• 次の記述中の に入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。 手続orderは、図の2分木の、引数で指定した節を根とする部分木…

  正解：8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7

  要点：左→自分→右の順に出力するのは中間順走査

  この手続は、左の子をたどってから自分の節番号を出力し、その後で右の子をたどる順序、すなわち中間順（in-order）走査です。最も左下の葉である8から出発し、8、4、9、2……と進み、根の1はちょうど中間に現れます。節7は子が左の14だけなので、14を出力してから7を出力します。

  出典：令和4年度 s 基本情報技術者試験 kamokuB 問9（IPA）