基本情報の木構造・二分木を攻略｜走査順と問題の解き方

基本情報で木構造や二分木が出てくると、急に図が増えて苦手に感じる人は多いです。配列やリストのように順番が見えやすいデータ構造と違って、親子関係、左右の子、走査順まで同時に追う必要があるからですね。

ただ、基本情報の木構造と二分木は、覚える範囲を広げすぎなければ得点源にできます。根、葉、部分木、二分探索木、前順・間順・後順の読み方を整理し、問題文を図に直す順番を決めておくことが大切です。

この記事では、基本情報の木構造と二分木を初めて学ぶ人向けに、用語の見方から走査順、科目Bでの解き方までを一つずつ整理します。

基本情報の木構造と二分木の基本

木構造でまず見る用語

木構造は、データ同士の上下関係を枝分かれの形で表すデータ構造です。基本情報で最初に押さえたいのは、木全体を暗記することではなく、図の中でどこが根で、どこが葉で、どこからどこまでが部分木なのかを見分けることです。根は一番上にある出発点、葉はそれ以上子を持たない末端、節点は丸や四角で描かれる一つ一つのデータ、辺は節点同士をつなぐ線だと考えると読みやすくなります。

試験では、用語そのものを問うよりも、図や説明文から条件に合う節点を選ばせる形で出ることがあります。たとえば「ある節点を根とする部分木」と言われたら、その節点から下につながる範囲だけを切り出して見る必要があります。逆に、親や祖先を聞かれたときは、対象の節点から上へたどります。上下と左右を同時に追うと混乱するので、まず対象の節点を丸で囲み、次に上方向か下方向かを決めるのが安全です。

木構造の用語は、文章だけで覚えるより図の中で位置を確認した方が定着します。根、親、子、兄弟、葉、部分木を一枚の図に書き込める状態が目標です。

用語	見る場所	試験での使われ方
根	木の最上位	探索や走査の開始点になりやすい
葉	子を持たない末端	処理の終了条件として出やすい
親と子	辺で直接つながる上下関係	配列添字やポインタの追跡で使う
部分木	ある節点から下のまとまり	再帰処理の対象範囲になる

この用語整理は、科目Aだけでなく科目Bにも効きます。科目Bでは擬似言語の中に「左の子」「右の子」「子を持たないなら」といった条件が出てくることがあり、用語を知らないと処理の分岐を読み間違えます。図の中の用語が読めるようになると、プログラムの変数がどの節点を指しているのかも追いやすくなります。

二分木と木構造の違い

二分木は木構造の一種で、各節点が持てる子の数が最大2つまでの木です。ここで大事なのは、「必ず2つの子を持つ」という意味ではないことです。子が0個なら葉、1個だけなら片側だけに子がある節点、2個なら左の子と右の子を持つ節点として扱います。基本情報では、この「最大2つ」という条件を読み落とすと、完全二分木や二分探索木の問題で混乱しやすくなります。

木構造はもっと広い言葉で、子の数が2つに限られないものも含みます。会社組織図、フォルダ階層、メニュー階層のように、一つの親から複数の子へ分かれる構造は広い意味で木構造です。その中で、アルゴリズムや探索の説明に使いやすいように左右2方向に絞ったものが二分木だと考えると理解しやすいですね。

また、二分木は左右の位置に意味があることもポイントです。単に子が2つあるだけでなく、左部分木と右部分木を区別します。特に二分探索木では、左側には小さい値、右側には大きい値が入るという条件が関係します。左右を入れ替えても同じだと思ってしまうと、探索順や走査結果が変わるので注意が必要です。

• 木構造は親子関係を表す広い言葉
• 二分木は各節点の子が最大2つまで
• 子が1つだけの節点があっても二分木
• 左右の子を区別する問題では位置に意味がある

基本情報の問題では、二分木という言葉だけで難しく考えすぎる必要はありません。最初は「親から左と右に分かれる図」くらいに置き換え、そこに探索や走査のルールが乗ると考えるのが実用的です。図を見て二分木かどうかを判断できれば、その後の条件整理に進めます。

二分探索木の条件

二分探索木は、二分木に「値の大小関係」というルールを加えたものです。基本は、ある節点を見たときに、左部分木にはその節点より小さい値、右部分木にはその節点より大きい値が入るという考え方です。問題によっては同じ値をどちら側に置くかが指定される場合もありますが、基本情報レベルではまず「左は小さい、右は大きい」を使って判断できることが多いです。

