データ構造とアルゴリズム
二分探索木を中間順(通りがけ順。左の部分木、その節、右の部分木の順に訪れる)でたどったとき、訪れた節の値はどのように並ぶか。値はすべて異なるものとする。
- A昇順(小さい順)に並ぶ
- B木に挿入した順に並ぶ
- C根から近い順(浅い順)に並ぶ
答えと解説を見る
正解：A. 昇順(小さい順)に並ぶ
二分探索木では、どの節についても、左の部分木の値はすべてその節より小さく、右の部分木の値はすべて大きくなっています。そのため、左の部分木、節、右の部分木の順にたどると、小さい値から順に訪れることになり、結果は昇順になります。根から近い順に並ぶのは、段ごとに左から訪れる幅優先(レベル順)のたどり方です。挿入した順は木の形には残りますが、たどり方の順序とは一致しません。
- A. 正しい。左は小さく右は大きいという性質から、中間順では昇順に並びます。
- B. 挿入した順は木の形に影響しますが、中間順の結果は挿入順によらず昇順です。
- C. 段ごとに訪れる幅優先(レベル順)のたどり方の結果です。