科目Bの二分木問題の解き方｜節点をたどる順番を解説

二分木の問題、図は描けるのに答えが合わない。

節点をたどっているうちに、どこまで進んだか分からなくなっていませんか？

科目Bの二分木問題は、木の形を覚える問題ではありません。与えられたコードを動かしたときに、節点がどの順番で処理されるかを答える問題です。

だから、図を眺めているだけでは解けません。手を動かして順番を書き出す作業が必要になります。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。画面のメニュー構造やフォルダの階層など、実務でも木の形をしたデータは毎日のように扱います。

そういうデータを処理するコードは、たいてい自分自身を呼び出す形で書かれます。現場でも、呼び出しの順番を紙に書かずに読むと必ずどこかで間違えます。

この記事では、二分木の設問をたどる順番の作業に落とし込む手順をお伝えします。科目B全体の姿をまだつかめていない人は、親記事から読むと位置づけがはっきりします。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

この設問は何を聞いているのか¶

まず、出題の意図を押さえておきましょう。ここがずれると、覚える方向を間違えます。

二分木が出てくる問題で問われるのは、木構造の定義ではありません。コードが節点をどの順にたどり、何をどの順に出力するかです。

言いかえると、暗記ではなく作業です。順番を書き出す手順さえ持っていれば、必ず答えにたどり着けます。

押さえる用語は3つだけ¶

覚えるべき用語は多くありません。たどる順番の名前が3つあるだけです。

表の右端は、このあと使う木で実際にたどった結果です。同じ木でも、処理する位置を変えるだけで結果が変わります。

大事なのは名前の暗記ではなく、コードのどこに出力の行が置かれているかを見ることです。そこだけ見れば、どの順番か判断できます。

木構造そのものの用語や表し方に不安が残る人は、先に文法側を固めておくと読みやすくなります。

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

図が描ければ半分は終わり¶

問題文には、木が配列で与えられることがよくあります。そのままでは形が見えません。

最初にやるのは、配列から木の絵を起こす作業です。ここさえ済めば、あとは順番をたどるだけになります。

私も複雑な階層データを扱うときは、必ず紙に形を描いてからコードを読みます。頭の中だけで形を保つのは、思っているより難しいからです。

まず目を付ける3か所¶

問題用紙を開いたら、1行目から読み始めないでください。先に見る場所を決めておくと、読む時間が短くなります。

見るのは次の3か所です。順番にも意味があるので、この並びで確認してください。

この3つが分かれば、細かい条件式は後回しにできます。全部を読もうとしないのが、時間を守るコツです。

配列で表された木を図に戻す¶

木が配列で与えられるとき、たいてい左の子と右の子の番号が別々の配列に入っています。値が0や-1なら子がない、という約束が問題文に書かれています。

読み方は単純です。根の番号から始めて、左と右の番号を順にたどり、枝を描き足していきます。

今回の記事では、次の形の木を例にします。根がA、その左にB、右にCがあり、Bの下にDとEがぶら下がっている形です。

配列の中身を表にすると、形が一気に見えるようになります。問題を解くときも、まずこの表を書くのがおすすめです。

この表があれば、コードを読みながら配列を何度も見返さずに済みます。書き写す手間は1分もかかりません。

再帰か、ループかを見分ける¶

二分木のコードは、自分自身を呼び出す形で書かれることが多いです。手続の中に同じ手続の名前が出てきたら、それが目印になります。

再帰の形だと分かったら、読み方も決まります。呼び出しが始まった順と、戻ってきた順を分けて追うことになるからです。

再帰そのものでつまずいている人は、先に呼び出しの追い方だけを練習しておくと楽になります。

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

トレース表で呼び出しを追ってみる¶

ここからは実際に手を動かします。試験の書き方に合わせた自作のコードを用意しました。

節点は番号で管理し、左右の子の番号を配列で持たせています。子がない場合は0を入れる約束です。

○大域: 文字型の配列: node ← {"A", "B", "C", "D", "E"}
○大域: 整数型の配列: left ← {2, 4, 0, 0, 0}
○大域: 整数型の配列: right ← {3, 5, 0, 0, 0}

○tour(整数型: p)
  if (p が 0 と等しい)
    return
  endif
  tour(left[p])
  node[p] を出力する
  tour(right[p])

出力の行が、左へもぐる処理と右へもぐる処理の間に置かれています。ここから、これは通りがけ順だと判断できます。

では tour(1) を呼んだときの動きを、呼び出しの順に書き出してみましょう。段の深さも一緒に書くのがコツです。

出力を順に並べると、D、B、E、A、C になります。表の右端を上から読むだけで答えが出ました。

