BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
二分木
子が最大二つの木
二分木は、各節が最大で二つの子を持つ木構造です。二つの子を左の子、右の子として区別します。最上位を根、子を持たない節を葉と呼びます。式の構造、探索、優先度の管理などに関連しますが、二分木であるだけで値が大小順に並んでいるとは限りません。
探索木との違い
二分探索木は、左側に小さい値、右側に大きい値を置くなど、大小関係の規則を加えたものです。一般の二分木にはその条件はありません。また、ヒープも二分木の一種として実装できますが、親子間の大小関係と、左右全体の大小関係は別です。似た形の図でも、どの不変条件を持つかを確認します。
走査の順序
根を処理してから左右をたどるのが先行順、左をたどって根を処理し右へ進むのが中間順、左右をたどってから根を処理するのが後行順です。二分探索木を中間順でたどると、定めた規則に応じた整列順を得られます。一般の二分木を中間順にすれば必ず整列するわけではありません。
小さな例
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