C 言語のバイナリツリー: 完全な初心者向けガイド

インフォマテックデジタル » アルゴリズム » C 言語のバイナリツリー: 完全な初心者向けガイド

最大 2 つの子を持つノードを持つ階層構造。ルート、リーフ、レベルが含まれます。
利点: 配列と比較した効率的な検索と挿入、階層的な表現、動的な柔軟性。
主な操作: データの並べ替えと管理のためのトラバーサル (in、pre、post)、検索、挿入、削除。

C 言語のバイナリツリーに関する包括的なガイドへようこそ。この記事では、バイナリツリーの基礎と、それを C プログラミング言語で実装する方法について説明します。プログラミングの初心者、または C スキルを向上させたい方には、このガイドが最適です。

二分木はコンピュータサイエンスにおける基本的なデータ構造であり、幅広いアプリケーションで使用されています。二分木の仕組みと実装方法を理解することで、複雑な問題をより効率的かつ洗練された方法で解決できるようになります。

この記事では、二分木の構造、ノードの挿入と削除、走査、要素検索など、二分木の基本について解説します。また、これらの概念が実際にどのように適用されるかを理解していただけるよう、C言語を用いた実践的な例も紹介します。

それでは始めましょう！

バイナリツリーとは何ですか?

バイナリツリーは、相互接続されたノードで構成された階層型データ構造です。各ノードには最大 2 つの子ノード (左側に 1 つ、右側に 1 つ) を設定できます。この 2 つのブランチ構造が、バイナリツリーを他のデータ構造と区別するものです。

バイナリツリーでは、最初のノードはルートノードと呼ばれます。子ノードは子ノードと呼ばれ、子を持たないノードはリーフノードと呼ばれます。同じレベルのノードは兄弟ノードと呼ばれます。

バイナリツリーの利点

バイナリツリーには、効率的なデータの保存と検索に関していくつかの利点があります。主な利点は次のとおりです。

効率的な検索バイナリツリーを使用すると、リンクリストなどの他のデータ構造よりも高速に実行時に要素を検索できます。これは、ツリーの階層構造と、データセットをすばやく分割する機能によるものです。
柔軟な挿入と取り外しバイナリツリーは、ノードの挿入および削除操作に非常に適応性があります。配列などの静的なデータ構造とは異なり、バイナリツリーは動的に成長し、構造を変更できます。
階層関係の表現バイナリツリーは、要素間の階層関係を表すのに特に役立ちます。たとえば、ファイルディレクトリ構造では、各ディレクトリはツリー内のノードとして表され、サブディレクトリとファイルはその子ノードとして表されます。

二分木の構造

C でのバイナリツリーの実装に進む前に、バイナリツリーの基本構造を理解することが重要です。バイナリツリーの各ノードには、値と、左側と右側の子ノードへの参照 (存在する場合) が含まれます。

次の表は、バイナリツリーのノードの構造を示しています。

バイナリノード
勇気
左ノード
右ノード

各ノードには、整数、文字、またはより複雑な構造など、あらゆるタイプのデータを格納できます。ルートノードはツリーの開始点であり、そこから他のすべてのノードにアクセスできます。

C で二分木を実装する

二分木に関する基本的な理解ができたところで、次はC言語で二分木を実装してみましょう。次に、C言語で二分木構造を宣言し、使用する方法を見ていきます。

バイナリツリー構造の宣言

C では、構造体とポインターを使用してバイナリツリーの構造を宣言できます。構造の基本的な宣言は次のとおりです。

struct NodoArbol {
    int valor;
    struct NodoArbol* izquierdo;
    struct NodoArbol* derecho;
};

この構造では、 valor ノードに格納されている値を表し、 izquierdo y derecho それぞれ左と右の子ノードへのポインタです。

最も人気のあるソートアルゴリズム 10 選

新しいノードの作成

バイナリツリーに新しいノードを作成するには、ノードにメモリを割り当て、その値を設定する必要があります。新しいノードを作成する C 関数を次に示します。

struct NodoArbol* crearNodo(int valor) {
    struct NodoArbol* nodo = (struct NodoArbol*)malloc(sizeof(struct NodoArbol));
    nodo->valor = valor;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}

関数 malloc ノードに動的メモリを割り当てるために使用されます。次にノードの値を設定し、作成されたノードを返します。

ノードの挿入

ノードの挿入はバイナリツリーの基本的なプロセスです。ノード値に基づいて、正しい位置に新しい要素をツリーに追加できます。以下はバイナリツリーにノードを挿入する C 関数です。

