C++系列—二叉搜索树

提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加
例如：第一章 Python 机器学习入门之pandas的使用

---

---

前言

一、二叉搜索树

1.1、二叉搜索树概念

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

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

二、二叉搜索树的构造

接下来我们以下面这个二叉搜索树为例进行讲解

假设我们需要使用这样一组数据构造一棵二叉搜索数 {8, 3, 1, 10, 6, 4, 7, 14, 13};

1. 首先插入第一个元素 8，此时二叉搜索树只有一个节点，这个节点就是根节点.

• 插入3，比较 3 和根节点 8，因为 3 < 8，所以 3 成为 8 的左子节点。
• 插入1，比较 1 和根节点 8，1 < 8，再比较 1 和 8 的左子节点 3，因为 1 < 3，所以 1 成为 3 的左子节点。
• 插入10，比较 10 和根节点 8，因为 10 > 8，所以 10 成为 8 的右子节点。
• 插入6，比较 6 和根节点 8，6 < 8，再比较 6 和 8 的左子节点 3，因为 6 > 3，所以 6 成为 3 的右子节点。
• 插入4，比较 4 和根节点 8，4 < 8，再比较 4 和 8 的左子节点 3，因为 4 > 3，继续比较 4 和 3 的右子节点 6，因为 4 < 6，所以 4 成为 6 的左子节点。
  7.插入7， 比较 7 和根节点 8，7 < 8，再比较 7 和 8 的左子节点 3，因为 7 > 3，继续比较 7 和 3 的右子节点 6，因为 7 > 6，所以 7 成为 6 的右子节点。
• 插入14，比较 14 和根节点 8，因为 14 > 8，再比较 14 和 8 的右子节点 10，因为 14 > 10，所以 14 成为 10 的右子节点。
• 插入13，比较 13 和根节点 8，13 > 8，再比较 13 和 8 的右子节点 10，因为 13 > 10，继续比较 13 和 10 的右子节点 14，因为 13 < 14，所以 13 成为 14 的左子节点。

我们可以看出：
只要左子树为空，就把小于父节点的数插入作为左子树
只要右子树为空，就把大于父节点的数插入作为右子树
如果不为空，就一直往下去搜索，直到找到合适的插入位置

那么构建出这样一颗二叉数，有什么用呢？
不妨思考一下，它为什么叫做二叉排序数？

当我们以中序遍历来读取它时得到的结果为：
1、2、4、6、7、8、10、13、14
这正是将上面数据升序，排序后的结果。

下面我们用代码将他实现出来：
节点：

利用结构体来实现，内部包含两个指针，一个指向左子树，一个指向右子树，一个_key变量用来存储数据。

struct BSTreeNode {typedef BSTreeNode<T> Node;T _key;Node* _left;Node* _right;BSTreeNode(const T&key):_key(key),_left(nullptr),_right(nullptr){}
};

插入：

根据我们构建上述二叉搜索的步骤，编写代码

