---

 

概念：

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：

搜索二叉树的操作：

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

• 二叉搜索树需要满足左子树比根小，右子树比根大，每一棵树，每一颗子树都需要满足这个条件
• 二叉搜索树使用中序遍历后，得出的遍历结果一定是一个升序序列
• 二叉搜索树的的查询操作雷素与二分查找，但是却比二分查找要来的简单，因为搜索二叉树的删除和插入操作比二分查找更为的简单，且并不需要二分查找一样，当插入和删除后必须要在经历一次排序操作。 
• 最后二叉搜索树是不允许进行节点内部的value 也就是节点数值的修改，这是因为二叉搜索树的排序操作和树的结构是因为节点的value进行链接和形成的

节点结构：

	template<class K>//struct BinarySearchTreeNodestruct BSTreeNode{BSTreeNode<K>* _left;//指向左子树指针BSTreeNode<K>* _right;//指向右子树指针K _key;//用来进行排序的value数值BSTreeNode(const K& key)//节点的初始化列表:_left(nullptr), _right(nullptr), _key(key){}};

插入操作：

 二叉搜索树的插入 插入的具体过程如下：

a. 树为空，则直接新增节点，赋值给root指针

b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

因为插入时需要保证插入之后还是二叉搜索树，所以插入操作需要进行一次的对比， 例如插入数字5，如果需要插入数字5，那么就需要进行依次的对比！

也就是和每一个节点进行对比，从根节点开始，比对比的节点小往左边移动，比对比的节点大往右移动，直到走到最后一个节点，走向空，需要记住每次插入的节点（非重复）最后都是会插入一个空的位置。

