木の巡回｜先行順・中間順・後行順のちがい【基本情報技術者試験 科目B】

現行FE シラバス Ver9.2 準拠擬似言語の記述形式は2022年から変更なし最終更新 2026-10-11

木の巡回とは、木の節を、決まった順番で1つ残らず1回ずつ訪ねることです。順番の決め方には先行順・中間順・後行順の3つがあり、プログラムの上でのちがいは、たった1行の位置だけです。サンプル問題には、巡回のプログラムが節番号をどの順に出力するかを答える出題があります。5つの節の小さな木で確かめます。

期間限定クーポンPR｜Udemy の講座科目B オリジナル模試 3回分・60問42%OFF 1,500円2,600円中身を見る ›

木の巡回とは ── すべての節を、1回ずつ訪ねる

下の図が、この回で使う木です。箱の1つ1つを節（せつ）といい、1 から 5 の節番号を付けてあります。線で下につながった節が子で、子は左の子と右の子を区別します。いちばん上の節1 が根、子のない節3・節4・節5 が葉です。このように、どの節も子が2つ以下の木を2分木といいます。

プログラムの中では、この木を配列 tree で持ちます。tree[n] は、節 n の子の節番号を、左の子・右の子の順に並べた配列です。子のない節は {}（要素数0の配列）になります。先頭の 大域: は、どの手続からもこの配列を使える、という印です。

大域: 整数型配列の配列: tree ← {{2, 3}, {4, 5}, {}, {}, {}}

もう1つ、言葉を用意します。ある節と、その下につながる節をまとめたものを、その節を根とする部分木といいます。節2 を根とする部分木は、節2・節4・節5 の3つです。節1 から見ると、これが左の部分木、節3 だけの部分木が右の部分木です。

巡回のプログラム ── 手続 order が、自分を呼ぶ

次の手続 order は、引数 n で受け取った節を根とする部分木をたどって、その節番号をすべて出力します。節を訪ねるたびにその節番号を1回出力するので、出力された順が、巡回の順です。

大域: 整数型配列の配列: tree ← {{2, 3}, {4, 5}, {}, {}, {}}

○order(整数型: n)
  if (tree[n]の要素数 が 2 と等しい)
    order(tree[n][1])
    nを出力
    order(tree[n][2])
  else
    nを出力
  endif

当サイトで作った例です。

order(1) を呼び出すと、4，2，5，1，3 の順に出力されます。

order の中で、order を呼んでいます。手続が自分自身を呼ぶこの書き方を再帰といいます（A8-1 再帰とは）。読み方は、ほかの手続を呼ぶときと変わりません。

order を呼んだ側は、その行で止まって待ちます。呼ばれた側が最後の行まで終わると、呼んだ側は次の行へ進みます。だから order(1) は、左の子で order(2) を呼んだ行で待ち続け、左の部分木の 4，2，5 が全部出てから、その次の行で自分の 1 を出力します。

n は、呼び出しごとに別のものです。order(2) の中の n が 2 でも、待っている order(1) の n は 1 のまま残っています。

先行順・中間順・後行順 ── 「nを出力」の位置で決まる

if の中の3行は、「左の子で order を呼ぶ」「nを出力」「右の子で order を呼ぶ」の3つでした。nを出力 を、2つの呼び出しの前に置くと先行順、あいだに置くと中間順、後ろに置くと後行順です。左を右より先に呼ぶところと、else の側は、3つとも変わりません。

nを出力
order(tree[n][1])
order(tree[n][2])

order(tree[n][1])
nを出力
order(tree[n][2])

order(tree[n][1])
order(tree[n][2])
nを出力

3つとも、左の部分木・根・右の部分木という3つのかたまりを、3行の並びと同じ順に置いたものになっています。かたまりの中の並びも、同じ決まりです。だから、プログラムを1行ずつ追わなくても、木の図からこの並びを書き出せます。

次に読む