用 C++ 實現二叉搜尋樹資料結構
本指南將演示如何在 C++ 中實現二叉搜尋樹資料結構。
在 C++ 中使用 struct 關鍵字實現二叉搜尋樹
二叉搜尋樹（BST）是二叉樹資料結構的特例。該資料結構通常用於儲存元素的排序列表，以便使用二進位制搜尋演算法進行快速搜尋。與常規二叉樹相比，BST 在每個節點中都有一個特殊的資料成員，稱為鍵，它必須具有唯一的值。
BST 中的每個節點都應滿足以下要求：key 值必須大於其左孩子的子樹中的所有鍵，並且小於其右孩子的子樹中的所有鍵。前面的語句暗示具有較小鍵值的元素將定位在樹層次結構的左側；這導致使用二叉搜尋的最佳結構。
在下面的示例程式碼中，我們定義了一個名為 BSTreeNode 的 struct，它由兩個指向左/右節點的指標和一個表示鍵的 string 成員組成。請注意，我們只是實現了 BST 的最簡單版本，其中鍵值與節點中儲存的資料相同。
一般來說，程式設計師可以根據具體問題的需要，自由定義一個 BST 節點來儲存其他資料成員。這個定義最適合模擬字串的排序陣列，需要搜尋給定的字串（鍵）。在我們實現二叉搜尋功能之前，需要從頭開始構建 BST 物件。因此，我們使用預定義的字串向量來初始化新的二叉搜尋樹。
insertNode 函式是遞迴實現，用於在樹的根作為引數傳遞時建立一個新的子 BSTreeNode。如果我們需要自己建立一個根節點，你可以宣告一個指向 BSTreeNode 型別的指標，將 nullptr 分配給它，然後將它傳遞給 insertNode 以及需要儲存在那裡的相應 string 值。一旦我們使用 v1 內容初始化列表，就可以呼叫 printTree 函式以按稱為 BST 的 inorder 遍歷的排序順序列印所有鍵值。
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
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::endl;
using std::string;
using std::vector;
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!
