過去問クラブ 学ぶ、わかる、つづく。
ログイン
用語解説

二分木

子が最大二つの木

二分木は、各節が最大で二つの子を持つ木構造です。二つの子を左の子、右の子として区別します。最上位を根、子を持たない節を葉と呼びます。式の構造、探索、優先度の管理などに関連しますが、二分木であるだけで値が大小順に並んでいるとは限りません。

探索木との違い

二分探索木は、左側に小さい値、右側に大きい値を置くなど、大小関係の規則を加えたものです。一般の二分木にはその条件はありません。また、ヒープも二分木の一種として実装できますが、親子間の大小関係と、左右全体の大小関係は別です。似た形の図でも、どの不変条件を持つかを確認します。

走査の順序

根を処理してから左右をたどるのが先行順、左をたどって根を処理し右へ進むのが中間順、左右をたどってから根を処理するのが後行順です。二分探索木を中間順でたどると、定めた規則に応じた整列順を得られます。一般の二分木を中間順にすれば必ず整列するわけではありません。

小さな例

        8
      /        3     10
    /    1   6

preorder : 8, 3, 1, 6, 10
inorder  : 1, 3, 6, 8, 10
postorder: 1, 6, 3, 10, 8

同じ木でも、節を処理するタイミングによって並びが変わります。再帰呼出しの前、間、後に出力があるプログラムと対応させると理解できます。

高さと性能

枝が均等に分かれる木と、片側だけにつながる木では、根から葉までの長さが大きく異なります。二分探索木だから常に対数時間で探せる、とは限りません。平衡を保つ仕組みの有無が重要です。試験では、節数、葉の数、高さの数え方の定義を確認し、根の深さを0とするか1とするかなどの前提をそろえて計算しましょう。

左右の子が欠けている節も二分木の条件を満たします。「最大二つ」と「必ず二つ」は異なるため、葉や片方だけ子を持つ節を除外しないようにします。

参考資料

内容確認日:2026-11-13

この言葉を含む問題を探す

この用語に関連する問題

2問

用語一覧

2件