同时还需要注意，当插入的数据已经在树中存在了，而就需要注意搜索树中不会冗余，也就是插入一个相同的元素是不允许在同一个树中出现两次，这是不允许的！除非需要一些扩展。

		bool Insert(const K& key){if (_root == nullptr){//当根节点是空的时候，直接进行创造新节点进行插入操作_root = new Node(key);return true;}Node* parent = nullptr;//记录父节点，方便之后的插入操作Node* cur = _root;//从根节点开始进行查找while (cur)//当节点为空时表示找到了插入的位置{//对比 比较的节点 是否比插入的节点的数值大还是小if (cur->_key < key){//对比的节点小，则插入的节点往右边进行查找parent = cur;cur = cur->_right;}else if (cur->_key > key){//对比的节点大，则插入的节点往左边寻找parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);//找到位置后进行插入操作//使用之前的父亲节点进行判断，如果比父亲节点大则右边否则左边if (parent->_key < key)/{parent->_right = cur;}else{parent->_left = cur;}return true;}

查找函数：

 二叉搜索树的查找：

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到到空，还没找到，这个值不存在。

bool Find(const K& key){Node* cur = _root;//从根节点开始进行查找操作while (cur){if (cur->_key < key){//查找的节点比比较节点大则往右边进行继续查找cur = cur->_right;}else if (cur->_key > key){//查找的节点比比较节点小则往右边进行继续查找cur = cur->_left;}else{//找到了就返回return true;}}//直到指向了空就表示二叉搜索树中没有这个节点存在return false;}

删除函数：

 删除操作分为三种情况/两种操作：

a、删除的节点他的左子树是空的，则他的父节点要指向他的右子树，同理删除的节点他的右子树是空的，他的父节点要指向他的左子树

b、叶子节点，不过叶子节点可以和第一种情况相结合，让父节点指向删除的叶子节点的右子树

c、左右子树都不为空的：需要使用替换法，找该节点的右子树最小节点或者左子树最大节点

这里找右子树的最小节点。

操作一：情况a、情况b

删除的节点他的左子树是空的，则他的父节点要指向他的右子树，同理删除的节点他的右子树是空的，他的父节点要指向他的左子树。

同时这里还会诞生一个问题，被删除节点的左子树是空的，那父节点指向这个节点的右子树，但是是父节点的那一个指针指向呢？是右指针还是左指针？

 需要进行额外的判断，判断删除的节点是父节点的左子树还是右子树，左子树就左指针，右子树就右指针。

且还有一个细节：例如左边为空时，被删除节点的父亲点的要进行判断，判断删除的节点是父亲节点的左节点还是右节点，但是如果我们删除的是根节点，就如上图所示.

这种就需要提前进行判断，如果当前的节点是一个根节点，且左边为空时，那么根节点就需要进行替换，替换成这个根节点的右子树的头一个节点，如果是右边为空，那么这个根节点就需要替换成根节点的左子树的头一个节点。

				else{// 删除// 左为空，父亲指向我的右if (cur->_left == nullptr)//判断被删除的节点是否是他的左子树为空{//if(parent == nullptr)是否为根节点的判断if (cur == _root){//为根节点，那么根节点替换成根节点的右子树_root = cur->_right;}else{//不算根节点则进行父亲节点的指向判断if (cur == parent->_left){
//如果当前节点是父亲节点的左子树，那么就使用父亲节点的左指针指向这个节点的右子树parent->_left = cur->_right;}else{
//如果当前节点是父亲节点的右子树，那么就使用父亲节点的右指针指向这个节点的右子树parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){//if(parent == nullptr)//是否是根节点的判断if (cur == _root){_root = cur->_left;}else{// 右为空，父亲指向我的左if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}

操作二：

 左右子树都不为空的：需要使用替换法，找该节点的右子树最小节点或者左子树最大节点，这里找右子树的最小节点。

找到这个被删除节点的右子树，然后进入右子树后一直往左边走，找到被删除节点的右子树的 最小的数，而删除操作则需要吧要删除的节点和最小数替换（交换操作）

但是有产生一个问题，之后要删除的话，可能找不到要删除的节点，所以我们还需要一个最小节点的父亲节点，进行指向操作，所以在找右子树最小节点的时候，还得跟更新他的父节点。

同时删除后让父亲节点的左指针指向空（这里删除的节点是叶子节点没有字节的，所以删除节点的指向是null）

但是这种只能因对常规删除，如果删除的的节点中他的右子树是一个叶子节点呢，又或者，它是根节点呢：

就如上图这种情况，这种情况下删除根节点，那么右子树的最小节点就是根的右孩子节点

同时在我们的代码中，交换删除后，我们让父亲节点的左指针，指向被删除节点的右子树（常规操作是最小右节点的父亲节点指向空，这里的最小右节点刚好是根节点的有孩子），那么放在上图情况会直接崩掉，所以还需要进行一个判断

最后这个判断的前者是判断是否是正常情况，在正常情况中，最小右子树节点的父节点只是一个普通的节点，且最小右子树节点的父节点的左边一定是最小右子树节点，所以可以让父节点指向最小右字数节点的 右子树

而非常情况就是如上图这种情况，根节点的右孩子节点就是根节点的最小右子树节点，这种非常情况下，根节点的最小右子树节点在右边，所以需要让根节点的右指针指向最小右子树节点的 右子树。

else{// 左右都不为空，替换法删除// // 查找右子树的最左节点替代删除Node* rightMinParent = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}swap(cur->_key, rightMin->_key);if (rightMinParent->_left == rightMin)rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;}

完成的删除函数代码： 

bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){//查询炒作，查询所需要删除的节点的位置if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}//找到位置后进行删除操作else{// 删除// 左为空，父亲指向我的右if (cur->_left == nullptr){//if(parent == nullptr)if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){//if(parent == nullptr)if (cur == _root){_root = cur->_left;}else{// 右为空，父亲指向我的左if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 左右都不为空，替换法删除// // 查找右子树的最左节点替代删除Node* rightMinParent = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}swap(cur->_key, rightMin->_key);if (rightMinParent->_left == rightMin)rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;}return true;}}return false;}

中序遍历：

void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}

需要注意，这里中序遍历这样写的原因是因为root根节点是私有的原因，所以在外是调不动中序遍历函数的，所以需要把中序遍历函数进行套用，放在私有成员内部，在外部套用一层调用即可使用。 

---