struct NodoArbol* insertarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return crearNodo(valor);
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = insertarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = insertarNodo(raiz->derecho, valor);
    }

    return raiz;
}

この関数は、ツリーのルートへのポインターと挿入するノードの値を受け取ります。ルートが null の場合、ツリーが空であることを意味し、ルートに新しいノードが作成されます。それ以外の場合は、ノードの値をルートの値と比較し、ノードを左に挿入するか右に挿入するかを決定します。

ノードの削除

バイナリツリー内のノードを削除するのは、少し複雑になる可能性があります。削除するノードに子があるかどうかなど、いくつかのケースによって異なります。以下はバイナリツリー内のノードを削除する C 関数です。

struct NodoArbol* eliminarNodo(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL) {
        return raiz;
    }

    if (valor < raiz->valor) {
        raiz->izquierdo = eliminarNodo(raiz->izquierdo, valor);
    } else if (valor > raiz->valor) {
        raiz->derecho = eliminarNodo(raiz->derecho, valor);
    } else {
        if (raiz->izquierdo == NULL) {
            struct NodoArbol* temp = raiz->derecho;
            free(raiz);
            return temp;
        } else if (raiz->derecho == NULL) {
            struct NodoArbol* temp = raiz->izquierdo;
            free(raiz);
            return temp;
        }

        struct NodoArbol* sucesor = encontrarSucesor(raiz->derecho);
        raiz->valor = sucesor->valor;
        raiz->derecho = eliminarNodo(raiz->derecho, sucesor->valor);
    }

    return raiz;
}

この関数では、ノードの値が現在のルートの値より小さいか、大きいか、等しいかをチェックします。ケースに応じて、以下のアクションを実行します。

値が小さい場合は、ツリーの左側に移動します。
値が大きい場合は、ツリーの右側に移動します。
値が等しい場合は、ノードの最も近い後継ノード (右側のサブツリー内の最小のノード) を見つけて、それを現在のノードに置き換えます。次に、右側のサブツリーから後続を削除します。

二分木の走査

トラバーサルは、バイナリツリーのすべてのノードを特定の順序で訪問できるようにする操作です。一般的なツアーの種類は 3 つあります。

順序通りの走査：まず左部分木、次に現在のノード、最後に右部分木を走査します。以下は、二分木を順序通り走査するC言語の関数です。

void inOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        inOrden(raiz->izquierdo);
        printf("%d ", raiz->valor);
        inOrden(raiz->derecho);
    }
}

先行順走査：まず現在のノードを訪問し、次に左部分木、最後に右部分木を訪問します。以下は、二分木の先行順走査を実行するC言語の関数です。

void preOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->valor);
        preOrden(raiz->izquierdo);
        preOrden(raiz->derecho);
    }
}

後順走査：まず左部分木を、次に右部分木を、最後に現在のノードを走査します。以下は、二分木の後順走査を実行するC言語の関数です。

void postOrden(struct NodoArbol* raiz) {
    if (raiz != NULL) {
        postOrden(raiz->izquierdo);
        postOrden(raiz->derecho);
        printf("%d ", raiz->valor);
    }
}

要素を検索

バイナリツリー内の要素を検索すると、データ構造内の特定の値をすばやく見つけることができます。以下はバイナリツリー内の要素を検索する C 関数です。

struct NodoArbol* buscarElemento(struct NodoArbol* raiz, int valor) {
    if (raiz == NULL || raiz->valor == valor) {
        return raiz;
    }

    if (valor < raiz->valor) {
        return buscarElemento(raiz->izquierdo, valor);
    } else {
        return buscarElemento(raiz->derecho, valor);
    }
}

この関数は、バイナリツリー内で再帰検索を実行します。現在のノードの値が検索された値と等しい場合、そのノードが返されます。それ以外の場合は、値に基づいて左または右のサブツリーが検索され、値が見つかるか null ノードに到達するまでプロセスが繰り返されます。

C と Java の MergeSort アルゴリズム

C言語で二分木を実装する例

バイナリツリーの基本と C での実装方法について説明したので、次は実用的な例を見てみましょう。

例1: バイナリツリーの作成

10、5、15、3、7、13、18 という値を持つバイナリツリーを作成するとします。C でこれを行う方法は次のとおりです。

