typedef struct node { //空木は(Tree *)NULL
int data; //格納される整数値データ
struct node *left; //左部分木を指すポインタ
struct node *right; //右部分木を指すポインタ
} Tree;
typedef Tree Node; //使用場面に応じて、TreeとNodeを使い分ける[自己参照構造体]二分木の操作関数
[コンストラクター]
①空木を取得する …getEmptyTree()
②新しいノードを作る …createNode()
[アクセサー]
③ノードにデータを格納する …setNodeData()
④ノードからデータを取り出す …getNodeData()
⑤左または右部分木に部分木を格納する …setSubTree()
⑥左または右部分木のポインタを取り出す …getSubTree()
⑦左または右部分木を保持するメンバ変数のアドレスを取り出す …getSubTreeRoot()
[データ構造に依存しない→コンストラクターやアクセサーを用いて実装]
⑧空木かどうか調べる …isEmptyTree()
⑨指定ノードのメモリ領域を解放する …freeNode()
⑩二分木内のノードをすべて削除する …rmTree()
⑪二分木内のデータを表示する …printTree()
演習ではこれらを利用して二分木を操作する
・完全にバランスした二分木の作成
・指定したデータを持つノードの削除
・二分探索木の作成
・二分探索木内のノードの追加削除 ... etc.
ノードの削除について
・3つの場合を考える必要がある
・それぞれの場合で削除方法が異なる
・リーフ(葉)の場合
・子を 持つノードの場合
・子を 持つノードの場合
リーフの削除
・これは簡単
子を1つ持つノードの削除
・これも簡単
子を2つ持つノードの削除
・この場合は単純に削除できない
最も削除が簡単なのはリーフ(葉)だよね … だったら削除対象にリーフの値をコピー
・削除対象にコピーするリーフは、どれにする？
・リーフならどれでもいい→最も探しやすいのはどれ？
最左端、または最右端のリーフ
※通常は最左端のリーフを選ぶことが多い