二叉搜索树概念详解

二叉搜索树的概念

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

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

二叉搜索树的操作(大致思路)

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

二叉搜索树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。

二叉搜索树的插入

插入的具体过程如下：
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

二叉搜索树的删除(最重点)

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点

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

形象地说,情况b\\c,我们就采取"托孤"的政策,将要删除的那个节点的一个孩子交给自己的父亲带(即爷爷带孙子),但是如果要删除那个节点有两个孩子(左右节点)的话,"爷爷"就忙不过来了,此时,我们需要换一种策略–>请保姆.
那么怎么找到这个保姆呢?首先我们要明确的一点是,在我们对搜索二叉树进行操作的时候,我们需要时刻保证搜索二叉树的性质是成立的–即跟比左子树大比右子树小.
我们是需要找到这个"保姆"将我们需要删除的那个节点交换,为了保持二叉搜索树的性质,我们就需要在他的子树中找到满足这种性质的节点来替换:即左子树中的最大节点(替换后肯定比原左子树中的每一个数都大,但是又比原右子树中的每一个树都小,完美符合性质),同样的,我们利用对称性原理不难发现,右子树的最小节点也是满足这个性质的
综上,我们只需要找到左子树的最右节点或者右子树的最左节点作为"保姆"替换掉要删除的目标节点即可.

手撕搜索二叉树代码

结点定义(以key型为例,KV型将在下一篇博客中介绍)

template<class k>
struct BSTreeNode
{BSTreeNode<k>* left;//定义左子树BSTreeNode<k>* right;//定义右子树k _key;//存储关键码BSTreeNode(const k& key)//构造函数:_key(key),_left(nullptr),_right(nullptr){}
}

树结构定义

上面我们已经把每个结点的结构定义出来了
这里我们需要把结点管理起来:

