スポンサーリンク

ツリー構造のデータ構造

構造体で下記のように表現しています。
各ノードには、値と左右のノードへのポインタを定義しています。

また、ツリー構造の先頭を定義するため、別途tree_tを定義しています。

スポンサーリンク

ツリー構造の各関数

まずは、実際にツリーにノードを挿入する関数です。
ツリーの先頭から各ノードをたどって行き、登録されていなければ、新しくノードを作成してvalueを格納します。

挿入しようとしているvalueとノードのvalueを比較して、挿入しようとしているvalueが小さければ左のノードを、大きければ右のノードをたどって行きます。再帰関数で実現しています。

下記は、ノードを実際に作成するサブ関数になります。
メモリを確保して、値を代入します。
終端ノードになるので、左右のノードへのポインタにはNULLを代入します。

下記は、各ノードのメモリを解放する関数になります。
再帰関数で全てのノードを順にたどって行き、free()していきます。

ツリーの中の最大値と階層レベルを表示する関数です。
ツリーの先頭から終端ノードに行き着くまで、右のノードをたどって行きます。
右終端ノードに最大値が格納されています。

ツリーの中の最小値と階層レベルを表示する関数です。
ツリーの先頭から終端ノードに行き着くまで、左のノードをたどって行きます。
左終端ノードに最小値が格納されています。

下記は、ツリーに指定したvalueの値が格納されているノードが存在するかを表示する関数になります。
再帰関数で全てのノードをたどって行きます。

スポンサーリンク

サンプルコード

下記がサンプルコードになります。

下記が実行結果になります。

スポンサーリンク