C二進制搜索樹示例

二進制搜索樹（BST）是一個二進制樹，其中左子樹僅包含小於節點值的節點，右子樹僅包含值大於節點值的節點，並且兩個子樹也必須是BST； 1。 C實現包括帶有價值，左和右指針的Treenode結構； 2。 BST類提供使用遞歸輔助方法的插入，搜索和內部遍歷操作； 3。插入通過比較值並避免重複物來維護BST屬性； 4。搜索通過基於比較左或右導航在O（log n）平均時間； 5。按順序打印值以排序順序訪問左，root，然後右； 6.生產的關鍵考慮包括添加一個用於內存清理的破壞者，使用AVL或紅色邏輯平衡樹，以及實現迭代方法以防止堆棧溢出，這使此示例成為對C中BST的基本理解。

這是帶有基本操作的二進制搜索樹（BST）的實用C示例：插入，搜索和按順序遍歷。

✅什麼是二進制搜索樹？

BST是一棵二進制樹：

• 節點的左子樹僅包含小於節點值的節點。
• 右子樹僅包含大於節點值的節點。
• 左右子樹都必須是二進制搜索樹。

？ C實施示例

#include <iostream>
使用命名空間std;

//定義樹節點的結構
struct treenode {
    int值；
    treenode*左；
    treenode*右；

    //構造函數
    treenode（int val）：value（val），左（nullptr），右（nullptr）{}
};

//二進制搜索樹類
BST類{
民眾：
    treenode* root;

    //構造函數
    bst（）：root（nullptr）{}

    //公共插入功能
    void insert（int value）{
        root = insertrecursive（root，value）;
    }

    //公共搜索功能
    bool搜索（int value）{
        返回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）;
        }
        //忽略重複（值==節點 - >值）

        返回節點;
    }

    //助手：遞歸搜索
    bool searchRecursive（treenode* node，int value）{
        if（node == nullptr）{
            返回false; // 未找到
        }
        if（node-> value == value）{
            返回true; // 成立
        }
        if（value <node-> value）{
            返回searchRecursive（節點 - >左，value）;
        } 別的 {
            返回searchRecursive（node->右值，value）;
        }
    }

    //助手：內排遍歷（左 - > root->右）
    void inorderRecursive（treenode* node）{
        if（node！= nullptr）{
            inorderRecursive（節點 - >左）;
            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）？“找到”：“找不到”）<< endl;
    cout <<“搜索25：” <<（tree.search（25）？“找到”：“找不到”）<< endl;

    返回0;
}

？輸出：

階段遍歷：20 30 40 50 60 70 80
搜索40：找到
搜索25：找不到

✅要點：

• 插入通過比較值來維護BST屬性。
• 搜索是有效的（o（log n）平均），左右行駛。
• 固定遍歷可提供排序的輸出 - BST的關鍵好處之一。
• 此版本忽略了重複的值。您可以對其進行修改以允許重複（例如，使用或存儲計數）。

⚠️注意：

這是一個基本實現。供生產使用，請考慮：

• 內存清理（添加刪除器刪除節點）。
• 平衡（使用AVL或紅色樹木以避免偏斜的樹木）。
• 迭代版本以避免在深樹中堆疊溢出。

基本上，此示例為您提供了堅實的基礎，以了解BST在C中的工作方式。

以上是C二進制搜索樹示例的詳細內容。更多資訊請關注PHP中文網其他相關文章！