C++ 中的二叉搜索树插入
Jinku Hu
2023年10月12日
本文将演示如何用 C++ 实现二叉搜索树数据结构的插入功能。
在 C++ 中的二叉搜索树中插入新节点
二叉树一般表示树结构的子集。它们被称为二元的，因为在任何给定节点上最多有两个孩子。在这种情况下，我们讨论二叉搜索树，其中每个节点都包含一个称为键的数据成员，并且在树的每一层，给定节点的键必须大于其左子树中的键且小于右子树中的所有键子树。此功能将允许我们在搜索排序数组时在树上使用二分搜索算法。
首先，我们需要声明一个树节点 struct，它包括两个指向 left/right 节点的指针和一个键。为简单起见，我们将键存储为 int 值，但可能需要根据问题为节点构建不同的布局。我们还通过将单个 TreeNode 指针声明为树的根，然后调用 insertNode 函数来添加新节点来手动构建这棵树。
为了更好地演示和验证我们的示例，我们还包括一个函数来查找具有给定键的节点和另一个打印整个树的内容的函数。后者将帮助我们在程序的每一步轻松检查树结构。请注意，所有三个函数都使用递归，因为树结构是分治算法所固有的。
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct TreeNode {
int key;
struct TreeNode *left{};
struct TreeNode *right{};
};
void insertNode(TreeNode *&root, const int k) {
if (root == nullptr) {
root = new TreeNode;
root->key = k;
root->left = nullptr;
root->right = nullptr;
} else {
if (k < root->key)
insertNode(root->left, k);
else
insertNode(root->right, k);
}
}
TreeNode *findNode(TreeNode *root, const int 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 printTree(TreeNode *n) {
if (n != nullptr) {
printTree(n->left);
cout << n->key << "; ";
printTree(n->right);
}
}
int main() {
std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};
TreeNode *root = nullptr;
for (const auto &item : v1) {
insertNode(root, item);
}
printTree(root);
cout << endl;
std::vector<int> v2{1, 22, 4, 16};
for (const auto &item : v2) {
insertNode(root, item);
}
printTree(root);
cout << endl;
return EXIT_SUCCESS;
}
输出：
2; 3; 5; 9; 11; 15; 20; 23;
1; 2; 3; 4; 5; 9; 11; 15; 16; 20; 22; 23;
在 main 函数中，我们声明了两个任意的 int 向量，然后将它们的元素推送到树中。请注意，我们的 insertNode 函数有两个参数 - 根节点和一个键值。它需要检查给定的根节点是否有效或只是一个 nullptr，后者表示该函数需要创建根节点内容。
如果根节点已经初始化，那么函数应该根据键值进行处理，键值与当前节点的键值进行比较。如果传递的键的值小于给定的键，我们应该向前移动到左子树。否则 - 右子树。
最终，我们将到达需要存储键的节点，并且中序遍历将始终打印已排序的键值，如代码片段所示。
作者： Jinku Hu