template<class k>class BSTree{typedef BSTreeNode<k> Node;//将结点名字重新命名,方便后续写代码public:BSTree() = default; BSTree(const BSTree<k>& t){}BSTree<k>& operator=(BSTree<k> t){}bool Insert(const k& key);bool Erase(const k& key);void InOrder();protected:Node* Copy(Node* root){}void Destroy(Node*& root{}void _InOrder(Node* root){}private:Node* _root = nullptr;};	

深拷贝构造函数与构造函数

编译器会自动给我们生成一个拷贝构造函数出来,但是这是浅拷贝,不是深拷贝.
因此,我们先写一个(深)拷贝构造出来,构造方式其实就类似于遍历,要使用递归的方法
一般来说,对于类中的函数递归,需要我们封装一下,才能将头节点传入
所以我们需要在protect域中写一个copy函数,然后再把构造函数接口开放给外面.
这里需要注意的是,如果我们写了拷贝构造而没有写默认构造(此时编译器已经不再会为我们自动创建构造函数了),编译会报错
有两种解决方式:

1. 手写一个默认构造函数
2. 使用default关键字(我们下面采用这种方式)

我们在下面的代码都进行了演示:

template<class k>
struct BSTree
{typedef BSTreeNode<k> Node; 
public:/*BSTree():_root(nullptr){}*/BSTree() = default; // 制定强制生成默认构造BSTree(const BSTree<k>& t)//拷贝构造封装{_root = Copy(t->_root);//利用this指针,得到拷贝后的树}
protect:Node* Copy(Node* root){if(Node* == nullptr)//如果递归到了空指针,则说明到底了{return nullptr;}//创建一个新的结点用来接收root的key:Node* newRoot = new Node(root->key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);//先创建,后链接return newRoot;//返回此时的跟结点,会与上一层的根节点链接.}
private:Node* _root = nullptr;void Destroy(Node*& root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}
}

赋值重载

既然都已经写了(深)拷贝构造了,那就直接把赋值重载也写了
这里我们直接采用更方便的"现代写法",即利用语法的机制,直接返回值:

BSTree<k>& operator=(BSTree<k> t)//传参进来的时候会拷贝构造,我们此时
{swap(_root, t._root);//这里的t是已经拷贝构造好的节点了,我们只需要交换他俩的值//就能直接窃取劳动成果了return *this;
}

析构函数

由于这里是树形结构,需要使用递归删除,而递归删除在类中一般都需要我们封装一层,才能将起始点传进去.

~BSTree(){Destroy(_root);//_root = nullptr;
}
protect:
void Destroy(Node*& root)//如果我们这里直接传引用的话,就可以省略上面的那句注释中的代码{if (root == nullptr)return;Destroy(root->_left);//先删除左子树Destroy(root->_right);//再删除右子树delete root;//最后删除根节点root = nullptr;//将根节点置空}

遍历(结果按从小到大遍历->中序遍历)

一样的,需要我们封装一层

public:void InOrder(){_InOrder(_root);cout << endl;}
protect:void _InOrder(Node* root){if(root == nullptr)//设置递归的终止条件.{return;}_InOrder(root->left);cout << root->key << " ";_InOrder(root->right);}	

增删查改

增加结点(插入)->循环版本

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;//如果是插入树中已经有的key值,则插入失败}}cur = new Node(key);// 再链接(首先要判断是父节点的左子树还是右子树)if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;//走到这里,则已经插入成功}

增加结点(插入)->递归版本

public:
bool InsertR(const k& key){return _InsertR(_root, key);}
protect:
bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}}

查找结点->循环版本

bool Find(const K& key)//该函数只需要返回是否能够找到即可,因此是bool类型的返回值{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;}

查找结点->递归版本

public:
bool FindR(const k& key){return _FindR(_root, key);}
protect:
bool _FindR(Node* root, const k& key){if (root == nullptr)return false;if (root->_key == key)return true;if (root->_key < key)return _FindR(root->_right, key);elsereturn _FindR(root->_left, key);}

删除结点->循环版本

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{// 删除// 1、左为空if (cur->_left == nullptr){if (cur == _root)//因为外面设置了parent,如果cur是跟节点的话,parent还是null,会发生错误,所以这里需要单独判断一下{_root = cur->_right;//直接把根节点给他的右子树的结点}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;} // 2、右为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 找右树最小节点替代，也可以是左树最大节点替代Node* pminRight = cur;//便于后续的"托孤"操作Node* minRight = cur->_right;while (minRight->_left){pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;//交换这个值if (pminRight->_left == minRight)//假如被换上去的那个结点还有右节点,则还需要"托孤"{pminRight->_left = minRight->_right;}else{pminRight->_right = minRight->_right;}delete minRight;//删除最小结点}return true;}}return false;}

删除结点->递归版本

private:
bool EraseR(const k& key){return _EraseR(_root, key);}
protect:
bool _EraseR(Node*& root, const k& key)//这里很巧妙地使用了引用{if (root == nullptr)return false;if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;// 开始准备删除if (root->_right == nullptr){root = root->_left;//这里的root是别名,因此可以直接这样用,不用找父节点}else if (root->_left == nullptr){root = root->_right;}else{Node* maxleft = root->_left;while (maxleft->_right){maxleft = maxleft->_right;}swap(root->_key, maxleft->_key);return _EraseR(root->_left, key);//交换了以后继续递归删除即可}delete del;return true;//走到这里说明已经删除完毕了}}

搜索二叉树代码完全版

#pragma once
#include<iostream>
using namespace std;// BinarySearchTree -- BSTreenamespace key
{template<class K>struct BSTreeNode{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}};template<class K>class BSTree{typedef BSTreeNode<K> Node;public:/*BSTree():_root(nullptr){}*/BSTree() = default; // 制定强制生成默认构造BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);//_root = nullptr;}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;}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;}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{// 删除// 1、左为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;} // 2、右为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 找右树最小节点替代，也可以是左树最大节点替代Node* pminRight = cur;Node* minRight = cur->_right;while (minRight->_left){pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (pminRight->_left == minRight){pminRight->_left = minRight->_right;}else{pminRight->_right = minRight->_right;}delete minRight;}return true;}}return false;}bool FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key){return _InsertR(_root, key);}bool EraseR(const K& key){return _EraseR(_root, key);}void InOrder(){_InOrder(_root);cout << endl;}protected:Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}void Destroy(Node*& root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key == key)return true;if (root->_key < key)return _FindR(root->_right, key);elsereturn _FindR(root->_left, key);}bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}}bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;// 开始准备删除if (root->_right == nullptr){root = root->_left;}else if (root->_left == nullptr){root = root->_right;}else{Node* maxleft = root->_left;while (maxleft->_right){maxleft = maxleft->_right;}swap(root->_key, maxleft->_key);return _EraseR(root->_left, key);}delete del;return true;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root = nullptr;};
}

总结

这篇文章写的都是搜索二叉树的K模型.
关于KV模型的代码手撕将在下一篇文章中,到时候查看我所写的博客即可.
希望大家学习了本篇博客后能够根据目录结构将代码全部重写一遍,只有自己写出来了才是真正的学会了.