問題
二分探索木において、ノード値の集合{50, 30, 70, 20, 40, 60, 80}をこの順に挿入した。ルートから値40に到達するために訪問するノードの順序はどれか。
選択肢
- 1ア 50 → 30 → 40
- 2イ 50 → 70 → 40
- 3ウ 50 → 40
- 4エ 30 → 50 → 40
解答と解説を見る
正解
1. ア 50 → 30 → 40
解説
二分探索木では、左の子 < 親 < 右の子の関係があります。挿入順により：ルートは50、30は50の左、70は50の右、20は30の左、40は30の右、60は70の左、80は70の右。40を探索すると50→30（40<50なので左）→40（40>30なので右）で到達。