当前位置： 首页 > news >正文

【C++、数据结构】二叉排序树（二叉查找树、二叉搜索树）（图解+完整代码）

news 2024/10/23 2:15:02

目录

[⚽1.什么是二叉排序树]

[🏐2.构建二叉排序树]

[🏀3.二叉排序树的查找操作]

[🥎4.二叉排序树的删除]

[🎱5.完整代码]

⚽1.什么是二叉排序树

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

  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树
    在这里插入图片描述

🏐2.构建二叉排序树

  1. 二叉搜索树的模拟实现

2.1 结点的声明

//描述二分查找树的一个结点
template<class K>
struct BSTNode
{K _key;						//数据域struct BSTNode* _left;		//指向左子树指针struct BSTNode* _right;		//指向右子树指针BSTNode(K key):_key(key),_left(nullptr),_right(nullptr){}
};

2.2 基本的几个成员函数

template<class K>class BSTree
{               typedef BSTreeNode<K> Node;
private://没有参数是不能递归的void DestroyTree(Node* root){if (root == nullptr)return;DestroyTree(root->_left);DestroyTree(root->_right);delete root;}Node* CopyTree(Node* root){if (root == nullptr)return nullptr;Node* copyNode = new Node(root->_key);copyNode->_left = CopyTree(root->_left);copyNode->_right = CopyTree(root->_right);return copyNode;}
public://强制编译器自己生成构造函数 -- C++11BSTree() = default;/*BSTree():_root(nullptr){}*///前序遍历递归拷贝BSTree(const BSTree<K>& t){_root = CopyTree(t._root);}//t1 = t2; -- 任何赋值重载都可以用现代写法BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}~BSTree(){DestroyTree(_root);_root = nullptr;}

构造函数：

  • 这里我们可以采用传统的方法
  • 直接初始化成员变量
  • 也可以用C++11的语法default
  • 强制编译器自己生成构造函数

拷贝构造：

  • 这里我们用了递归的方式进行拷贝
  • 采用根 - 左 - 右 的前序遍历的递归方式对整个二叉树拷贝
  • 最后将跟结点返回

析构函数：

  • 析构函数我们这里也是采用递归的方式进行一个一个结点析构
  • 同样的我们再嵌套一个子函数
  • 也是采用类似前序遍历的方法将整个二叉树释放掉

采用递归方式的缺点就是如果数的结点个数足够多的时候，就会有爆栈的风险！！

2.3 插入操作

假设我们有以下数据，我们按从左到右的顺序来构建二叉排序树：

  1. 首先，将8作为根节点
  2. 插入3，由于3小于8，作为8的左子树
  3. 插入10，由于10大于8，作为8的右子树
  4. 插入1，由于1小于8，进入左子树3，1又小于3，则1为3的左子树
  5. 插入6，由于6小于8，进入左子树3，6又大于3，则6为3的右子树
  6. 插入14，由于14大于8，进入右子树10，14又大于10，则14为10的右子树
  7. 插入4，由于4小于8，进入左子树3，4又大于3，进入右子树6，4还小于6，则4为6的左子树
  8. 插入7，由于7小于8，进入左子树3，7又大于3，进入右子树6，7还大于于6，则7为6的右子树
  9. 插入13，由于13大于8，进入右子树10，又13大于10，进入右子树14,13小于14，则13为14的左子树

经过以上的逻辑，这棵二叉排序树构建完成。

我们可以看出：

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

没错，这棵二叉树中序遍历结果为：

  • 二叉树中序遍历结果为升序，左节点<根节点<右节点

插入思路：

  • 从根结点开始遍历。（不能相等哦，直接结束就好）
  • key<遍历结点的值,则遍历其左子树；key>遍历结点的值,则遍历其右子树
  • 直到遍历到某个叶子结点
  • 插入：比叶子节点小，插入左子树，反之，右子树。

根据以上思路，我们其实就可以写出代码了，构建的过程其实就是插入的过程：

//插入函数
bool Insert(const K key)
{Node* newnode = new Node(key);//空树时if (_root == NULL){_root = newnode;return true;}Node* cur = _root;			//用来遍历Node* parent = nullptr;		//记录上一个节点while (cur){parent = cur;//key< 结点值，遍历其左子树if (key < cur->_key){cur = cur->_left;}//key> 结点值，遍历其右子树else if (key > cur->_key){cur = cur->_right;}//不能插入相同的else{return false;}}if (key < parent->_key){parent->_left = newnode;}if (key > parent->_key){parent->_right = newnode;}return true;
}

🏀3.二叉排序树的查找操作

它既然也叫二叉查找树，那想必会非常方便我们查找吧！它的操作并不是把中序遍历的结果存入数组，然后在有序数组里查找，而是直接在树上查找。

  1. 首先，访问根节点8
  2. 根据性质，7<8，访问8的左子树
  3. 访问到了3，7>3，访问3的右子树
  4. 访问到了6，继续访问6的右子树
  5. 访问到了7，刚好找到啦！

显然，它的效率会比在无序数组中挨着查找快多了吧！我们直接上代码。

	//查找bool Find(const K& key){Node* cur = _root;while (cur){//往左子树找if (key<cur->_key){cur = cur->_left;}//往右子树找else if (key>cur->_key){cur = cur->_right;}//找到了else{return true;	}}return false;	//没有找到}

🥎4.二叉排序树的删除（动图演示）

二叉搜索树的删除函数是最难实现的，若是在二叉树当中没有找到待删除结点，则直接返回 false 表示删除失败即可，但若是找到了待删除结点，此时就有以下三种情况：

  • 待删除结点的左子树为空(因为放第一个，所以包含左子树和无子树)
  • 待删除结点的右子树为空
  • 待删除结点的左右子树均不为空
    下面进行一对一处理：

情况一：左子树为空

（1）待删除结点的左子树为空，即右子树不为空,或者不为空

  • 待删除结点的左子树为空(因为放第一个，所以包含左子树和无子树)
  • 若待删除结点的左子树为空，那么当我们在二叉搜索树当中找到该结点后，只需先让其父结点指向该结点的右孩子结点，然后再将该结点释放便完成了该结点的删除，进行删除操作后仍保持二叉搜索树的特性

注意：如果删除的节点为叶子节点，即待删除节点左右子树均为空，这个情况包含在这种情况里面

动图演示（演示其中一种情况）：删除10
在这里插入图片描述

  • 待删除结点不是根结点，此时parent不为nullptr
  • 待删除结点是其父结点的左孩子，父结点的左指针指向待删除结点的右子树即可
  • 反之，父结点的右指针指向待删除结点的右子树即可

下面只是删除部分的代码哦，看下面完整代码

//(1)删除节点只有0-1个孩子的时候(只有右孩子或者没有孩子)
//  这里包括了  cur->_left=nullptr&&cur->_right=nullptr的情况，就是没有孩子的情况
if (cur->_left == nullptr)
{//删除的是根节点//parent==nullptr;if (cur == _root){_root = cur->_right;}else{//cur是parent的左子树，把cur的右子树托孤给parent的左/右子树if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;		//删除节点return true;
}

情况二：右子树为空

（2）待删除结点的右子树为空，即左子树不为空

  • 若待删除结点的右子树为空，那么当我们在二叉搜索树当中找到该结点后
  • 只需先让其父结点指向该结点的左孩子结点，然后再将该结点释放便完成了该结点的删除，进行删除操作后仍需要保持二叉搜索树的特性

动图演示（演示其中一种情况）：删除14
在这里插入图片描述

  • 待删除结点不是根结点，此时parent不为nullptr
  • 待删除结点是其父结点的右孩子,父结点的左指针指向待删除结点的左子树即可
  • 反之，父结点右指针指向待删除结点的左子树即可

下面只是删除部分的代码哦，看下面完整代码

//(2) 删除节点只有左孩子
else if (cur->_right == nullptr)
{//删除的是根节点//parent==nullptr;if (cur == _root){_root = cur->_right;}else{//cur是parent的左子树，把cur的左子树托孤给parent的左/右子树if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;		//删除节点return true;
}

情况三：两个左右子树都不为空

（3）待删除结点的左右子树均不为空

若待删除结点的左右子树均不为空，那么当我们在二叉搜索树当中找到该结点后，可以使用替换法进行删除

有两种替换方法：

（1）删除结点左子树当中值最大的结点
（2）删除结点右子树当中值最小的结点

关于两种替换方法：
替换方法(1):要删的结点(8)的左子树的最大结点
那就是用7来顶替位置

此时7从叶子结点“升迁”到了根节点（只是刚好要删除的结点为根节点，如果删除3，就替换3的位置）

替换方法(2):要删的结点(8)的右子树的最小结点
那就是用10来顶替位置

下面演示我们用删除结点右子树当中值最小的结点来替换。

动图演示（演示其中一种情况）：删除3

显然删除结点右子树当中值最小的结点为4

  • 怎么找到（删除结点右子树当中值最小的结点）？
    • 1.用minParent记录minRight的父节点
    • 2.minRight从删除节点的右子树开始
    • 3.一直往左找
//这里找右子树的最小节点替换cur
Node* minParent = cur;
Node* minRight = cur->_right;//从右子树开始找
while (minRight->_left)		//当然一直往左找
{minParent = minRight;minRight = minRight->_left;
}

下面只是删除部分的代码哦，看下面完整代码

//(3)删除节点左右孩子都有
//替换法，然后删除(找右子树的最小节点或者找到左子树的最大节点)
else
{//这里找右子树的最小节点替换curNode* minParent = cur;Node* minRight = cur->_right;//从右子树开始找while (minRight->_left)		//当然一直往左找{minParent = minRight;minRight = minRight->_left;}//开始替换//1.替换值cur->_key = minRight->_key;//2.连接minParent和minRight（把minRight右边连上就OK）//minRight是minParent的左节点if (minRight == minParent->_left)minParent->_left = minRight->_right;//minRight是minParent的右节点elseminParent->_right = minRight->_right;//3.删除节点delete minRight;return true;
}

删除代码

//删除
bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){//往左走if (key < cur->_key){parent = cur;cur = cur->_left;}//往右走else if(key>cur->_key){parent = cur;cur = cur->_right;}//找到了，开删else{//(1)删除节点只有0-1个孩子的时候(只有右孩子或者没有孩子)//  这里包括了  cur->_left=nullptr&&cur->_right=nullptr的情况，就是没有孩子的情况if (cur->_left == nullptr){//删除的是根节点//parent==nullptr;if (cur == _root){_root = cur->_right;}else{//cur是parent的左子树，把cur的右子树托孤给parent的左/右子树if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;		//删除节点return true;}//(2) 删除节点只有左孩子else if (cur->_right == nullptr){//删除的是根节点//parent==nullptr;if (cur == _root){_root = cur->_right;}else{//cur是parent的左子树，把cur的左子树托孤给parent的左/右子树if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;		//删除节点return true;}//(3)删除节点左右孩子都有//替换法，然后删除(找右子树的最小节点或者找到左子树的最大节点)else{//这里找右子树的最小节点替换curNode* minParent = cur;Node* minRight = cur->_right;//从右子树开始找while (minRight->_left)		//当然一直往左找{minParent = minRight;minRight = minRight->_left;}//开始替换//1.替换值cur->_key = minRight->_key;//2.连接minParent和minRight（把minRight右边连上就OK）//minRight是minParent的左节点if (minRight == minParent->_left)minParent->_left = minRight->_right;//minRight是minParent的右节点elseminParent->_right = minRight->_right;//3.删除节点delete minRight;return true;}}}return false;
}

