二叉搜索树（BST）
从一棵随机二叉搜索树开始，逐步插入、查找或删除值，同时展示其数组形式并高亮 C++ 代码。
所有内容均在此浏览器中模拟，不会发送到任何服务器。
无步骤
无步骤
二叉搜索树
数组索引
数组形式
索引 i 的子节点位于 2i+1 和 2i+2。
- 无关
- 已经过
- 正在比较
- 已找到
- 新增
- 待删除
- 后继节点
无步骤
代码
#include <iostream>
using namespace std;
class Node { // 节点保存其值和指向两个子节点的指针
private: // 私有属性：只有方法可以访问
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
Node* insert(Node* root, int v) { // 将 v 插入搜索树并返回根节点
if (root == nullptr) // 空位：新节点放在这里
return new Node(v); // 创建新节点
if (v < root->getValue()) // 较小的值放左边，较大的值放右边
root->setLeft(insert(root->getLeft(), v)); // 进入左子树
else
root->setRight(insert(root->getRight(), v)); // 进入右子树
return root;
}
int main() {
Node* root = buildTree(); // 所示的树，已构建完成
root = insert(root, v); // 首次调用，来自 main
return 0; // 操作结束
}