木の走査

すべての節を1回ずつ訪れる

前回で木の呼び名がそろいました。今回は、木のすべての節を1回ずつ訪れて値を並べる操作を扱います。これを走査 (トラバーサル) と呼びます。列と違って木は枝分かれしているので、訪れる順番が一通りに決まりません。そこで、定番の3つの順番が用意されています。

違いは1点だけです。ある節にいるとき、その節自身をいつ出力するか、というタイミングだけが変わります。左の部分木を先に、右の部分木をその後に処理する点は3つとも共通です。

• 行きがけ順 (先行順) は、自分、左、右の順です
• 通りがけ順 (中間順) は、左、自分、右の順です
• 帰りがけ順 (後行順) は、左、右、自分の順です

擬似言語で書くと、出力する行の位置が上から下へずれていくだけだと分かります。

通りがけ順なら出力の行を2つの再帰呼出しの間に、帰りがけ順なら2つの後ろに置きます。前章の再帰そのままで、部分木もまた木だからこの短さで書けます。

実際に並べてみる

次の木で3通りを書き出します。

行きがけ順は、まず自分の A、次に左部分木 B、D、E、最後に右部分木 C、F をたどるので A B D E C F です。

通りがけ順は、左部分木を先に片付けます。B の左の D、B 自身、B の右の E で D B E、そのあと A、続いて右部分木は F、C の順なので D B E A F C です。

帰りがけ順は自分が最後です。D E B、F C、最後に A で D E B F C A となります。根がどこに現れるかを見れば、どの順で走査したかを見分けられます。行きがけ順なら先頭、帰りがけ順なら末尾、通りがけ順なら左部分木の節数のぶんだけ後ろです。

式と結び付ける

走査が試験で繰り返し問われるのは、計算式と対応するからです。演算子を内部節、値を葉に置いた木を考えます。

この木の通りがけ順は 3 + 4 × 2 で、普段書く中置記法です。帰りがけ順は 3 4 + 2 × となり、これが逆ポーランド記法 (後置記法) です。行きがけ順の × + 3 4 2 はポーランド記法 (前置記法) です。

逆ポーランド記法は括弧が要りません。左から読んで、値ならスタックに積み、演算子なら上から 2 つ取り出して計算し結果を積み直す、という手順でそのまま計算できます。ここで最初のレッスンのスタックが再び出てきます。式の変換問題が出たら、まず木を描いて、どの走査かを当てはめるのが確実です。

もう1つ覚えておきたいのが、二分探索木を通りがけ順で走査すると値が小さい順に並ぶ、という性質です。左の子は自分より小さく、右の子は自分より大きいという規則と、左、自分、右という順番がそのまま対応するためです。