【数据结构高阶】二叉搜索树

接下来我们来开始使用C++来详细讲解数据结构的一些高阶的知识点

本期讲解的是二叉搜索树，对于初阶二叉树有所遗忘的同学可以看到这里：

【精选】【数据结构初阶】链式二叉树的解析及一些基本操作

讲解二叉搜索树主要是为了后面的map和set做铺垫，废话不多说我们直接上干货：

---

目录

一、二叉搜索树的概念

二、模拟实现二叉搜索树

2.1 插入数据

2.1.1 插入数据的非递归实现

2.2 遍历数据

2.3 查找数据

2.4 删除数据

2.4.1 删除数据的非递归实现

2.5 模拟实现二叉搜索树的全部代码

---

一、二叉搜索树的概念

二叉搜索树又称二叉排序树（BST， Binary Search Tree），它可以是一棵空树，或者是具有以下性质的二叉树：

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

 例如：

 

我们可以发现的一点：无论是什么样的二叉搜索树，使用中序遍历，遍历出的值都是升序排列的

二、模拟实现二叉搜索树

下面又到了我们最激动人心的代码实现环节，本次代码实现我们还是要基于链式二叉树的实现：

template<class K>
struct BSTreeNode//节点
{BSTreeNode<K>* _lchild;BSTreeNode<K>* _rchild;K _key;BSTreeNode(const K& key):_lchild(nullptr),_rchild(nullptr),_key(key){}
};

2.1 插入数据

我们可以根据二叉搜索树的规律来向其中插入数据，但是插入数据时需要注意一点：要记录插入节点的上一个父节点，将插入的节点连接上二叉树：

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);_root->_key = key;return true;}Node* cur = _root;//使用cur遍历二叉树找到合适的插入位置Node* parent = cur;//记录cur的父节点while (cur){parent = cur;if (key < cur->_key){cur = cur->_lchild;}else if (key > cur->_key){cur = cur->_rchild;}else{return false;//这里创建的二叉搜索树不允许出现值的冗余}}cur = new Node(key);//创建//将创建的节点链接到二叉树上if (key < parent->_key){parent->_lchild = cur;}else{parent->_rchild = cur;}return true;}private:Node* _root = nullptr;//根节点
};

2.1.1 插入数据的非递归实现

递归的效率并没有循环高，那为什么要说一下插入数据的非递归实现呢

主要是非递归的数据插入的传值方法值得一说：

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool InsertR(const K& key)//插入数据(递归){return _InsertR(_root, key);}bool _InsertR(Node*& root,const K& key)//这里使用指针的引用用来直接修改其父节点指针的指向{if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){_InsertR(root->_lchild, key);}else if (root->_key < key){_InsertR(root->_rchild, key);}else{return false;}}
private:Node* _root = nullptr;//根节点
};

我们可以看到在递归时，传入的形参类型为Node*&，这样可以直接在其函数内部习惯其父节点孩子指针的指向

那为什么要写两个插入函数呢？因为如果我们直接使用_InsertR函数，无法直接使用对象对_InsertR函数进行传参

2.2 遍历数据

因为二叉搜索树的性质，这里我们采用中序遍历： 

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key)插入数据{....}void InOrder()//中序遍历{_InOrder(_root);cout << endl;}void _InOrder(Node* root){if (root == NULL)//如果是空树就直接结束{return;}_InOrder(root->_lchild);//先递归遍历其左子树cout << root->_key << " ";//再遍历其根节点_InOrder(root->_rchild);//最后递归遍历其右子树}private:Node* _root = nullptr;//根节点
};

那为什么要写两个中序遍历函数呢？因为如果我们直接使用_InOrder函数，无法直接使用对象对_InOrder函数进行传参

2.3 查找数据

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key)//插入数据{......}void InOrder()//中序遍历{......}void _InOrder(Node* root){......}bool Find(const K& key)//查找数据{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_rchild;}else if (cur->_key > key){cur = cur->_lchild;}else{return true;}}return false;}private:Node* _root = nullptr;//根节点
};

2.4 删除数据

对于在二叉搜索树中删除数据，我们就要好好说道说道了

下面我们有这样的一个二叉搜索树：

现在我们要删除其叶子节点，这很容易，直接删除完，再将其父节点对应的孩子指针置空即可

那我们要删只有一个孩子节点的数据呢？例如14和10

这个稍微麻烦一点，删除完该节点后将其孩子节点托付给其父节点即可：

那要删带有两个孩子节点的数据呢？例如3、6、8：

对于这种情况我们可以选择其节点下的左子树的最大节点（左子树的最右节点），或者右子树的最小节点（右子树的最左节点）来替代要删除的节点：

综上所述，要删除的结点可能分下面四种情况：

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点 

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除

情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除

情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除

