二叉搜索树介绍
二叉搜索树又称二叉排序树，是一颗二叉树完成了排序的工作。它与大小顶堆有所不同。
特点剖析
二叉搜索树（可以为空树）的语言描绘特征如下：
- 从根节点开始，它的左子节点小于父节点。
- 从根节点开始，它的右子节点大于父节点。
- 它的左右子树也分别为二叉搜索树。
二叉搜索树实现
结构创建
实现一棵二叉搜索树，我们需要一个节点结构、一个功能结构。
节点结构里面有左右子节点（left，right）、一个数据存储变量（data）。 注意：主模板的声明不允许使用模板参数。 功能结构用来实现二叉搜索树的功能。
插入节点
插入节点我们需要根据数据的大小来判断插在左右节点的 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;
} else {
// 插在父节点右侧
parent->right = new Node(data);
return;
}
}
中序遍历
中序我们调用递归来完成：先遍历左子树，然后父节点，然后右子树。
