用 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::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!
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