この条件は、根だけに当てはめればよいわけではありません。根の左側にある部分木の中でも、その部分木の根を基準にして左は小さく右は大きくなります。右側の部分木でも同じです。つまり、どの節点を基準にしても同じルールが成り立つ必要があります。根だけ見て正しそうでも、途中の節点で大小関係が崩れていれば二分探索木ではありません。判断に迷う節点があれば、その節点だけを小さな根として見直すと崩れを見つけやすいです。

二分探索木の確認では、対象の値が根より小さいか大きいかを見たあと、移動先の部分木でも同じ判断を繰り返します。検索対象を半分ずつ絞る感覚で追うと、選択肢を消しやすくなります。

見る条件	判断	注意点
左部分木	基準の節点より小さい値	左側全体が条件を満たすか見る
右部分木	基準の節点より大きい値	右側全体が条件を満たすか見る
各部分木	同じ大小ルールを繰り返す	根だけで判断しない

二分探索木は、探索アルゴリズムの記事で扱う二分探索とも名前が似ています。二分探索は整列済み配列を半分に割って探す方法で、二分探索木は木構造の形を使って探す方法です。探索の考え方は似ていますが、対象になるデータ構造が違います。配列の添字を追う問題なのか、節点と左右の子を追う問題なのかを最初に分けると混同しにくいです。関連する探索の全体像は基本情報の探索アルゴリズムでも整理しています。

完全二分木の考え方

完全二分木は、上の段から順番に節点が詰まり、最後の段も左から順に埋まっている二分木です。基本情報では、ヒープや配列で木を表す話と一緒に出ることがあります。図として見ると単純ですが、文章だけで「上から」「左から」と言われると迷いやすいので、段ごとに横へ読んで確認するのがコツです。

完全二分木では、途中の段に穴が空いている形は基本的に認められません。たとえば、上から2段目に左の子がないのに右の子だけある、最後の段で右側だけ埋まっていて左側が空いている、といった形は完全二分木としては不自然です。試験では、複数の図から完全二分木を選ぶ問題や、配列の添字と親子関係を結びつける問題でこの考え方が使われます。

• 上の段から順に埋まる
• 同じ段では左から順に埋まる
• 途中の段に空きがある形は避ける
• 配列表現やヒープの理解につながる

配列で木を表す問題では、親と子の添字関係を問われることがあります。添字が1から始まる前提なら、ある位置の左の子は2倍、右の子は2倍して1を足す、親は2で割った商という関係が使われます。添字が0から始まる前提なら式が変わるため、問題文にどちらの前提が書かれているかを必ず確認してください。ここを読み飛ばすと、考え方は合っているのに選択肢を間違える原因になります。

完全二分木は、きれいな三角形かどうかではなく、上から左へ詰めて置いた結果になっているかで判断します。見た目のバランスより、空き位置の有無を優先して確認しましょう。

この考え方は、スタックやキューのような他のデータ構造と一緒に覚えると整理しやすいです。データをどの順序で取り出すか、どの位置関係で保持するかという視点を持つと、木構造だけが特別に難しいものではなくなります。データ構造の基礎を合わせて復習したい場合は、基本情報のスタックとキューも確認しておくと流れがつかみやすいです。

二分探索との混同に注意

二分木を学ぶときに一番混同しやすいのが、二分木、二分探索木、二分探索の三つです。名前が似ているため、どれも同じように感じますが、試験では別物として扱った方が安全です。二分木は木の形そのもの、二分探索木は大小関係を持つ二分木、二分探索は整列済み配列に対する探索方法です。問題文に「配列」「添字」「中央」と出てきたら二分探索寄り、「節点」「左の子」「右の子」と出てきたら木構造寄りに読むと切り分けやすくなります。

特に科目Bでは、擬似言語の変数名だけを見て判断しようとすると迷います。node、left、right のような言葉が出てくるなら二分木の処理である可能性が高いです。一方で、low、high、mid のような変数が出てくるなら、配列の範囲を半分に狭める二分探索の可能性があります。もちろん変数名は問題ごとに違いますが、処理対象が「節点」なのか「配列の範囲」なのかを見れば、かなり判断しやすくなります。問題文の冒頭でデータ構造を確定させるだけでも、後半の読み違いを減らせます。