🎱5.完整代码(非递归)

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
//描述二分查找树的一个结点
template<class K>
struct BSTNode
{K _key;				//数据域struct BSTNode* _left;		//指向左子树指针struct BSTNode* _right;		//指向右子树指针BSTNode(K key):_key(key),_left(nullptr),_right(nullptr){}
};
template<class K>
class BSTree
{typedef BSTNode<K> Node;
private:Node* _root;void Destory(Node* root){if (root == nullptr) return;Destory(root->_left);Destory(root->_right);delete(root);}//拷贝函数(递归)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 _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_key<< endl;_InOrder(root->_right);}
public://构造函数BSTree() {};//拷贝构造BSTree(const BSTree<K>& t) {_root = Copy(t._root);}//析构~BSTree(){Destory(_root);		//调用销毁函数_root = nullptr;}//插入函数bool Insert(const K key){Node* newnode = new Node(key);//空树时if (_root == NULL){_root = newnode;return true;}Node* cur = _root;			//用来遍历Node* parent = nullptr;		//记录上一个节点while (cur){parent = cur;//key< 结点值，遍历其左子树if (key < cur->_key){cur = cur->_left;}//key> 结点值，遍历其右子树else if (key > cur->_key){cur = cur->_right;}//不能插入相同的else{return false;}}if (key < parent->_key){parent->_left = newnode;}if (key > parent->_key){parent->_right = newnode;}return true;}//查找bool Find(const K& key){Node* cur = _root;while (cur){//往左子树找if (key<cur->_key){cur = cur->_left;}//往右子树找else if (key>cur->_key){cur = cur->_right;}//找到了else{return true;	}}return false;	//没有找到}//删除bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){//往左走if (key < cur->_key){parent = cur;cur = cur->_left;}//往右走else if(key>cur->_key){parent = cur;cur = cur->_right;}//找到了，开删else{//(1)删除节点只有0-1个孩子的时候(只有右孩子或者没有孩子)//  这里包括了  cur->_left=nullptr&&cur->_right=nullptr的情况，就是没有孩子的情况if (cur->_left == nullptr){//删除的是根节点//parent==nullptr;if (cur == _root){_root = cur->_right;}else{//cur是parent的左子树，把cur的右子树托孤给parent的左/右子树if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;		//删除节点return true;}//(2) 删除节点只有左孩子else if (cur->_right == nullptr){//删除的是根节点//parent==nullptr;if (cur == _root){_root = cur->_right;}else{//cur是parent的左子树，把cur的左子树托孤给parent的左/右子树if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;		//删除节点return true;}//(3)删除节点左右孩子都有//替换法，然后删除(找右子树的最小节点或者找到左子树的最大节点)else{//这里找右子树的最小节点替换curNode* minParent = cur;Node* minRight = cur->_right;//从右子树开始找while (minRight->_left)		//当然一直往左找{minParent = minRight;minRight = minRight->_left;}//开始替换//1.替换值cur->_key = minRight->_key;//2.连接minParent和minRight（把minRight右边连上就OK）//minRight是minParent的左节点if (minRight == minParent->_left)minParent->_left = minRight->_right;//minRight是minParent的右节点elseminParent->_right = minRight->_right;//3.删除节点delete minRight;return true;}}}return false;}//中序遍历-有序void InOrder(){_InOrder(_root);cout << endl;}};int main()
{BSTree<int> bst;//插入int arr[] = { 8,3,10,1,6,14,4,7,13 };int n = sizeof(arr) / sizeof(arr[0]);for (int i = 0; i < n; i++){bst.Insert(arr[i]);}//中序遍历bst.InOrder();//查找//int p = 0;//cout << "输入要找的数：";//cin >> p;	//if (bst.Find(p))//{//	cout << "找到了" << endl;//}//else//{//	cout << "没有找到" << endl;//}//删除//1.测试没有孩子//bst.Erase(10);//2.测试一个孩子//bst.Erase(14);//3.测试有两个孩子//bst.Erase(3);bst.InOrder();return 0;
}

递归版本（扩展）

递归版本理解起来就相对与非递归版本更好理解了，直接看代码

（1）查找：

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

逐层递归查找即可…

（2）插入：（重点）

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){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}
}

