擬似言語の木構造（二分木）がわからない人へ｜節点のたどり方と走査の読み方を解説

木構造の問題になると、図とコードが頭の中でつながらない。

枝分かれした図を見て、どこから読み始めればいいのか迷っていませんか？

配列や繰返しは追えるようになったのに、木が出たとたんに手が止まる。そういう相談を受けることが増えました。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。商品カテゴリの親子関係をたどる処理で、階層の深さを一つ数え間違えて表示が崩れた不具合を直したこともあります。

木構造は、図で見ると難しそうに映ります。でも仕組みそのものは、親と子という関係が繰り返されているだけです。

この記事では、木構造を科目Bで読み解くために必要なところだけを、順番に見ていきます。

木構造は枝分かれしていくデータの並べ方¶

まず、木がどういう形なのかを押さえましょう。ひとつのデータから、下に向かって枝分かれしていく並べ方のことです。

配列が一列に並んだ形だとすれば、木は上から下へ広がっていく形になります。会社の組織図や、パソコンのフォルダの入れ子を思い浮かべてもらうと近いです。

そして木の中でも、科目Bでよく出るのが二分木です。ひとつのデータから伸びる枝が、多くても二本までに限られている木を指します。

枝が二本までと決まっていると、処理の書き方も自然に決まってきます。だから試験でも扱いやすく、出題の中心になっているわけです。

用語は最小限だけ覚えれば足りる¶

木構造の説明には、聞き慣れない言葉が並びます。ただ、科目Bを読むために必要なものは多くありません。

問題文を読むときに困らない範囲で、最低限を表にまとめます。

この五つが分かれば、問題文の意味は取れます。深さや高さといった言葉も出てきますが、根から何段目かを表しているだけです。

とくに大事なのが部分木という考え方になります。木の途中を切り出しても、やはり木の形をしている。この性質が、後で出てくる処理の書き方につながります。

配列や連結リストとどう違うのか¶

すでに配列や連結リストを学んだ人は、それらとの違いが気になるところだと思います。つながり方の自由度が違う、というのが答えになります。

三つを並べて比べてみましょう。

連結リストは進む先がひとつしかないので、迷う余地がありません。ところが二分木では、左に行くか右に行くかを毎回決めることになります。

この分かれ道こそが、木構造の問題の中心です。どちらへ進むかを決める条件を読み取れれば、処理はほとんど追えたようなものです。

参照でつなぐという考え方そのものに不安がある場合は、先に連結リストを確認しておくと理解が早くなります。

【関連記事】擬似言語のリスト（連結リスト）がわからない人へ｜ノードと参照のたどり方を解説

二分木を擬似言語でどう表すか¶

図で描かれた木を、コードではどう表しているのか。ここがつながらないと、問題文の図とコードが別物に見えてしまいます。

表し方は大きく二つあります。節点ごとに左右の参照を持たせる方法と、配列にまとめて入れてしまう方法です。

科目Bの問題では、後者の配列で表す形がよく登場します。仕組みが単純で、添字の計算だけで親子をたどれるからです。

添字の2倍が左の子になる¶

配列で二分木を表すときは、置く場所にきまりがあります。根を1番目に置き、そこから上の段から順に、左から詰めていきます。

このきまりに従うと、親子の関係が計算で求められるようになります。

左の子が2倍、右の子はそれに1を足すだけ。この二つを覚えておけば、木の上を自由に動けます。

実際の並びで確かめてみましょう。次の配列は、根が50で、その左に30、右に70がぶら下がった木を表しています。

○整数型の配列: tree ← {50, 30, 70, 20, 40, 60, 80}

/* tree[1] = 50 が根
   tree[2] = 30 が左の子、tree[3] = 70 が右の子
   tree[4] = 20 と tree[5] = 40 は 30 の子
   tree[6] = 60 と tree[7] = 80 は 70 の子 */

30の左の子を知りたければ、2に2を掛けて4番目を見ます。中身は20です。

70の右の子なら、3に2を掛けて1を足した7番目で、80になります。図をたどらなくても、計算だけで答えが出る点が便利なところです。

