データ構造とアルゴリズム
空の二分探索木に、50, 30, 70, 20, 40, 60, 80 の順に値を挿入した。この木を後行順(帰りがけ順。左の部分木、右の部分木、その節の順に訪れる)でたどったときの順はどれか。
- A50, 30, 20, 40, 70, 60, 80
- B20, 40, 30, 60, 80, 70, 50
- C20, 30, 40, 50, 60, 70, 80
答えと解説を見る
正解：B. 20, 40, 30, 60, 80, 70, 50
根は50で、左の子は30(その子が20と40)、右の子は70(その子が60と80)になります。後行順では、左の部分木の 20, 40, 30、右の部分木の 60, 80, 70 を訪れてから、最後に根の50を訪れます。50, 30, 20, 40, 70, 60, 80 は節を先に訪れる先行順(行きがけ順)、20, 30, 40, … は中間順(通りがけ順)の結果です。後行順は、子を先に処理する必要がある木の削除や、式の木から後置記法を作るときに使われます。
- A. 節を先に訪れる先行順(行きがけ順)の結果です。
- B. 正しい。左右の部分木を訪れてから節を訪れるので、根の50が最後になります。
- C. 中間順(通りがけ順)の結果で、値が昇順に並びます。