アルゴリズムとプログラミング

空の二分探索木（BST）に対して、次の順序でキーを挿入した：50, 30, 70, 20, 40, 60, 80。この木を中間順（in-order）走査したときの出力として、正しいものはどれか。

ア.20, 30, 40, 50, 60, 70, 80正解

イ.50, 30, 20, 40, 70, 60, 80

ウ.20, 40, 30, 60, 80, 70, 50

エ.50, 30, 70, 20, 40, 60, 80

解説

BSTの中間順走査は「整列のための魔法呪文」。左→自分→右の順で訪問するだけで、勝手にソート済みリストが出てきます。挿入順は関係なく、必ず昇順になるのがBSTの不変条件です。

なぜアが正解か

アが正解。まず木を構築：50が根、30は左子、70は右子、20は30の左子、40は30の右子、60は70の左子、80は70の右子。中間順走査（左→自分→右）：①左部分木(30の枝)：20→30→40、②根：50、③右部分木(70の枝)：60→70→80 → 20, 30, 40, 50, 60, 70, 80。BSTの定義「左<親<右」が成立する限り、中間順走査は常に昇順ソートを返す。

なぜイは間違いか

50, 30, 20, 40, 70, 60, 80 は先行順（pre-order：自分→左→右）の出力。「自分が先か後か」で順序が変わる。

なぜウは間違いか

20, 40, 30, 60, 80, 70, 50 は後行順（post-order：左→右→自分）の出力。式の評価などで使う走査順。

なぜエは間違いか

50, 30, 70, 20, 40, 60, 80 は挿入順そのまま。レベル順（幅優先）走査の結果と偶然一致するが、中間順とは別物。

出典: AI生成問題（学習用）

← 前の問題

空のスタックに対して次の順序で操作を行った。push(1), push(2), pop, push(3), push(4), pop, push(5), pop, pop。すべての操作後、スタックに残っている要素を底から順に並べたものはどれか。

次の問題 →

ハッシュ表のサイズ m=7 とし、ハッシュ関数を h(k) = k mod 7 で定義する。キー集合 {15, 22, 8, 36, 25} を順に挿入したとき、衝突が発生する組み合わせとして正しいものはどれか。

アルゴリズムとプログラミングの問題を解くこの分野の問題一覧を見る