Cバイナリ検索ツリーの例

バイナリ検索ツリー（BST）は、左サブツリーにはノードの値よりも低い値を持つノードのみが含まれるバイナリツリーであり、右サブツリーにはノードの値よりも大きい値を持つノードのみが含まれ、両方のサブツリーもBSTでなければなりません。 1. C実装には、値、左、および右のポインターを持つTreeNode構造が含まれます。 2。BSTクラスは、再帰ヘルパー法を使用して、挿入、検索、および順序トラバーサル操作を提供します。 3.挿入値を比較し、重複を回避することにより、BSTプロパティを維持します。 4.比較に基づいて左または右をナビゲートすることにより、検索はO（log n）平均時間で動作します。 5.左、ルート、右にアクセスして、並べ替えられた順序で値を印刷する順序で印刷する。 6.生産に関する重要な考慮事項には、メモリクリーンアップのためのデストラクタの追加、AVLまたは赤黒のロジックを使用してツリーのバランスをとること、スタックオーバーフローを防ぐための反復方法の実装、この例はcのBSTの基礎的理解になります。

以下は、基本的な操作を備えたバイナリ検索ツリー（BST）の実用的な例です。挿入、検索、および順序トラバーサルです。

binaryバイナリ検索ツリーとは何ですか？

BSTは次のバイナリツリーです：

• ノードの左サブツリーには、ノードの値よりも小さい値を持つノードのみが含まれています。
• 右のサブツリーには、ノードの値よりも大きい値を持つノードのみが含まれています。
• 左右のサブツリーもバイナリ検索ツリーでなければなりません。

？ C実装の例

#include <iostream>
名前空間STDを使用。

//ツリーノードの構造を定義します
streenode {
    int値;
    treeNode*左;
    treenode*右;

    //コンストラクター
    treenode（int val）：value（val）、left（nullptr）、右（nullptr）{}
};

//バイナリ検索ツリークラス
クラスBST {
公共：
    treenode* root;

    //コンストラクター
    bst（）：root（nullptr）{}

    //パブリックインサート機能
    void insert（int value）{
        root = insertrecursive（root、value）;
    }

    //パブリック検索機能
    bool search（int value）{
        return searchRecursive（root、value）;
    }

    //注文のトラバーサル（ソート順序で値を印刷）
    void inorder（）{
        inorderRecursive（root）;
        cout << endl;
    }

プライベート：
    //ヘルパー：ノードを再帰的に挿入します
    treenode* insertrecursive（treeNode* node、int value）{
        //ツリーが空の場合は、新しいノードを作成します
        if（node == nullptr）{
            新しいtreeNode（value）を返します。
        }

        //それ以外の場合、ツリーを再発します
        if（value <node-> value）{
            node-> left = insertrecursive（node-> left、value）;
        } else if（value> node-> value）{
            node-> right = insertrecursive（node-> right、value）;
        }
        //複製を無視する（value == node-> value）

        ノードを返す;
    }

    //ヘルパー：再帰的に検索します
    bool searchRecursive（treenode* node、int value）{
        if（node == nullptr）{
            falseを返します。 // 見つかりません
        }
        if（node-> value == value）{
            trueを返します。 // 見つかった
        }
        if（value <node-> value）{
            SearchRecursive（node-> left、value）を返します。
        } それ以外 {
            return searchRecursive（node-> right、value）;
        }
    }

    //ヘルパー：注文のトラバーサル（左 - > root->右）
    void inorderRecursive（treenode* node）{
        if（node！= nullptr）{
            inorderRecursive（node-> left）;
            cout << node-> value << "";
            inorderRecursive（node-> right）;
        }
    }
};

//使用の例
int main（）{
    BSTツリー;

    //値を挿入します
    tree.insert（50）;
    tree.insert（30）;
    tree.insert（70）;
    tree.insert（20）;
    tree.insert（40）;
    tree.insert（60）;
    tree.insert（80）;

    //注文のトラバーサルを印刷（ソートする必要があります）
    cout << "順序トラバーサル：";
    tree.inorder（）; //出力：20 30 40 50 60 70 80

    //値を検索します
    cout << "検索40：" <<（tree.search（40）？ "fund"： "not in not in"）<< endl;
    cout << "検索25：" <<（tree.search（25）？ "fund"： "not ingoind"）<< endl;

    0を返します。
}

？出力：

順序トラバーサル：20 30 40 50 60 70 80
検索40：見つかりました
検索25：見つかりません

✅キーポイント：

• 挿入は、値を比較することによりBSTプロパティを維持します。
• 検索は、左/右に進むことにより、効率的です（平均してo（log n））。
• 順序トラバーサルは、ソートされた出力を提供します。これは、BSTの重要な利点の1つです。
• このバージョンは、重複した値を無視します。それを変更して、複製を許可することができます（例： またはcountを使用することで）。

⚠️注：

これは基本的な実装です。生産の使用については、次のことを検討してください。

• メモリクリーンアップ（ノードを削除するためにデストラクタを追加）。
• バランス（歪んだ木を避けるためにAVLまたは赤黒の木を使用してください）。
• 深い木のスタックオーバーフローを避けるための反復バージョン。

基本的に、この例は、cでBSTがどのように機能するかを理解するための強固な基盤を提供します。

以上がCバイナリ検索ツリーの例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。