C++ 二叉搜索树原理与高效实现
一、二叉搜索树介绍
二叉搜索树（Binary Search Tree, BST）又称二叉排序树，是一种基础且强大的数据结构。它通过特定的节点排列规则实现了数据的有序存储，在算法设计与内存优化中扮演核心角色。
二、特点剖析
二叉搜索树可以为空树，其语言描绘特征如下：
- 从根节点开始，左子节点的值小于父节点。
- 从根节点开始，右子节点的值大于父节点。
- 左右子树也分别为二叉搜索树。
三、二叉搜索树实现
（1）结构创建
实现一棵二叉搜索树，需要定义节点结构和功能结构。
节点结构包含左右子节点（left, right）和数据存储变量（data）。
（2）插入节点
插入节点需要根据数据的大小判断插在左右节点的 nullptr 位置。这里使用循环实现。
注意： 需要使用其他节点代替 node 去移动，否则 node 每次都不是指向根节点。
// 插入节点
void Insert(const T& data) {
// 如果根节点为空
if (node == nullptr) {
node = new Node(data);
return;
}
// 根据数据大小查找
Node* parent = nullptr;
Node* cur = node;
while (cur) {
// 记录父节点
parent = cur;
// 如果小于父节点
if (data < cur->data) {
cur = cur->left;
} else {
cur = cur->right;
}
}
// 此时已经到了节点为空的位置
// 如果小于父节点
if (data < parent->data) {
// 插在父节点左侧
parent->left = new Node(data);
return;
} {
parent->right = (data);
;
}
}
