基本情報技術者試験「木構造」の問題
次の 2 分木がある。各ノードは値・左の子・右の子をもつ（子がなければ空）。
根=500、500 の左の子=300、500 の右の子=800、300 の左の子=200、300 の右の子=400、800 の右の子=900（800 の左の子は空、200・400・900 の子はすべて空）。
この木に対し次の擬似言語（中順走査：左部分木→節点→右部分木の順に値を出力）を根から実行したとき、出力される値の並びはどれか。
○手続: inorder(ノード: n)
if (n が 空)
return
endif
inorder(n.左)
nの値を出力
inorder(n.右)ア200 300 400 500 800 900
ウ200 300 400 300 500 800 900
イ200 400 300 900 800 500
エ昇順の200から900
正解
ア．200 300 400 500 800 900
中順では左部分木をすべて出力してから節点、最後に右部分木を出力する。この木は左<節点<右の関係を満たすため出力は昇順 200 300 400 500 800 900 となり アが正しい。
?選択肢ごとの解説
ア ○中順では左部分木をすべて出力してから節点、最後に右部分木を出力する。この木は左<節点<右の関係を満たすため出力は昇順 200 300 400 500 800 900 となり アが正しい。
ウ ×節点 300 を左部分木の前後で 2 回出力して 200 300 400 300 500 800 900 とした、各節点を一度だけ出力する原則を破った誤りである。
イ ×後順走査（左→右→節点）の結果 200 400 300 900 800 500 であり、節点を最後に出力した誤りである。
エ ×昇順になること自体は正しいが具体的な並びを示さず『昇順の200から900』と言葉で濁した、出力列を明示していない不適切な解答である。
✎くわしく
中順走査を 2 分探索木に適用すると常に昇順列が得られる。これは中順が『左部分木（小さい値群）→節点→右部分木（大きい値群）』を順に出すためである。
✓本番での押さえどころ
試験のコツ
中順は『最も左下のノードが先頭』を手掛かりに、左を出し切ってから節点へ戻る。
覚え方
中順=『左・自分・右』の真ん中で自分、と唱える。探索木なら昇順と覚える。
よくある誤り
前順と中順を混同し、根が先頭に来る並びを選ぶミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0115