【C++】搜索二叉树底层实现

目录

一，概念

二，实现分析

1.  插入

（1.）非递归版本 

 （2.）递归版本

 2. 打印搜索二叉树

3.查找函数

（1.）非递归版本

（2.）递归版本

4. 删除函数（重难点） 

易错点分析，包你学会

（1.）删除目标，没有左右孩子

（2.）删除目标，只有一个孩子

（3.）删除目标，有两个孩子

代码

（1.）非递归版本 

（2.）递归版本

5. 析构函数

6.拷贝构造 

 三，应用

 四，搜索二叉树的缺陷及优化

五，代码汇总

结语

---

一，概念

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

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

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

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

为啥又被称作二叉排序树呢？ 当该树被层序遍历时，就是升序。

二，实现分析

实验例子：

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

1.  插入

（1.）非递归版本 

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

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

 比较简单这里就直接放代码：

template <class K>
class BinarySeaTree_node
{typedef BinarySeaTree_node<K> BST_node;
public:BinarySeaTree_node(const K& val): _val(val),_left(nullptr),_right(nullptr){}K _val;BST_node* _left;BST_node* _right;
};template <class T>
class BSTree
{typedef BinarySeaTree_node<T> BST_node;
private:BST_node* root = nullptr;public:bool Insert(const T& val){BST_node* key = new BST_node(val);BST_node* cur = root;BST_node* parent = nullptr;while (cur){if (key->_val < cur->_val){parent = cur;cur = cur->_left;}else if (key->_val > cur->_val){parent = cur;cur = cur->_right;}else{return 0;}}// 查询好位置后，建立链接if (!root){root = key;return 0;}if (key->_val > parent->_val){parent->_right = key;}else{parent->_left = key;}return 1;}
};

 （2.）递归版本

这里面整了个活，大家注意了!!!

bool Re_Insert(const T& val){  return Re_Insert_table(root, val);}bool Re_Insert_table(BST_node*& node, const T& val){if (node == nullptr){node = new BST_node(val);return 1;}if (val < node->_left){return Re_Insert_table(node->_left, val);}else if (val > node->_right){ return Re_Insert_table(node->_right, val);}else{return 0;}}

这里方便大家理解，我给大家花一个递归展开图。

