C の二分木
Cでは、 二分木 最大 2 つの子ノードを持つ親ノードを持つツリー データ構造のインスタンスです。 0、1、または 2 つの子孫ノード。内のすべてのノード 二分木 には、独自の値と、その子への 2 つのポインター (左の子用のポインターと右の子用のポインター) があります。
二分木の宣言
あ 二分木 と呼ばれるオブジェクトを使用して C で宣言できます。 構造体 ツリー内のノードの 1 つを表します。
構造体 ノード {
データ型 var_name ;
構造体 ノード * 左 ;
構造体 ノード * 右 ;
} ;
上記は1つの宣言です 二分木 ノードとしてのノード名。 3 つの値を保持します。 1 つはデータ格納変数で、他の 2 つは子へのポインタです。 (親ノードの左右の子)。
二分木の事実
大規模なデータ セットの場合でも、 二分木 検索がより簡単かつ迅速になります。木の枝の数に制限はありません。アレイとは対照的に、あらゆる種類のツリーは、個人の要求に基づいて作成および増加できます。
C でのバイナリ ツリーの実装
以下は、実装の段階的なガイドです。 二分木 Cで。
ステップ 1: 二分探索木を宣言する
data、*left_child、*right_child などの 3 種類のデータを持つ構造体ノードを作成します。データは整数型にすることができ、*left_child ノードと *right_child ノードの両方を NULL として宣言することも、宣言しないこともできます。
構造体 ノード{
整数 データ ;
構造体 ノード * right_child ;
構造体 ノード * left_child ;
} ;
ステップ 2: 二分探索木に新しいノードを作成する
引数として整数を受け取り、その値で作成された新しいノードへのポインタを提供する関数を作成して、新しいノードを作成します。作成されたノードの動的メモリ割り当てには、C の malloc() 関数を使用します。左右の子を NULL に初期化し、nodeName を返します。
構造体 ノード * 作成 ( データ型データ )
{
構造体 ノード * ノード名 = malloc ( のサイズ ( 構造体 ノード ) ) ;
ノード名 -> データ = 価値 ;
ノード名 -> left_child = ノード名 -> right_child = ヌル ;
戻る ノード名 ;
}
ステップ 3: 二分木に右と左の子を挿入する
挿入される値と、両方の子が接続されるノードへのポインターである 2 つの入力を受け入れる関数 insert_left および insert_right を作成します。 create 関数を呼び出して新しいノードを作成し、返されたポインターをルートの親の左の子の左ポインターまたは右の子の右ポインターに割り当てます。
構造体 ノード * insert_left ( 構造体 ノード * 根 、 データ型データ ) {根 -> 左 = 作成 ( データ ) ;
戻る 根 -> 左 ;
}
構造体 ノード * insert_right ( 構造体 ノード * 根 、 データ型データ ) {
根 -> 右 = 作成 ( データ ) ;
戻る 根 -> 右 ;
}
ステップ 4: 走査法を使用して二分木のノードを表示する
C では、3 つのトラバーサル メソッドを使用してツリーを表示できます。これらのトラバーサル メソッドは次のとおりです。
1: 事前注文トラバーサル
このトラバーサル メソッドでは、次の方向にノードを通過します。 親ノード -> 左子 -> 右子 .
空所 予約注文 ( ノード * 根 ) {もしも ( 根 ) {
printf ( '%d \n ' 、 根 -> データ ) ;
display_pre_order ( 根 -> 左 ) ;
display_pre_order ( 根 -> 右 ) ;
}
}
2: ポストオーダー トラバーサル
この走査方法では、ノードからの方向にノードを通過します。 left_child->right_child->parent_node-> .
空所 display_post_order ( ノード * 根 ) {もしも ( binary_tree ) {
display_post_order ( 根 -> 左 ) ;
display_post_order ( 根 -> 右 ) ;
printf ( '%d \n ' 、 根 -> データ ) ;
}
}
3: インオーダートラバーサル
このトラバーサル メソッドでは、次の方向にノードを通過します。 left_node->root_child->right_child .
空所 display_in_order ( ノード * 根 ) {もしも ( binary_tree ) {
display_in_order ( 根 -> 左 ) ;
printf ( '%d \n ' 、 根 -> データ ) ;
display_in_order ( 根 -> 右 ) ;
}
}
ステップ 5: バイナリ ツリーで削除を実行する
作成したものを削除できます 二分木 次のように、C の親ノード関数で両方の子を削除します。
空所 delete_t ( ノード * 根 ) {もしも ( 根 ) {
delete_t ( 根 -> 左 ) ;
delete_t ( 根 -> 右 ) ;
無料 ( 根 ) ;
}
}
二分探索木のCプログラム
以下は、C プログラミングでの二分探索木の完全な実装です。
#include#include
構造体 ノード {
整数 価値 ;
構造体 ノード * 左 、 * 右 ;
} ;
構造体 ノード * ノード1 ( 整数 データ ) {
構造体 ノード * tmp = ( 構造体 ノード * ) malloc ( のサイズ ( 構造体 ノード ) ) ;
tmp -> 価値 = データ ;
tmp -> 左 = tmp -> 右 = ヌル ;
戻る tmp ;
}
空所 印刷する ( 構造体 ノード * root_node ) // ノードを表示します!
{
もしも ( root_node != ヌル ) {
印刷する ( root_node -> 左 ) ;
printf ( '%d \n ' 、 root_node -> 価値 ) ;
印刷する ( root_node -> 右 ) ;
}
}
構造体 ノード * insert_node ( 構造体 ノード * ノード 、 整数 データ ) // ノードの挿入!
{
もしも ( ノード == ヌル ) 戻る ノード1 ( データ ) ;
もしも ( データ < ノード -> 価値 ) {
ノード -> 左 = insert_node ( ノード -> 左 、 データ ) ;
} それ以外 もしも ( データ > ノード -> 価値 ) {
ノード -> 右 = insert_node ( ノード -> 右 、 データ ) ;
}
戻る ノード ;
}
整数 主要 ( ) {
printf ( 「二分探索木のC実装！ \n \n ' ) ;
構造体 ノード * 親 = ヌル ;
親 = insert_node ( 親 、 10 ) ;
insert_node ( 親 、 4 ) ;
insert_node ( 親 、 66 ) ;
insert_node ( 親 、 4.5 ) ;
insert_node ( 親 、 9 ) ;
insert_node ( 親 、 7 ) ;
印刷する ( 親 ) ;
戻る 0 ;
}
上記のコードでは、最初に ノード 使用して 構造体 .次に、新しいノードを「 ノード1 」を使用してメモリを動的に割り当てます malloc() 宣言されたノードを使用して、データと 2 つのポインター型の子を持つ C で。この後、ノードを表示します printf() 関数を呼び出して 主要（） 関数。そうして 挿入_ノード() 関数が作成され、ノード データが NULL の場合 ノード1 それ以外の場合、データは ノード 左右の子の (親)。プログラムは、 主要（） この関数は、いくつかのサンプル ノードを子として使用してノードを生成し、次に順序内トラバーサル メソッドを使用してノードの内容を出力します。
出力
結論
ツリーは、データを非線形形式で保持するためによく使用されます。 二分木 各ノード (親) が左の子と右の子の 2 つの子孫を持つツリーのタイプです。あ 二分木 は、データを転送および保存する多目的な方法です。 C の Linked-List と比較してより効率的です。上記の記事では、 二分木 の段階的な実装により、 二分探索木 Cで。