添字の扱いそのものがあやしいと感じたら、土台を固めておくと安心です。

【関連記事】擬似言語の配列と添字がわからない人へ｜要素数・二次元配列の読み方を解説

左が小さく右が大きい木もある¶

さきほどの配列をよく見ると、あるきまりに気づくかもしれません。どの節点も、左の子が自分より小さく、右の子が自分より大きくなっています。

この並べ方をした二分木を、二分探索木と呼びます。探すときに強さを発揮する形です。

なぜ強いのか。探したい値と今の節点を比べるだけで、進む方向が決まるからです。

小さければ左、大きければ右。それだけで、見なくていい側をまるごと切り捨てられます。

二分探索木の中を探す処理を読む¶

では、実際に値を探す処理を見てみましょう。根から始めて、比べながら下りていくだけの短いコードです。

○整数型の配列: tree ← {50, 30, 70, 20, 40, 60, 80}
○整数型: i, x

x ← 60                                    /* 探したい値 */
i ← 1                                     /* 根から始める */
while (i が tree の要素数 以下 かつ tree[i] が x と等しくない)
  if (x が tree[i] より小さい)
    i ← i × 2                             /* 左の子へ下りる */
  else
    i ← i × 2 + 1                         /* 右の子へ下りる */
  endif
endwhile

繰返しの条件が二つ並んでいる点に注目してください。範囲の外に出ていないこと、そしてまだ見つかっていないこと。この二つが同時に成り立つ間だけ、下り続けます。

値の動きを表で追ってみます。

たった3回の比較で見つかりました。7個の中から探しているのに、半分以下しか見ていません。

見なくていい側を捨てながら進むという発想は、配列に対する二分探索とまったく同じです。木の形になっているだけで、考え方は共通しています。

【関連記事】擬似言語の線形探索と二分探索の違いとは？科目Bで差がつく探索の読み方

こうした表を書く手順に不安がある人は、専用の記事にまとめてあります。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

木を全部たどる走査の三つの順番¶

探すのではなく、木の中の全部の節点を一度ずつ訪れたい場合もあります。この動きを走査と呼びます。

一列に並んだ配列なら、先頭から順に見るだけでした。ところが木は枝分かれしているので、訪れる順番に何通りかの選び方が生まれます。

代表的なのが三つの順番です。自分自身をいつ処理するかだけが違います。

左を先に見て、右を後に見る。この点は三つとも共通しています。

違うのは、自分の値を出すタイミングだけです。最初か、間か、最後か。ここだけを見分ければ、名前は自然と決まります。

通りがけ順の結果を見てください。20から80まで、きれいに小さい順に並んでいます。

これは偶然ではありません。二分探索木を通りがけ順でたどると、必ず昇順で取り出せるという性質があります。

走査の処理は自分自身を呼び出す¶

走査を擬似言語で書くと、少し変わった形になります。手続の中で、その手続自身を呼び出すのです。

行きがけ順の例を見てみましょう。

○junkai(整数型: i)
  if (i が tree の要素数 より大きい)
    return                    /* 節点が無ければ何もしない */
  endif
  tree[i] を表示する          /* 先に自分を処理する */
  junkai(i × 2)               /* 左の部分木へ */
  junkai(i × 2 + 1)           /* 右の部分木へ */

自分を呼ぶという書き方が、最初は不思議に見えるかもしれません。ただ、これは部分木もまた木である、という性質をそのまま書いただけです。

左の子から下は、それ自体がひとつの木になっています。だから同じ手続をそのまま使えるわけです。

そして、表示する行を動かすだけで走査の種類が変わります。二つの呼び出しの間に置けば通りがけ順、後ろに置けば帰りがけ順になります。

呼び出しの形は変えず、一行の位置だけを変える。この対応が見えると、三つの走査は覚えるものではなく読み取るものになります。

自分自身を呼び出す処理そのものが苦手な場合は、こちらもあわせてどうぞ。

【関連記事】基本情報科目Bの再帰呼び出しがわからない人への対策方法を解説｜擬似言語で処理を追うコツ