该如何链接上树呢？

  • 可以在递归的参数中多一个父亲结点，每次递归都更新一下Parent，然后再带到下一层递归
  • 显然这样在学过C++之后就麻烦了

用了一个指针的引用就解决了问题

  • 因为root的值此时是空，但是root同时是这个结点里的_left这个指针的别名
  • 相当于当前结点的父节点的左指针的别名
  • 意味着此时再去给root赋值就是去给该结点父亲结点的_left赋值
  • 那么此时就链接起来了

（3）删除：

bool EraseR(const K& key)
{return _EraseR(_root, key);
}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;//root是要删除结点的左结点/右结点的别名if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* minRight = root->_right;while (minRight->_left){minRight = minRight->_left;}swap(root->_key, minRight->_key);return _EraseR(root->_right, key);//转换成在root->_right（右子树）中去删除key//这里删除这个key一定会走左为空的场景（找最小）}delete del;return true;}
}

相等时就开始删除了（递归只是用来查找要删除的数的位置）

  • root是要删除结点的左结点 / 右结点的别名

分三种情况删除：

  1. 要删除的结点左为空
  2. 要删除的结点右为空
  3. 要删除的结点左右都为空（替换法）

总的来说递归版本比非递归版本更容易理解，删除过程参考非递归删除过程……（有异曲同工之妙）