bool _Insert(Node* root,const T&key)
{if (root == nullptr){ _root = new Node(key);//树为空，直接更新根节点return true;}	Node* cur = _root;//记录当前节点Node* parent = nullptr;//记录当前节点的父节点while (cur){parent = cur;if (cur->_key > key)//待插入值小于当前节点存储值{cur = cur->_left;//更新当前节点到左子树}else if (cur->_key < key)//待插入值大于当前节点存储值{cur = cur->_right;//更新当前节点到右子树}else {return false;//待插入值等于当前节点存储值，不插入}}cur= new Node(key);//cur为空，结束循环，找到要插入位置if (parent->_key > key)//利用父节点判断连接位置parent->_left = cur;else parent->_right = cur;return true;
}

三、二叉排序树的查找操作

二叉搜索树又叫二叉查找树，听名字就具备优秀的查找功能，其操作与二分查找非常相似，它是利用二叉树构建时的特性，来实现快速查找的。下面我们直接来查找一个，让大家体会一下查找过程。（这里要说明以下：在正常的数据结构中，由于数据量很大，所以我们也不知道我们想要的元素在不在里面；同时也不知道每个元素具体是多少，只知道他们的大小关系。我们是在此基础上进行查找）

假设要找6，首先我们拿待查找值与根节点所存储值8，进行比较，发下6小于8，于是我们就可以去8的左子树中查找，也就是和3比较，发现比它大，于是去3的右子树中查找，再通过比较，发现相等，就可以找到了。同样的如果，所查找值，不存在这棵树中，最终我们会得到一个空节点。

bool find(const T&x)//用来处理类外无法获得根节点问题，也可添加一个成员函数，用于在类外获取根节点
{_find(_root);
}
bool _find(Node*root,const T&key)
{if (root == nullptr)return false;if (root->_key > key)return _find(root->_left);if (root->_key < key)return _find(root->_right);return true;
}

四、二叉搜索数的删除

这一块可以说是二叉搜索数最难的一个成员函数了

对于待删除节点首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程
如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除（简单来说就是查找待删除节点左子树的最右节点，或右子树的最左节点来和他交换）

这样讲理论是很抽象的，下面我们结合图型来分析一下这几种情况

4.1、被删除结点为叶子结点

这一场景，即可归为情况b,也可归为情况c，如果不理解，没关系先继续往下看

直接从二叉排序中删除即可，不会影响到其他结点。例如删去13

4.2、被删除结点cur仅有一个孩子

情况b->仅有左孩子：

情况c->仅有右孩子：

4.3、被删除结点左右孩子都在

这种情况就要复杂很多了,大家要仔细看。

在学习堆的删除时，我们使用到了替换法，它的目的是保证，删除堆顶元素后，仍要保持结构满足堆的特性，这里也一样，我们要在删除节点后使得仍满足，搜索二叉树的性质，那么我们该找哪个位置的元素，来和待删除位置进行交换呢？

为了方便大家看，把树再放下来一份

假设我们们要删除8(它满足左右节点都存在），我们需要在下面找一个可以看住场子的了“老大哥”，这时只有，左子树的最大节点或右子树的最小节点，来带替这个位置最合适，即左子树的最右节点或右子树的最左节点。
使用8左子树的最右节点：

使用8右子树的最左节点：

删除操作代码：

bool erase(const T& key)
{if (_root == nullptr)//空树删除失败return false;Node* parent = nullptr;Node* cur = _root;//存储待删除节点while (cur)//循环找到要删除节点{parent = cur;if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key)cur = cur->_right;else break;}if (cur == nullptr)return false;//待删除节点不存在，返回失败if (cur->_left==nullptr)// 当前节点只有右孩子---可直接删除（思考一下这里叶子节点也能跑过）{//删除后让付节点指向右孩子，这里右孩子是否为空，不产生影响，顾上述可将四种情况，归纳为三种if (parent->_left = cur)parent->_left = cur->_right;elseparent->_right = cur->_right;delete cur;}else if (cur->_right == nullptr)// 当前节点只有左孩子---可直接删除{if (parent->_left = cur)parent->_left = cur->_left;elseparent->_right = cur->_left;delete cur;}else //左右孩子都存在{Node* parent = cur;Node* subLeft = cur->_right;//这里我使用的是右子树，最左节点while (subLeft->_left){parent = subLeft;if (subLeft->_left)subLeft = subLeft->_left;}swap(subLeft->_key, cur->_key);//交换待删除节点，右子树最左节点（值交换）if (parent->_left == subLeft)parent->_left = subLeft->_right;elseparent->_right = subLeft->_right;delete subLeft;}return true;
}

还有一些简单接口，就不讲解了，我把代码给大家贴出来

#include<iostream>
using namespace std;
template<class T>
struct BSTreeNode {typedef BSTreeNode<T> Node;T _key;Node* _left;Node* _right;BSTreeNode(const T&key):_key(key),_left(nullptr),_right(nullptr){}
};
template<class T>
class BSTree {
public:BSTree():_root(nullptr){}typedef BSTreeNode<int> Node;bool Insert(T key){return _Insert(_root,key);}bool _Insert(Node* root,const T&key){if (root == nullptr){ _root = new Node(key);return true;}	Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else {return false;}}cur= new Node(key);if (parent->_key > key)parent->_left = cur;else parent->_right = cur;return true;}bool find(const T&x){_find(_root);}bool _find(Node*root,const T&key){if (root == nullptr)return false;if (root->_key > key)return _find(root->_left);if (root->_key < key)return _find(root->_right);return true;}bool erase(const T& key){if (_root == nullptr)return false;Node* parent = nullptr;Node* cur = _root;while (cur){parent = cur;if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key)cur = cur->_right;else break;}if (cur == nullptr)return false;if (cur->_left==nullptr){if (parent->_left = cur)parent->_left = cur->_right;elseparent->_right = cur->_right;delete cur;}else if (cur->_right == nullptr){if (parent->_left = cur)parent->_left = cur->_left;elseparent->_right = cur->_left;delete cur;}else {Node* parent = cur;Node* subLeft = cur->_right;while (subLeft->_left){parent = subLeft;if (subLeft->_left)subLeft = subLeft->_left;}swap(subLeft->_key, cur->_key);if (parent->_left == subLeft)parent->_left = subLeft->_right;elseparent->_right = subLeft->_right;delete subLeft;}return true;}void print(){_print(_root);}void _print(Node* root){if (root == nullptr)return;_print(root->_left);cout << root->_key << " ";_print(root->_right);}bool empty(){return _root == nullptr;}bool Erase(const T&key){return _erase(_root,key);}bool _erase(Node*& root,const T&key){if (root == nullptr)return false;if (root->_key > key)return _erase(root->_left,key);else if(root->_key<key)return _erase(root->_right,key);else{if (root->_left == nullptr)root = root->_right;else if (root->_right == nullptr)root = root->_left;else{Node* subLeft = root->_right;Node* parent = root;while (subLeft->_left){parent = subLeft;subLeft = subLeft->_left;}swap(root->_key, subLeft->_key);if (parent->_left == subLeft)parent->_left = subLeft->_right;elseparent->_right = subLeft->_right;}}return true;}
private:Node* _root;
};

总结

在学习树型结构时，希望大家可以画图理解！！！！