用 C++ 實現二叉搜尋樹資料結構

Jinku Hu 2023年1月30日 2021年6月28日
  1. 在 C++ 中使用 struct 關鍵字實現二叉搜尋樹
  2. 用 C++ 實現二叉搜尋樹的二叉搜尋演算法
用 C++ 實現二叉搜尋樹資料結構

本指南將演示如何在 C++ 中實現二叉搜尋樹資料結構。

在 C++ 中使用 struct 關鍵字實現二叉搜尋樹

二叉搜尋樹(BST)是二叉樹資料結構的特例。該資料結構通常用於儲存元素的排序列表,以便使用二進位制搜尋演算法進行快速搜尋。與常規二叉樹相比,BST 在每個節點中都有一個特殊的資料成員,稱為,它必須具有唯一的值。

BST 中的每個節點都應滿足以下要求:key 值必須大於其左孩子的子樹中的所有鍵,並且小於其右孩子的子樹中的所有鍵。前面的語句暗示具有較小鍵值的元素將定位在樹層次結構的左側;這導致使用二叉搜尋的最佳結構。

在下面的示例程式碼中,我們定義了一個名為 BSTreeNodestruct,它由兩個指向左/右節點的指標和一個表示鍵的 string 成員組成。請注意,我們只是實現了 BST 的最簡單版本,其中鍵值與節點中儲存的資料相同。

一般來說,程式設計師可以根據具體問題的需要,自由定義一個 BST 節點來儲存其他資料成員。這個定義最適合模擬字串的排序陣列,需要搜尋給定的字串(鍵)。在我們實現二叉搜尋功能之前,需要從頭開始構建 BST 物件。因此,我們使用預定義的字串向量來初始化新的二叉搜尋樹。

insertNode 函式是遞迴實現,用於在樹的根作為引數傳遞時建立一個新的子 BSTreeNode。如果我們需要自己建立一個根節點,你可以宣告一個指向 BSTreeNode 型別的指標,將 nullptr 分配給它,然後將它傳遞給 insertNode 以及需要儲存在那裡的相應 string 值。一旦我們使用 v1 內容初始化列表,就可以呼叫 printTree 函式以按稱為 BST 的 inorder 遍歷的排序順序列印所有鍵值。

#include <iostream>
#include <vector>

using std::cout; using std::vector;
using std::endl; using std::string;

struct BSTreeNode {
    string key;
    struct BSTreeNode *left{};
    struct BSTreeNode *right{};
};

void insertNode(BSTreeNode *&root, const string& k) {
    if (root == nullptr) {
        root = new BSTreeNode;
        root->key = k;
        root->left = nullptr;
        root->right = nullptr;
    } else {
        if (k < root->key)
            insertNode(root->left, k);
        else
            insertNode(root->right, k);
    }
}

void printTree(BSTreeNode *n) {
    if (n != nullptr) {
        printTree(n->left);
        cout << n->key << "; ";
        printTree(n->right);
    }
}

int main() {
    std::vector<string> v1 {"camel", "wind", "zero", "maya", "aim", "born", "xen"};

    BSTreeNode *root = nullptr;

    for (const auto &item : v1) {
        insertNode(root, item);
    }

    printTree(root);

    return EXIT_SUCCESS;
}

輸出:

aim; born; camel; maya; wind; xen; zero;

用 C++ 實現二叉搜尋樹的二叉搜尋演算法

由於排序,二進位制搜尋演算法在 BST 結構上是有效的,其中鍵儲存在層次結構中。BST 實現了三個主要操作:插入、刪除和查詢。

在下面的例子中,我們更多地關注查詢。findNode 函式負責在 BST 中查詢給定鍵,該鍵被傳遞給使用其根節點的函式。此命令具有遞迴性質,並返回指向儲存金鑰的 BSTreeNode 的指標。如果在任何節點中都找不到鍵值,則返回 nullptr。為了更好地演示,我們還實現了一個 printNode 函式,該函式接受節點指標並將鍵值輸出到 cout 流,以直接在函式中連結 findNode 函式返回值以列印它。

#include <iostream>
#include <vector>

using std::cout; using std::vector;
using std::endl; using std::string;

struct BSTreeNode {
    string key;
    struct BSTreeNode *left{};
    struct BSTreeNode *right{};
};

void insertNode(BSTreeNode *&root, const string& k) {
    if (root == nullptr) {
        root = new BSTreeNode;
        root->key = k;
        root->left = nullptr;
        root->right = nullptr;
    } else {
        if (k < root->key)
            insertNode(root->left, k);
        else
            insertNode(root->right, k);
    }
}

BSTreeNode *findNode(BSTreeNode *root, const string& k) {
    if (root == nullptr)
        return nullptr;

    if (k == root->key)
        return root;

    if (k < root->key)
        return findNode(root->left, k);
    else
        return findNode(root->right, k);
}

void printNode(BSTreeNode *n) {
    if (n != nullptr) {
        cout << n->key << endl;
    } else {
        cout << "Not a valid node!" << endl;
    }
}

int main() {
    std::vector<string> v1 {"camel", "wind", "zero", "maya", "aim", "born", "xen"};

    BSTreeNode *root = nullptr;

    for (const auto &item : v1) {
        insertNode(root, item);
    }

    printNode(findNode(root, "zero"));
    printNode(findNode(root, "zeroo"));

    return EXIT_SUCCESS;
}

輸出:

zero
Not a valid node!
Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn

相關文章 - C++ Data Structure