http://www.mrgr.cn/news/56436.html

相关文章：

  • html+css+js实现Notification 通知
  • 代码随想录算法训练营第51天｜101. 孤岛的总面积、102. 沉没孤岛、103. 水流问题、104.建造最大岛屿
  • 蓄电池在线监测系统 各大UPS铅酸蓄电池监测 保障安全
  • Shell 脚本从入门到精通：全面指南与学习资源
  • Rust小练习，编写井字棋
  • 结构化分析与设计（绪论）
  • C++入门知识
  • 【二刷hot100】day 4
  • Python程序设计 内置模块 随机函数
  • 【C++】— 一篇文章让你认识STL
  • Git的原理和使用（六）
  • 开源医疗管理的未来：参与码良诊所管理系统，助力智能医疗
  • 中国古代数学的杰出研究成果之一 - 杨辉三角 - 怎么用go、C++进行编程解决
  • 二叉树展开为链表
  • 代码随想录算法训练营第51天｜101. 孤岛的总面积、102. 沉没孤岛、103. 水流问题、104.建造最大岛屿
  • 集合框架16：HashMap的使用
  • C++编程语言：抽象机制：特殊运算符(Bjarne Stroustrup)
  • 容灾与云计算概念
  • Javascript基础面试题
  • Leetcode—1114. 按序打印【简单】（多线程）
  • http作业
  • 10.22软考初级网络管理员工重点之因特网与网络互联技术
  • 红黑树(创建 插入 测试验证)
  • 深入了解Java
  • 力扣 困难 52.N皇后II
  • ＜a-table＞行数据增加点击事件并获取点击行的数据+自定义button按事件