 2. 打印搜索二叉树

 

插入的具体过程如下：

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

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

这里也是仅做代码分享： 

void Print_table() { Re_Print(root); }void Re_Print(const BST_node* node){if (node == nullptr)return;Re_Print(node->_left);cout << node->_val << " ";Re_Print(node->_right);}

3.查找函数

思路：其实也没啥思路，比父结点小，就找左边，否则找右边。 

（1.）非递归版本

BST_node* Find(const T& val){//直接跟寻找位置一样BST_node* parent = nullptr;BST_node* cur = root; // 以返回cur的方式返回while (cur)   // 非递归版本{if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{return cur;}}return cur;}

（2.）递归版本

BST_node* Re_Find(const T& val){   return Re_Find_table(root, val); }BST_node* Re_Find_table(BST_node* node, const T& val){if (node == nullptr)return nullptr;if (val < node->_val){return Re_Find_table(node->_left, val);}else if (val > node->_val){return Re_Find_table(node->_right, val);}else{return node;}}

4. 删除函数（重难点） 

我们简单寻找了一下思路，如下：

但这些思路只是大概方向，其中藏着许多的坑点，诺接下来我来带大家，对这些易错点进行分析。

首先是查询到目标：

这个比较简单，这里不做解释。 

       //首先寻找到目标,并且记录到parentBST_node* parent = nullptr;BST_node* cur = root;while (cur){if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{break;}}if (!cur){return 0;}

易错点分析，包你学会

（1.）删除目标，没有左右孩子

 

（2.）删除目标，只有一个孩子

一般的思路： 

 但，这是有漏洞的！

诺：

（3.）删除目标，有两个孩子

 好啦，前菜上完了来看看，本次的大菜。

代码

（1.）非递归版本 

bool Erase(const T& val){//首先寻找到指定值,并且记录到parentBST_node* parent = nullptr;BST_node* cur = root;while (cur){if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{break;}}if (!cur){return 0;}// 查询成功,开始删除if (!cur->_left && !cur->_right) // cur没有左右孩子{   // 当要删除目标是根if (cur == root){root = nullptr;delete cur;}// 判断cur是左右孩子else if (cur->_val < parent->_val){parent->_left = nullptr;delete cur;}else{parent->_right = nullptr;delete cur;}return 1;}else if (!cur->_left || !cur->_right)  // 只有一个孩子{if (!parent)  // 判断是否是目标是根{root = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}// 判断cur为啥孩子else if (cur->_val < parent->_val) // 左侧{parent->_left = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}else                          // 右侧{parent->_right = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}}else   // 有2个孩子{  // 使用左侧最大的孩子来领养// 寻找左侧最大BST_node* maxnode = cur->_left;BST_node* max_parent = cur;while (maxnode->_right){max_parent = maxnode;maxnode = maxnode->_right;}// 现在又进入一种特殊情况,1.max_parent就没进入循环，2.进入了循环if (max_parent == cur){max_parent->_left = maxnode->_left;}else{max_parent->_right = maxnode->_left;}// 值转移cur->_val = maxnode->_val;delete maxnode;}return 1;}

（2.）递归版本

bool Re_Erease( const T& val){return Re_Erease_table(root, val);}bool Re_Erease_table(BST_node*& node, const T& val){// 首先我们先找到值if (node == nullptr){return 0; // 如果访问到了空，则说明删除失败，原因是：不存在}if (val < node->_val){return Re_Erease_table(node->_left, val);}else if (val > node->_val){return Re_Erease_table(node->_right, val);}else{// 开始删除目标数据。方法如下；// 1. 就按照非递归的思路，不用改多少代码 // 2. 使用递归方法，优势就是代码简洁// 这里使用方法2BST_node* del = node;  // 保存每次访问的对象，如果是目标，就备份好了if (node->_left == nullptr){node = node->_right;}else if (node->_right == nullptr){node = node->_left;}else{//处理左右都有孩子的目标// 左侧查找最大值，右侧查找最小值BST_node* max_node = node->_left;while (max_node->_right){max_node = max_node->_right;}// 完成循环后，max_node最多有左孩子，然后数据交换，我们以目标左侧树为起点// 再次递归删除替换数据。swap(max_node->_val, node->_val);return Re_Erease_table(node->_left, val); //已经完成删除，就直接退出，以免触发删除delete}			//处理前两种情况delete del;}}

5. 析构函数

思路：

~BSTree(){  Distroy_Re(root);root = nullptr;   }
void Distroy_Re(BST_node*& node) // 我们采用递归删除{if (node == nullptr)return ;// 先处理左右孩子Distroy_Re(node->_left);Distroy_Re(node->_right);delete node;node = nullptr;}

6.拷贝构造 

    // 我们实现了拷贝构造，默认构造函数则不会生成 // 解决方案：1.实现构造函数 2.使用default关键字，强制生成默认构造BSTree()                 {}// BSTree() = defaultBSTree(const BSTree& Tree) // 拷贝构造{root = copy(Tree.root);}BST_node* copy(BST_node* root){if (root == nullptr)return nullptr;BST_node* new_node = new BST_node(root->_val);new_node->_left = copy(root->_left);new_node->_right = copy(root->_right);return new_node;}

 三，应用

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到

的值。

比如： 给一个单词word，判断该单词是否拼写正确，具体方式如下：以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：

比如 英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；

再比如 统计单词次数，统计成功后，给定单词就可快速找到其出现的次数， 单词与其出现次数就是<word, count>就构成一种键值对（这个比较简单，修改一下即可）

 四，搜索二叉树的缺陷及优化

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最坏情况：N

平均情况：O(logN)

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL树和红黑树就可以上场了。

五，代码汇总

namespace key
{
template <class K>
class BinarySeaTree_node
{typedef BinarySeaTree_node<K> BST_node;
public:BinarySeaTree_node(const K& val): _val(val),_left(nullptr),_right(nullptr){}K _val;BST_node* _left;BST_node* _right;
};template <class T>
class BSTree
{
public:typedef BinarySeaTree_node<T> BST_node;// 我们实现了拷贝构造，默认构造函数则不会生成 // 解决方案：1.实现构造函数 2.使用default关键字，强制生成默认构造BSTree(){}// BSTree() = defaultBSTree(const BSTree& Tree) // 拷贝构造{root = copy(Tree.root);}BSTree<T>& operator=(BSTree<T> t){swap(root, t.root);return *this;}BST_node* copy(BST_node* root){if (root == nullptr)return nullptr;BST_node* new_node = new BST_node(root->_val);new_node->_left = copy(root->_left);new_node->_right = copy(root->_right);return new_node;}bool Re_Insert(const T& val) { return Re_Insert_table(root, val); }void Re_Print() { Re_Print_table(root); }bool Re_Erease(const T& val) { return Re_Erease_table(root, val); }BST_node* Re_Find(const T& val) { return Re_Find_table(root, val); }bool Insert(const T& val){BST_node* key = new BST_node(val);BST_node* cur = root;BST_node* parent = nullptr;while (cur){if (key->_val < cur->_val){parent = cur;cur = cur->_left;}else if (key->_val > cur->_val){parent = cur;cur = cur->_right;}else{return 0;}}// 查询好位置后，建立链接if (!root){root = key;return 0;}if (key->_val > parent->_val){parent->_right = key;}else{parent->_left = key;}return 1;}BST_node* Find(const T& val){//直接跟寻找位置一样BST_node* parent = nullptr;BST_node* cur = root; // 以返回cur的方式返回while (cur)   // 非递归版本{if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{return cur;}}return cur;}bool Erase(const T& val){//首先寻找到指定值,并且记录到parentBST_node* parent = nullptr;BST_node* cur = root;while (cur){if (val < cur->_val){parent = cur;cur = cur->_left;}else if (val > cur->_val){parent = cur;cur = cur->_right;}else{break;}}if (!cur){return 0;}// 查询成功,开始删除if (!cur->_left && !cur->_right) // cur没有左右孩子{   // 当要删除目标是根if (cur == root){root = nullptr;delete cur;}// 判断cur是左右孩子else if (cur->_val < parent->_val){parent->_left = nullptr;delete cur;}else{parent->_right = nullptr;delete cur;}return 1;}else if (!cur->_left || !cur->_right)  // 只有一个孩子{if (!parent)  // 判断是否是目标是根{root = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}// 判断cur为啥孩子else if (cur->_val < parent->_val) // 左侧{parent->_left = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}else                          // 右侧{parent->_right = cur->_left != nullptr ? cur->_left : cur->_right;delete cur;}}else   // 有2个孩子{  // 使用左侧最大的孩子来领养// 寻找左侧最大BST_node* maxnode = cur->_left;BST_node* max_parent = cur;while (maxnode->_right){max_parent = maxnode;maxnode = maxnode->_right;}// 现在又进入一种特殊情况,1.max_parent就没进入循环，2.进入了循环if (max_parent == cur){max_parent->_left = maxnode->_left;}else{max_parent->_right = maxnode->_left;}// 值转移cur->_val = maxnode->_val;delete maxnode;}return 1;}~BSTree(){Distroy_Re(root);root = nullptr;}protected:bool Re_Insert_table(BST_node*& node, const T& val){if (node == nullptr){node = new BST_node(val);return 1;}if (val < node->_val){return Re_Insert_table(node->_left, val);}else if (val > node->_val){return Re_Insert_table(node->_right, val);}else{return 0;}}void Re_Print_table(const BST_node* node){if (node == nullptr)return;Re_Print_table(node->_left);cout << node->_val << " ";Re_Print_table(node->_right);}BST_node* Re_Find_table(BST_node* node, const T& val){if (node == nullptr)return nullptr;if (val < node->_val){return Re_Find_table(node->_left, val);}else if (val > node->_val){return Re_Find_table(node->_right, val);}else{return node;}}bool Re_Erease_table(BST_node*& node, const T& val){// 首先我们先找到值if (node == nullptr){return 0; // 如果访问到了空，则说明删除失败，原因是：不存在}if (val < node->_val){return Re_Erease_table(node->_left, val);}else if (val > node->_val){return Re_Erease_table(node->_right, val);}else{// 开始删除目标数据。方法如下；// 1. 就按照非递归的思路，不用改多少代码 // 2. 使用递归方法，优势就是代码简洁// 这里使用方法2BST_node* del = node;  // 保存每次访问的对象，如果是目标，就备份好了if (node->_left == nullptr){node = node->_right;}else if (node->_right == nullptr){node = node->_left;}else{//处理左右都有孩子的目标// 左侧查找最大值，右侧查找最小值BST_node* max_node = node->_left;while (max_node->_right){max_node = max_node->_right;}// 完成循环后，max_node最多有左孩子，然后数据交换，我们以目标左侧树为起点// 再次递归删除替换数据。swap(max_node->_val, node->_val);return Re_Erease_table(node->_left, val); //已经完成删除，就直接退出，以免触发删除delete}// 查找到删除数据delete del;}}void Distroy_Re(BST_node*& node) // 我们采用递归删除{if (node == nullptr)return;// 先处理左右孩子Distroy_Re(node->_left);Distroy_Re(node->_right);delete node;node = nullptr;}
private:BST_node* root = nullptr;};
}

结语

   本小节就到这里了，感谢小伙伴的浏览，如果有什么建议，欢迎在评论区评论，如果给小伙伴带来一些收获请留下你的小赞，你的点赞和关注将会成为博主创作的动力