木構造の基本要素と種類

木構造は、根を起点に親子関係で節点を階層接続し、閉路を持たない連結構造です。

■ 試験で押さえるポイント

• 根は親を持たない最上位節点、葉は子を持たない節点、内部節点は子を持ち、枝・辺が親子を結びます。

• 節点の深さは根からの辺数、高さは最も深い葉までの長さ、部分木はある節点とその子孫から成ります。

• 二分木は各節点の子が最大二つで左右を区別し、完全二分木は最下層以外が満たされ最下層を左から詰めます。

• 順序木は兄弟の順序に意味があり、多分木は二つを超える子を許し、平衡木は高さの偏りを抑えて操作効率を保ちます。

$\text{深さ}h\text{までの完全な二分木の最大節点数}=2^{h+1}-1$

■ 選択肢での判断ポイント

根は親なし、葉は子なし、深さは根から、部分木は節点と全子孫です。完全二分木は最下段を左から詰めると定義します。

例: 深さ2まで全て埋まった二分木は$1+2+4=7$節点を持ち、深さ2の4節点が葉です。