呼び出しの途中経過はどこに残るのか¶

走査を追っていると、ひとつ疑問がわいてきます。左へ下りていったあと、どうやって元の場所へ戻ってこられるのでしょうか。

答えは、呼び出しの記録が積み上がっているからです。呼び出すたびに戻り先が積まれ、終わるたびに上から取り出されます。

この積み上げ方は、スタックそのものです。最後に積んだものから先に取り出される、あの動きになります。

木の走査とスタックが裏でつながっていると分かると、両方の理解が一段深まります。

【関連記事】擬似言語のスタックとキューの違いとは？科目Bで出る出し入れの順番を解説

科目Bでつまずきやすい場所¶

ここまでの仕組みが分かっていても、本番で失点しやすい箇所は決まっています。私が学習の相談を受けてきた範囲では、次の三つが目立ちました。

先に知っておけば避けられるものばかりなので、表で確認しましょう。

どれも知識としては簡単です。それでも、図とコードを行き来しながら急いで読むと、こういうところで足をすくわれます。

とくに三つ目は見落とされがちです。子がいない節点まで下りたときに処理を止める条件が、必ずどこかに書かれています。

空欄補充では進む方向と止まる条件を見る¶

木構造の問題で空欄になりやすいのは、進む方向を決める行か、止まる条件の行です。この二つに狙いを定めるだけで、探す時間が減ります。

空欄が if の中にあれば、左右どちらへ進むかを問われています。比べている値の大小関係から逆算してください。

空欄が繰返しの条件や return のそばにあれば、いつ止まるかを問われています。範囲の外に出る場合と、目的の値に届いた場合の二つを思い出しましょう。

判断に迷ったら、節点が三つだけの小さな木を紙に書いて当てはめてみてください。それだけで、選択肢のほとんどはふるい落とせます。

【関連記事】基本情報技術者試験の科目Bの空欄補充問題の解き方を解説｜擬似言語で見る判断ポイント

図は自分で描き直すほうが速い¶

問題文に木の図が載っていても、そのまま使わないほうがうまくいく場合があります。配列で与えられているなら、自分で図を描き直すのがおすすめです。

根から順に、1番目、2番目と番号を振りながら描きます。番号が振ってあると、コードの添字と図がそのまま結びつきます。

手を動かす時間は30秒ほどです。その30秒で、たどる先を間違える事故がほとんど防げます。

手を動かして確かめるのが一番の近道¶

木構造は、読むだけでは身につきにくい分野です。枝を下りていく感覚は、実際に追ってはじめて腑に落ちます。

まずは節点が七つほどの小さな木で、三つの走査を紙に書いて出力してみてください。数分で終わりますし、一度やれば順番の違いが体に残ります。

そのうえで、コードを一行ずつ動かして確かめられるとさらに理解が速くなります。Giji Academy の擬似言語シミュレーターなら、変数の値が変わっていく様子を見ながら処理を追えます。

使い方から知りたい人は、次の記事に手順をまとめてあります。

【関連記事】擬似言語 シミュレーターとは？試験対策に役立つ使い方と学習法を解説

まとめ¶

最後に、この記事で確認したことを振り返ります。

木構造は、親と子という関係が繰り返された並べ方でした。枝が二本までのものが二分木で、科目Bの出題はここが中心になります。

配列で二分木を表すときは、添字の2倍が左の子、それに1を足したものが右の子でした。この計算だけで、木の上を自由に動けます。

二分探索木では、値を比べて進む方向が決まります。小さければ左、大きければ右と進むだけで、見なくていい側を大きく捨てられました。

走査には三つの順番があり、違いは自分を処理するタイミングだけでした。通りがけ順で二分探索木をたどると、必ず昇順で並ぶという性質も押さえておきたいところです。

そして最大のつまずきどころは、進む方向と止まる条件でした。空欄補充でもここが狙われるので、if の中と終了条件を意識して読む癖をつけてください。

木が読めるようになると、科目Bで手が出る問題は確実に増えます。今日の一問から、小さな木を描いて追いかけてみましょう。