思路我们有了，下面用代码来实现一下：

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key)//插入数据{...}void InOrder()//中序遍历{...}private:void _InOrder(Node* root){...}public:bool Find(const K& key)//查找数据{...}bool Erase(const K& key){Node* cur = _root;//使用cur遍历二叉树找到要删除元素的位置Node* parent = cur;//记录cur的父节点while (cur)//寻找需要删除的节点{if (cur->_key < key){parent = cur;cur = cur->_rchild;}else if (cur->_key > key){parent = cur;cur = cur->_lchild;}else//找到了,开始删除{if (cur->_lchild == cur->_rchild && cur->_lchild == nullptr)//删除的节点为叶子节点{if (parent == cur)//删除的是根节点{_root = nullptr;//更新根节点}//将其父节点指向的自身的指针置空else if (parent->_lchild == cur){parent->_lchild = nullptr;}else{parent->_rchild = nullptr;}//释放节点空间delete cur;cur = nullptr;}else if (cur->_rchild == nullptr)//删除的节点右孩子为空,左孩子不为空{if (parent == cur)//删除的是根节点{_root = cur->_lchild;//更新根节点}//将删除节点的左孩子交给其父节点else if (parent->_lchild == cur){parent->_lchild = cur->_lchild;}else{parent->_rchild = cur->_lchild;}//释放节点空间delete cur;cur = nullptr;}else if (cur->_lchild == nullptr)//删除的节点左孩子为空,右孩子不为空{if (parent == cur)//删除的是根节点{_root = cur->_rchild;//更新根节点}//将删除节点的右孩子交给其父节点else if (parent->_lchild == cur){parent->_lchild = cur->_rchild;}else{parent->_rchild = cur->_rchild;}//释放节点空间delete cur;cur = nullptr;}else//删除的节点左右孩子都不为空,要找到删除节点的左子树的最大节点或右子树的最小节点可将其替换{//这里找要删除节点的左子树的最大节点（右子树的最小节点也可）Node* maxleft = cur->_lchild; // 记录左子树的最大节点Node* pmaxleft = cur;//记录左子树的最大节点的父节点while (maxleft->_rchild)//查找左子树的最大节点{pmaxleft = maxleft;maxleft = maxleft->_rchild;}//将找到的节点替换要删除的节点cur->_key = maxleft->_key;if (pmaxleft->_lchild == maxleft){pmaxleft->_lchild = maxleft->_lchild;}else{pmaxleft->_rchild = maxleft->_lchild;}//释放节点空间delete maxleft;maxleft = nullptr;}return true;}}return false;//没找到要删除的节点}
private:Node* _root = nullptr;//根节点
};

2.4.1 删除数据的非递归实现

template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool EraseR(const K& key)//递归删除数据{return _EraseR(_root, key);}bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}else if (root->_key < key){_EraseR(root->_rchild, key);}else if (root->_key > key){_EraseR(root->_lchild, key);}else{Node* del = root;if (root->_lchild == root->_rchild && root->_lchild == nullptr)//删除的节点为叶子节点{//释放节点空间delete root;//将其父节点指向的自身的指针置空root = nullptr;}else if (root->_rchild == nullptr)//删除的节点右孩子为空,左孩子不为空{//将删除节点的左孩子交给其父节点root = root->_lchild;//释放节点空间delete del;del = nullptr;}else if (root->_lchild == nullptr)//删除的节点左孩子为空,右孩子不为空{//将删除节点的右孩子交给其父节点root = root->_rchild;//释放节点空间delete del;del = nullptr;}else//删除的节点左右孩子都不为空,要找到删除节点的左子树的最大节点或右子树的最小节点将其替换{//这里找要删除节点的右子树的最小节点（左子树的最大节点也可）Node* minright = del->_rchild; // 记录右子树的最小节点while (minright->_lchild)//查找右子树的最小节点{minright = minright->_lchild;}root->_key = minright->_key;//将找到的节点替换要删除的节点return _EraseR(root->_rchild, root->_key);//继续递归删除其右子树中用来替换的节点}return true;}}private:Node* _root = nullptr;//根节点
};

 

2.5 模拟实现二叉搜索树的全部代码

