木構造というデータ構造の中で、子ノードを3つ以上取れる木構造は多分木と言い、
子ノードの数がNで固定されている物をN分木と言います。
子ノードの数が2つの物を2分木と言います。
親のないノードを根(root node)、子のないノードを葉(leaf node)と呼びます。
なぜ急に2分木を解説するかと言うと、階層アニメーションや
スキンメッシュアニメーションの階層構造を配列や動的な多次元配列で
管理すると無駄が生じるからです。
それに対して2分木構造で管理すると全く無駄が無く、どのような
子ノードの数や階層数にも対応でき、動的に増やしたり減らしたりする事も
簡単にできます。
ではまず、簡単に仕組みを解説します。
2分木構造は前回解説した自己参照構造体の自己参照ポインタを2つ持っている
構造体を作るだけで簡単に作成できます。
左ノード、右ノードという使用法が一般的ですが、今回は少し見方を変えて、
子ノードへのポインタと同一階層の隣階層へのポインタという感じで使用します。
子ノードが存在したら子ノードへのポインタを new で作成し、隣階層が
存在したら隣階層へのポインタを new で作成します。
それを再帰関数で処理し、ノードが無いデータの終わりは NULL で埋めます。
以下に簡単な解説図を示します。
