Cクイックリファレンス 第2版

12.6

 実装

191

は0、図12-1の木の高さは3となる。

12.6

 実装

次に、二分探索木の基本関数の実装例を示し、動的メモリ管理を使う。この木はどのよ

うな種類のデータも扱えることを意図する。そのために、節点の構造体型はデータを格納

する柔軟なメンバとデータのサイズを示すメンバを含む。

typedef struct Node {

struct Node* left; //

左右の子節点へのポインタ

struct Node* right;

size_t size; //

データのサイズ

char data[]; //

データそのもの

} Node_t;

ポインタ

left

と

right

は節点が左の子または右の子を持たないとナルポインタだ。

実装のユーザは2つの補助関数を用意しなければならない。1番目の関数は渡されたデー

タ値に対応するキーを求め、2番目は2つのキーを比較する。1番目の

関数は次の型となる。

typedef const void* GetKeyFunc_t(const void* dData);

第2関数は標準関数

bsearch()

で使われる比較関数と同じ型となる。

typedef int CmpFunc_t(const void* pKey1, const void* pKey2);

比較関数を呼び出すときに渡される引数は、比較したい 2つのキーへのポインタだ。関

数の戻り値は、第1キーが第2キーより小さいと負、同じだと0、第1キーが第2キーより大

きいと正となる。キーはデータそのものでもよい ...