二叉搜索树（附源码C++）
游凡/搜索二叉树
https://gitee.com/you-fan-a/search-binary-tree
一、什么是二叉搜索树？
- 若它的左子树不空，则左子树上所有结点的值均小于它根结点的值。
- 若它的右子树不空，则右子树上所有结点的值均大于它根结点的值。
- 它的左、右树又分为⼆叉排序树
简记：“左小，右大”
举例：
此我们对这棵树进行中序遍历，就可以得到：1、3、6、8、10
二叉树的插入代码：
bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
}
else
{
Node* parent = _root;
Node* child = _root;
while (child)
{
if (key < child->_key)
{
parent = child;
child = parent->_left;
}
else if(key>child->_key)
{
parent = child;
child = parent->_right;
}
else
{
return false;
}
}
child = new Node(key, value);
if (key < parent->_key)
{
parent->_left = child;
}
else if(key>parent->_key)
{
parent->_right = child;
}
}
return true;
}二、二叉树的查找
二叉树的查找也十分简单，就是比大小：
代码：
Node* Find(const K& key)
{
Node* parent = _root;
Node* child = _root;
while (child)
{
if (key < child->_key)
{
parent = child;
child = parent->_left;
}
else if (key > child->_key)
{
parent = child;
child = parent->_right;
}
else
{
return child;
}
}
return nullptr;
}三、二叉树的删除
删除有三种情况：1、删除的节点为叶子节点。
2、删除的节点有一个孩子
3、删除的节点有两个孩子
1、第一种情况最好处理，直接删就行
2、第二种情况需要删除指定节点后再把后面的节点链接上
3、第三种情况需要一种特殊的删除放方法
找左子树的最右值或右子树的最左值，记为x，把指定要删除的节点的值替换为x，然后删除x。
（最左和最右是物理位置上的最左和最右）
例子1：
例子2：