用語	対象	見るポイント
二分木	木の形	子が最大2つまで
二分探索木	値を持つ木	左が小さく右が大きい
二分探索	整列済み配列	中央を見て範囲を半分にする

この違いを先に整理しておくと、問題を読んだときの入口で迷いません。基本情報の学習では、似た名前を一気に覚えようとするより、対象データと処理の流れをセットで覚える方が実戦的です。木なら節点をたどる、配列なら添字を動かす。この基準を持っておくだけでも、選択肢の読み間違いはかなり減らせます。

基本情報の木構造と二分木の解き方

問題文から図に直す

基本情報で木構造の問題を解くときは、最初に問題文を図に直すのが一番安定します。文章のまま「Aの左の子はB」「Bの右の子はC」と追い続けると、途中で親子関係を見失いやすいからです。紙に小さく丸を書き、根から順に左の子、右の子を置いていくと、条件の矛盾や見落としに気づきやすくなります。図はきれいである必要はありません。左右の位置と親子関係がわかれば十分です。

図に直すときは、先に根を決めます。根が明示されていない場合は、親を持たない節点を探します。次に、各節点の左の子と右の子を置きます。二分探索木なら、値の大小関係も同時に確認します。最後に、問題が聞いているものが走査順なのか、探索回数なのか、条件を満たす節点なのかを確認します。この順番を固定すると、毎回考えることが減ります。解答欄に向かう前に小さな図を一つ作るだけで、読み直しの回数も減らせます。

図に直す作業は時間がかかるように見えますが、実際には読み直しを減らせます。特に科目Bでは、プログラムの途中で現在の節点が移動することがあります。最初に図を用意しておくと、変数が指している節点を鉛筆でなぞるだけで済みます。暗算で追うよりミスが少なく、見直しもしやすいですね。

木構造の問題は、問題文を読みながら完璧な図を作ろうとしなくて大丈夫です。根、左右、葉の位置だけを先に置き、必要な条件をあとから書き足す方が速く解けます。

前順・間順・後順を区別

二分木の走査順でよく出るのが、前順、間順、後順です。この三つは名前を丸暗記するより、「根をいつ読むか」で区別すると一気に楽になります。前順は根を先に読む、間順は左部分木と右部分木の間で根を読む、後順は根を最後に読む、という考え方です。つまり、根の位置だけに注目すれば、名前と処理順が結びつきます。

前順は「根、左、右」、間順は「左、根、右」、後順は「左、右、根」です。ここで注意したいのは、左や右と書いてある部分も、単なる一つの節点ではなく部分木として同じルールで読まれることです。左部分木に複数の節点があるなら、その中でも前順、間順、後順のルールを再帰的に使います。最初は面倒に感じますが、小さな部分木に分けて読むと安定します。

走査	読む順番	覚え方
前順	根、左、右	根を前に読む
間順	左、根、右	根を間に読む
後順	左、右、根	根を後に読む

間順は二分探索木と相性がよく、左、根、右の順に読むと値が小さい順に並びます。これはよく使われる性質です。ただし、これは二分探索木の条件が成り立つ場合の話です。ただの二分木を間順で読んでも、必ず昇順になるわけではありません。問題文に「二分探索木」と書かれているか、「左の子孫は小さく右の子孫は大きい」といった条件があるかを確認しましょう。

走査順で迷ったら、根に印を付けて「根を前に読むか、間に読むか、後に読むか」だけを先に決めます。次に左部分木、最後に右部分木へ同じルールを適用します。

基本情報の選択肢では、最初の数個だけ見れば消せることもあります。前順なら最初に根が来るはずです。後順なら最後に根が来るはずです。間順なら、左部分木を読み終えてから根が出ます。すべてを最後まで丁寧に並べる前に、根の位置だけで明らかに違う選択肢を消すと、時間を節約できます。

幅優先と深さ優先の見方

木構造の探索では、幅優先と深さ優先という見方も出てきます。幅優先は、根から近い段を横方向に順番に見ていく方法です。上の段から順に、同じ段では左から右へ読むイメージですね。深さ優先は、行けるところまで下へ進み、行き止まりになったら戻って別の枝をたどる方法です。前順、間順、後順は、この深さ優先の読み方に含めて考えると整理しやすくなります。

