スタックと木・逆ポーランド 想定問題 3

登録順から二分探索木を作り，先行順でたどった並びを求める問題です。

先行順は「節 → 左 → 右」で，自分を先に書きます。

• 木を作る：50 が根。30 は左，70 は右
• 木を作る（続き）：20 は 30 の左，40 は 30 の右。60 は 70 の左，80 は 70 の右
• 35 は 50 → 30 → 40 と進み，40 の左
• 節（左，右）の形で書くと 50（30（20，40（35，−）），70（60，80））
• 先行順：50 → 左の部分木 30 → 20 → 40 → 35 → 右の部分木 70 → 60 → 80
• 並べると 50，30，20，40，35，70，60，80。答えは ⑤

①：中間順（左 → 節 → 右）の並びで，キーが小さい順になっています。

②：後行順（左 → 右 → 節）の並びで，根の 50 が最後に来ています。

④：35 を最後に置いています。35 は 40 の左の子なので，先行順では 40 のすぐ後，70 より前に来ます。

• 木のたどり方：先行順（節 → 左 → 右），中間順（左 → 節 → 右），後行順（左 → 右 → 節）（テキスト・覚えること）
• 二分探索木を中間順でたどると，キーが小さい順に並ぶ（テキスト・覚えること）
• 二分探索木は，登録順に1つずつ根から置き場所をたどって木を書き，それから先行順などでたどる（テキスト・解き方）
• 登録順をそのまま並べた選択肢や，中間順・後行順の並びがまぎれている（テキスト・ひっかけ）