int main() {
    struct NodoArbol* raiz = NULL;

    raiz = insertarNodo(raiz, 10);
    raiz = insertarNodo(raiz, 5);
    raiz = insertarNodo(raiz, 15);
    raiz = insertarNodo(raiz, 3);
    raiz = insertarNodo(raiz, 7);
    raiz = insertarNodo(raiz, 13);
    raiz = insertarNodo(raiz, 18);

    return 0;
}

この例では、ツリーのルートへのポインタを作成し、関数を使用します。 insertarNodo ツリーに値を追加します。

例2: バイナリツリーの順序走査

バイナリツリーの値を順番に印刷するには、関数を呼び出すことができます。 inOrden 次のようにします。

int main() {
    // Crear el árbol binario

    printf("Recorrido en orden: ");
    inOrden(raiz);
    printf("\n");

    return 0;
}

この例では、ツリー内の値を昇順で出力します。

よくある質問

1. バイナリツリーとバイナリ検索ツリーの違いは何ですか?

二分探索木 (BST) は、小さい値が左側に、大きい値が右側になるように要素が配置される特殊なタイプの二分木です。これにより、通常のバイナリツリーと比較して、より効率的な要素の検索が可能になります。

2. バイナリツリーに重複した値を持つノードを置くことはできますか?

はい、バイナリツリーに重複した値を持つノードが存在する可能性があります。ただし、バイナリツリーの実装と特定のルールに応じて、重複ノードを処理する方法が異なる場合があります。一部の実装では重複を許可し、任意の順序で保存しますが、他の実装では重複した値を特別に処理するか破棄することを要求する場合があります。

3. バイナリツリーから特定のノードを削除するにはどうすればよいですか?

バイナリツリーから特定のノードを削除するには、次の手順に従う必要があります。

ツリー検索を使用して、削除するノードを見つけます。
排除のさまざまなケースを検討します。
- ノードに子がない場合、単にノードを削除してメモリを解放することができます。
- ノードに子が 1 つしかない場合は、ノードをその子に置き換えることができます。
- ノードに 2 つの子がある場合は、最も近い後続ノード (右側のサブツリー内の最小のノード) を見つけて、削除するノードの値を後続ノードの値に置き換える必要があります。次に、ツリーから後継を削除します。
正しいツリー構造を維持するために、必要に応じてリンクとポインターを調整します。

JavaScript のバイナリツリー: 完全ガイド

4. 完全二分木とは何ですか?

完全二分木は、最後のレベルを除くすべてのレベルが完全に埋められ、最後のレベルのノードが可能な限り左に配置される特殊なタイプの二分木です。これは、最後のレベルのノードを除き、すべてのノードに 2 つの子があることを意味します。最後のレベルのノードには、子が 1 つまたはまったくない可能性があります。

5. 二分木の高さはどれくらいですか?

二分木の高さは、ルートからリーフまでの最長パスの長さです。つまり、ツリー内のルートと任意のリーフ間のエッジの最大数です。高さはレベルの数で測定されるため、ノードが 0 つだけのツリーの高さは XNUMX になり、空のツリーには高さがありません。

6. プログラムでバイナリツリーを使用する必要があるのはどのような場合ですか?

バイナリツリーはさまざまな状況で役立ちます。バイナリツリーを使用する一般的なケースとしては、次のようなものがあります。

効率的な要素検索: データ構造内の要素をすばやく検索する必要がある場合、バイナリツリーを使用するとデータに効率的にアクセスできます。
階層関係の表現: バイナリツリーは、ディレクトリ構造などの階層関係を表現するのに最適です。ファイルシステム.
データのソート: バイナリ検索ツリーを使用すると、データを効率的にソートし、検索、挿入、削除を対数時間で実行できます。

プログラムでバイナリツリーを使用するかどうかを決定する前に、必ず要件を評価し、バイナリツリーに対する操作の複雑さを考慮してください。

結論

この包括的なガイドでは、C のバイナリツリーの基本的な概念について説明しました。バイナリツリーの構造、ノードの挿入と削除の方法、トラバーサルの実行方法、バイナリツリー内の要素の検索方法について学習しました。

このガイドによって、バイナリツリーとそれを C 言語で実装する方法について理解を深めていただけたと思います。バイナリツリーは、プログラミングにおけるさまざまな問題を解決するのに役立つ、多用途で強力なデータ構造です。

C 言語のバイナリツリーの理解を深めるために、提供されている例を使って練習と実験を行ってください。ソフトウェアの学習と開発の旅がうまくいくことを祈っています。