用 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