ALDS1_7_B:

二分木

１つの根を持ち全ての節点についてその子の数が２以下である木を根付き二分木と言います。図1は二分木の例です。

図1 二分木の例

二分木では、節点が持つ子の数が２つ以下となりますが、左の子と右の子は区別されます。つまり、子が１つの場合はそれが左の子なのか右の子なのかが厳密に区別されます。 例えば、図1の二分木の例では、 (a) の節点3 は左の子として節点6 を持ちますが、一方(b) の節点3 は右の子として節点6を持っています。このように、子に順序性がある木を順序木と呼びます。

図2に示すように、二分木$T$ は再帰的に定義することができ、以下のいずれかの条件を満たす木です：

• $T$ は接点をまったくもたない。
• $T$ は共通要素をもたない次の３つの頂点集合から構成される：
  　- 根(root)
  　- 左部分木(left subtree) と呼ばれる二分木
  　- 右部分木(right subtree) と呼ばれる二分木
  

図2 二分木の部分木

Reference

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ) AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。