幅優先では、キューの考え方が使われます。根をキューに入れ、取り出した節点の子を順にキューへ追加していくと、近い段から順に処理できます。一方、深さ優先ではスタックや再帰の考え方が関係します。現在の節点から左へ進み、戻って右へ進むような処理は、呼び出しの積み重なりとして説明されることがあります。スタックとキューの違いを理解していると、木の探索もつながって見えてきます。

方法	進み方	関係する考え方
幅優先	近い段から横に読む	キュー
深さ優先	枝を奥までたどる	スタック、再帰
前順など	根の読む位置で変わる	深さ優先の一種

試験で幅優先と深さ優先を見分けるときは、最初の数ステップに注目します。根の次に同じ段の節点が続くなら幅優先の可能性が高いです。根の次に子、その次にさらに孫へ進んでいるなら深さ優先の可能性があります。すべてを一気に追わず、最初の移動だけで方向性をつかむと、選択肢の比較が楽になります。

幅優先は横に広がる探索、深さ優先は縦に潜る探索です。名前の印象だけで覚えるより、図の上でペンをどう動かすかを決めておくと忘れにくくなります。

この分野は単体で完璧にしようとするより、配列、リスト、スタック、キュー、再帰と合わせて学ぶ方が理解が深まります。木構造はそれらの知識を組み合わせる場面が多いからです。科目B全体の解き方を整理したい場合は、基本情報のアルゴリズム対策も合わせて見ておくと、どこまで練習すればよいか判断しやすくなります。

科目Bでの解く手順

科目Bで木構造や二分木が出た場合は、いきなりコード全体を読もうとしない方が安全です。まず、プログラムが扱っているデータが木なのか、配列で表した木なのか、ポインタのように節点同士をたどる形なのかを確認します。次に、変数がどの節点を指しているかを図に書き込みます。最後に、条件分岐や繰り返しによって、その変数がどこへ移動するかを一つずつ追います。

特に大切なのは、1回目のループで何が起きるかを丁寧に見ることです。木構造のプログラムは、同じ処理を節点を変えながら繰り返すことが多いです。1回目の動きがわかれば、2回目以降も同じ型で追えます。逆に、最初の移動を雑に読むと、途中から変数の位置がずれてしまい、選択肢が全部それらしく見えてしまいます。

科目Bでは、問題文が長くても、実際に問われているのは「条件を満たすまでどちらへ進むか」「何番目にどの節点を読むか」「処理後の木がどう変わるか」といった部分に絞られることが多いです。全部を完璧に理解しようとするより、設問に関係する変数と条件だけを拾う方が得点につながります。木構造に限らず、アルゴリズム問題ではこの読み方が重要です。

選択肢を見る前に、必ず自分で1〜2手だけトレースしましょう。選択肢から逆算すると、似た順序に引っ張られて根や左右の位置を読み間違えやすくなります。

基本情報の二分木まとめ

基本情報の木構造と二分木は、最初に覚える用語が多く見えますが、実際に試験で使う視点はかなり絞れます。まず、根、親、子、葉、部分木を図で見分けます。次に、二分木なら子が最大2つまで、二分探索木なら左が小さく右が大きいという条件を確認します。最後に、走査順では根を読む位置に注目します。この三段階で整理すれば、問題文が長くても入口で迷いにくくなります。

学習するときは、用語集を眺めるだけではなく、必ず小さな図を描いてください。3段くらいの二分木を自分で描き、前順、間順、後順で読んでみるだけでも理解が進みます。二分探索木なら、適当な値を一つ追加するときにどちらへ進むかを追う練習も有効です。慣れてきたら、配列で木を表す問題や、再帰で走査する擬似言語にも挑戦するとよいですね。短い問題で手順を固めてから長文問題に入ると、苦手意識も下げやすいです。

苦手な人ほど、いきなり難しい科目B問題に入るより、まず図を読む練習から始めた方が伸びやすいです。木構造の基本がわかると、探索、再帰、スタック、キューの理解にもつながります。二分木は単独の暗記項目ではなく、アルゴリズム全体を読みやすくする土台だと考えて学習していきましょう。

最後にもう一度だけ整理すると、二分木では「左右」、二分探索木では「大小」、走査順では「根の位置」を見ます。この三つを問題用紙の余白に書けるようになれば、基本情報の木構造と二分木はかなり扱いやすくなります。復習では一度に多くの木を扱わず、同じ図を何度も読み替える練習から始めましょう。