游凡/搜索二叉树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：