#include<iostream>
using namespace std;template<class K>
struct BSTreeNode//节点
{BSTreeNode<K>* _lchild;BSTreeNode<K>* _rchild;K _key;BSTreeNode(const K& key):_lchild(nullptr),_rchild(nullptr),_key(key){}
};template<class K>
class BSTree 
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key)//插入数据{if (_root == nullptr)//如果根节点为空就直接插入{_root = new Node(key);_root->_key = key;return true;}Node* cur = _root;//使用cur遍历二叉树找到合适的插入位置Node* parent = cur;//记录cur的父节点while (cur){parent = cur;if (key < cur->_key){cur = cur->_lchild;}else if (key > cur->_key){cur = cur->_rchild;}else{return false;//这里创建的二叉搜索树不允许出现值的冗余}}cur = new Node(key);//创建//将创建的节点链接到二叉树上if (key < parent->_key){parent->_lchild = cur;}else{parent->_rchild = cur;}return true;}bool InsertR(const K& key)//插入数据(递归){return _InsertR(_root, key);}private:bool _InsertR(Node*& root,const K& key)//这里使用指针的引用用来直接修改其父节点指针的指向{if (root == nullptr){root = new Node(key);return true;}if (root->_key > key){_InsertR(root->_lchild, key);}else if (root->_key < key){_InsertR(root->_rchild, key);}else{return false;}}public:void InOrder()//中序遍历{_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == NULL)//如果是空树就直接结束{return;}_InOrder(root->_lchild);//先递归遍历其左子树cout << root->_key << " ";//再遍历其根节点_InOrder(root->_rchild);//最后递归遍历其右子树}public:bool Find(const K& key)//查找数据{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_rchild;}else if (cur->_key > key){cur = cur->_lchild;}else{return true;}}return false;}bool Erase(const K& key)//删除数据{Node* cur = _root;//使用cur遍历二叉树找到要删除元素的位置Node* parent = cur;//记录cur的父节点while (cur)//寻找需要删除的节点{if (cur->_key < key){parent = cur;cur = cur->_rchild;}else if (cur->_key > key){parent = cur;cur = cur->_lchild;}else//找到了,开始删除{if (cur->_lchild == cur->_rchild && cur->_lchild == nullptr)//删除的节点为叶子节点{if (parent == cur)//删除的是根节点{_root = nullptr;//更新根节点}//将其父节点指向的自身的指针置空else if (parent->_lchild == cur){parent->_lchild = nullptr;}else{parent->_rchild = nullptr;}//释放节点空间delete cur;cur = nullptr;}else if (cur->_rchild == nullptr)//删除的节点右孩子为空,左孩子不为空{if (parent == cur)//删除的是根节点{_root = cur->_lchild;//更新根节点}//将删除节点的左孩子交给其父节点else if (parent->_lchild == cur){parent->_lchild = cur->_lchild;}else{parent->_rchild = cur->_lchild;}//释放节点空间delete cur;cur = nullptr;}else if (cur->_lchild == nullptr)//删除的节点左孩子为空,右孩子不为空{if (parent == cur)//删除的是根节点{_root = cur->_rchild;//更新根节点}//将删除节点的右孩子交给其父节点else if (parent->_lchild == cur){parent->_lchild = cur->_rchild;}else{parent->_rchild = cur->_rchild;}//释放节点空间delete cur;cur = nullptr;}else//删除的节点左右孩子都不为空,要找到删除节点的左子树的最大节点或右子树的最小节点可将其替换{//这里找要删除节点的左子树的最大节点（右子树的最小节点也可）Node* maxleft = cur->_lchild; // 记录左子树的最大节点Node* pmaxleft = cur;//记录左子树的最大节点的父节点while (maxleft->_rchild)//查找左子树的最大节点{pmaxleft = maxleft;maxleft = maxleft->_rchild;}//将找到的节点替换要删除的节点cur->_key = maxleft->_key;if (pmaxleft->_lchild == maxleft){pmaxleft->_lchild = maxleft->_lchild;}else{pmaxleft->_rchild = maxleft->_lchild;}//释放节点空间delete maxleft;maxleft = nullptr;}return true;}}return false;//没找到要删除的节点}bool EraseR(const K& key)//递归删除数据{return _EraseR(_root, key);}private:bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}else if (root->_key < key){_EraseR(root->_rchild, key);}else if (root->_key > key){_EraseR(root->_lchild, key);}else{Node* del = root;if (root->_lchild == root->_rchild && root->_lchild == nullptr)//删除的节点为叶子节点{//释放节点空间delete root;//将其父节点指向的自身的指针置空root = nullptr;}else if (root->_rchild == nullptr)//删除的节点右孩子为空,左孩子不为空{//将删除节点的左孩子交给其父节点root = root->_lchild;//释放节点空间delete del;del = nullptr;}else if (root->_lchild == nullptr)//删除的节点左孩子为空,右孩子不为空{//将删除节点的右孩子交给其父节点root = root->_rchild;//释放节点空间delete del;del = nullptr;}else//删除的节点左右孩子都不为空,要找到删除节点的左子树的最大节点或右子树的最小节点将其替换{//这里找要删除节点的右子树的最小节点（左子树的最大节点也可）Node* minright = del->_rchild; // 记录右子树的最小节点while (minright->_lchild)//查找右子树的最小节点{minright = minright->_lchild;}root->_key = minright->_key;//将找到的节点替换要删除的节点return _EraseR(root->_rchild, root->_key);//继续递归删除其右子树中用来替换的节点}return true;}}private:Node* _root = nullptr;//根节点
};

---

本期博客到这里就结束了，代码量较大，还请各位仔细分析呀

我们下期见~