段の深さを必ず書く¶

再帰のトレースで迷う原因は、ほとんどが戻る先を見失うことです。段の深さを書いておけば、戻る場所が一目で分かります。

紙の上では、段の数だけ右にずらして書くのがおすすめです。形がそのまま木の形になるので、見返したときに間違いに気づけます。

トレース表の書き方そのものをまだ決めていない人は、型を先に用意しておくと速くなります。

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

戻ってきたあとの行を飛ばさない¶

再帰のトレースでいちばん多い抜けは、呼び出しから戻ったあとの処理を忘れることです。戻った先には、まだ実行していない行が残っています。

例のコードでいえば、左の呼び出しから戻ったあとに出力の行があります。ここを飛ばすと、出力される節点が1つ足りなくなります。

表に書くときは、呼び出す行と戻った行をそれぞれ1行として扱ってください。手間は増えますが、抜けが起きなくなります。

手続の呼び出しと戻り値の扱いがあいまいな人は、文法の側を確かめておくと安心です。

【関連記事】擬似言語の手続と関数の違いとは？引数・戻り値と変数の有効範囲を解説

間違いやすい選択肢の見分け方¶

選択肢は、あえて似た並びが用意されています。どれも見覚えのある順番に見えるので、勘で選ぶと外します。

よくあるひっかけを整理しました。答えを出したあと、この表で確かめてください。

3つ目と4つ目は、自分のトレースが崩れたときに出やすい答えです。出力した順に書き出していれば防げます。

出力の行の位置だけ二度見る¶

時間がないときでも、ここだけは確認してください。出力の行が再帰の前か、間か、後ろかです。

この位置を読み違えると、正しくトレースしても答えが変わります。二分木の設問で落とす原因の多くは、ここにあります。

解き方の手順そのものを整えたい人は、科目B全体に通じる読み方をまとめた記事があります。

【関連記事】基本情報 科目Bの問題はどう解く？問題文から答えを出すまでの手順

二分木は試験のためだけの構造ではない¶

ここで少しだけ、実務の話をしておきます。二分木は、現場のシステムでも形を変えて出てきます。

身近なところでは、フォルダの階層や画面のメニューが木の形をしています。親の下に子がぶら下がる構造は、どこにでもあるものです。

データベースの索引にも木構造が使われています。目的のデータへ少ない回数でたどり着ける仕組みが必要だからです。

片側に偏った木が遅くなる理由¶

左右に均等に広がった木なら、根から葉まで短い段数でたどり着けます。段が浅いほど、探す回数が少なくて済みます。

ところが、右にばかり枝が伸びた木は形が一列になります。そうなると、先頭から順に見ていくのと変わらなくなってしまいます。

科目Bでこの話が直接問われることは多くありません。それでも、形によって速さが変わると知っておくと、選択肢の判断が速くなります。

私も検索が遅いという相談を受けたとき、索引の形を確認するところから始めます。原因がデータの並び方にあることは珍しくありません。

シミュレーターで動かして確かめる¶

紙のトレースだけで終わらせると、合っているかどうかを確かめる手段がありません。答え合わせの場所を持っておきましょう。

Giji Academy の擬似言語シミュレーターなら、コードを1行ずつ実行して変数の値が変わる様子を画面で追えます。自分で書いた表と並べれば、ずれた行がその場で見つかります。

擬似言語シミュレーターで節点をたどってみる

無料で使えるので、さきほどのコードをそのまま試してみてください。出力の行を1つ上に動かすと、結果が行きがけ順に変わることも確かめられます。

木の形を変えて解き直す¶

一度解いた問題は、配列の中身を変えるだけでもう一度使えます。右に偏った木、節点が1つだけの木などが良い練習になります。

節点が1つだけの木は、とくに試す価値があります。どのたどり方でも結果が同じになるので、自分の理解の確認に使えるからです。

同じように節点をたどる問題として、連結リストの設問も近い考え方で解けます。あわせて練習しておくと定着が早くなります。

【関連記事】科目Bの連結リスト問題の解き方｜nextを図にして追う

まとめ¶

科目Bの二分木問題は、覚える量がとても少ない分野です。たどる順番を表で追えれば、それだけで正解にたどり着けます。

今日お伝えした手順を振り返っておきましょう。

この5段階は、再帰を使うほかの設問にもそのまま使えます。読む場所を決めて、表で追って、選択肢を疑う。やることは毎回同じです。

最初は段を書き足すのが面倒に感じるかもしれません。それでも3問も書けば、手が自然に動くようになります。

まずは今日、さきほどのコードを自分の手で追ってみてください。DBEAC と書けたなら、この分野はもう取れる分野です。