C++进阶—二叉搜索树

news/2024/11/30 18:33:07/

目录

0. 前言

1. 二叉搜索树概念

2. 二叉搜索树操作

3. 二叉搜索树的实现

3.1 非递归实现插入操作Insert

3.2 二叉搜索树中序遍历递归实现（排序）

3.3 非递归实现查找操作Find

3.4 非递归实现删除操作Erase

3.5 递归实现插入操作InsertR

3.5 递归实现查找操作FindR

3.6 递归实现删除操作EraseR（递归引用的价值）

4.二叉搜索树的拷贝赋值析构&&其他操作

4.1 二叉树的拷贝构造

4.2 二叉搜索树的赋值

4.3 二叉搜索树的析构

4.4 二叉搜索树的其他操作

5. 二叉搜索树的性能分析

0. 前言

以下是前面有关二叉树的文章：

二叉树和堆

二叉树链式结构的实现

二叉树层序遍历

更新C++二叉树进阶是因为：

  1.         map和set特性需要先铺垫二叉搜索树，而二叉搜索树也是一种树形结构
  2.         二叉搜索树的特性了解，有助于更好的理解map和set的特性
  3.         二叉树中部分面试题稍微有点难度，在前面学习不容易接受，且时间长容易忘
  4.         有些OJ题使用C语言方式实现比较麻烦，比如有些地方要返回动态开辟的二维数组，非常麻烦。

因此最近有关二叉树搜索树的文章，是对二叉树部分进行收尾总结。

1. 二叉搜索树概念

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

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

 

2. 二叉搜索树操作

 

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

1. 二叉搜索树的查找

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

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

2. 二叉搜索树的插入具体过程如下：

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

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

如下插入0、9、16

3. 二叉搜索树的删除

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

  •         a. 要删除的结点无孩子结点
  •         b. 要删除的结点只有左孩子结点
  •         c. 要删除的结点只有右孩子结点
  •         d. 要删除的结点有左、右孩子结点

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

        假设删除的节点为cur，parent为cur的父节点，绘图分析

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

 

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

 

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

 

3. 二叉搜索树的实现

注：C++11新增用法，构造函数关键字default，强制生成默认构造

​
#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;template<class K>
class BSTreeNode {
public:BSTreeNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;
};//key
template<class K>
class BinarySearchTree {typedef BSTreeNode<K> Node;
public:/*BinarySearchTree() :_root(nullptr){}*///强制编译器生成默认构造 —— c++11用法，defaultBinarySearchTree() = default;
private:Node* _root = nullptr;
};

二叉受搜索树采用链式结构，左右孩子进行实现

3.1 非递归实现插入操作Insert

	bool Insert(const K& 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;}}if (parent->_key > key) {parent->_left = new Node(key);return true;}else{parent->_right = new Node(key);return true;}}

3.2 二叉搜索树中序遍历递归实现（排序）

二叉搜索树也叫做二叉排序树，因为其结构性质导致了按照中序遍历，便可以得到有序数据！

public：void InOrder() {_InOrder(_root);cout << endl;}private:void _InOrder(Node* root) {if (root == nullptr) {return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}

注：由于递归需要穿参，遍历二叉树左右子树，而首要传参为根节点，根节点便是this的成员变量，可以直接访问，且缺省参数不可以使用成员变量（缺省参数必须是常量），如果在外传参，需要使用getRoot获取根节点，在传递，使用不便，因此只需要在内部套一层private修饰的成员函数，只可以类内部访问，使其在使用上和普通成员函数无差异！！！

3.3 非递归实现查找操作Find

	bool Find(const K& key) const {if (_root == nullptr) {return false;}Node* cur = _root;while (cur) {if (cur->_key > key) {cur = cur->_left;}else if (cur->_key < key) {cur = cur->_right;}else {return true;}}return false;}

3.4 非递归实现删除操作Erase

bool Erase(const K & key) {if (_root == nullptr) {return false;}Node* cur = _root;Node* parent = nullptr;while (cur) {if (cur->_key > key) {parent = cur;cur = cur->_left;}else if (cur->_key < key) {parent = cur;cur = cur->_right;}else {if (cur->_left == nullptr) {if (cur == _root) {_root = cur->_right;}else{if (cur == parent->_left) {parent->_left = cur->_right;}else {parent->_right = cur->_right;}}delete cur;cur = nullptr;return true;}else if (cur->_right == nullptr) {if (cur == _root) {_root = cur->_left;}else {if (cur == parent->_left) {parent->_left = cur->_left;}else {parent->_right = cur->_left;}}delete cur;cur = nullptr;return true;}else {//替换法删除 -- 右数最小节点Node* replace = cur->_right;Node* replaceParent = cur;while (replace->_left != nullptr) {replaceParent = replace;replace = replace->_left;}std::swap(cur->_key, replace->_key);if (replaceParent->_left == replace) {replaceParent->_left = replace->_right;}else {replaceParent->_right = replace->_right;}delete replace;return true;}}}return false;}

注： 采用替换法删除数据，因为二叉搜索树的性质，导致其元素如果重复便会插入失败，因此说明其可以自动去重，在删除时，由于每个元素数据不同，采用替换的方式更为高效易懂。

3.5 递归实现插入操作InsertR

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

3.5 递归实现查找操作FindR

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

3.6 递归实现删除操作EraseR（递归引用的价值）

递归下引用传值的价值：

public:bool EraseR(const K& key) {return _EraseR(_root, key);}
private:bool _EraseR(Node*& root ,const K& key) {if (root == nullptr) {return false;}if (key > root->_key) {return  _EraseR(root->_right, key); }else if (key < root->_key) {return  _EraseR(root->_left, key);}else {//删除数据Node* del = root;if (root->_left == nullptr) {root = root->_right;}else if (root->_right == nullptr) {root = root->_left;}else {Node* replace = root->_right;while (replace->_left != nullptr) {replace = replace->_left;}std::swap(root->_key, replace->_key);return _EraseR(root->_right, key);}delete del;return true;}}

4.二叉搜索树的拷贝赋值析构&&其他操作

4.1 二叉树的拷贝构造

二叉树的拷贝因每个节点都是new出来的，因此需要采用深拷贝，而拷贝不能改变树的结构，并保持节点左孩子有孩子指向相同，可以使用递归方式，采用先序遍历，先开辟根节点，再使根节点的左孩子指向左子树，有右孩子指向右子树递归，构建树

public:BinarySearchTree(const BinarySearchTree<K>& bst) {_root = _copy(bst._root);}
private:Node* _copy(Node* root) {if (root == nullptr) {return nullptr;}Node* copyRoot = new Node(root->_key);copyRoot->_left = _copy(root->_left);copyRoot->_right = _copy(root->_right);return copyRoot;}

注：虽然自定义类型构造函数生成的默认构造即可满足需求，但是拷贝构造完成的是值拷贝，会造成double free，因此重写拷贝构造时，拷贝构造也是构造，编译器不在生成默认构造，使用C++11新增的default关键字，强制编译器生成默认构造！

4.2 二叉搜索树的赋值

默认生成的赋值同样完成的是值拷贝，因此需要重写赋值操作，而赋值可以根据拷贝构造并使用现代写法，完成赋值运算

public:BinarySearchTree<K>& operator=(BinarySearchTree<K> bst) {std::swap(_root, bst._root);return *this;}

4.3 二叉搜索树的析构

因为使用了堆区空间，析构时需要遍历整棵树，而析构应采用后序遍历，使用分治思想，先析构左子树，在析构右子树，最终析构根节点，否者会找不到左右子树，会造成内存泄露！

		void _destory(Node*& root) {if (root == nullptr) {return;}_destory(root->_left);_destory(root->_right);delete root;root = nullptr;}public:~BinarySearchTree() {_destory(_root);}

4.4 二叉搜索树的其他操作

求叶子节点个数、节点个数、树深度

​
public:int depth() const {return _depth(_root);}int nodeCount() const {return _nodeCount(_root);}int leafSize() const {return _leafSize(_root);}
private:int _depth(Node* root) const {if (root == nullptr) {return 0;}int leftDepth = _depth(root->_left) + 1;int rightDepth = _depth(root->_right) + 1;return  leftDepth > rightDepth ? leftDepth : rightDepth;}int _nodeCount(Node* root) const {if (root == nullptr) {return 0;}int leftCount = _nodeCount(root->_left) + 1;int rightCount = _nodeCount(root->_right) + 1;return leftCount + rightCount - 1;}int _leafSize(Node* root) const {if (root == nullptr) {return 0;}if (root->_left == nullptr && root->_right == nullptr) {return 1;}int leftSize = _leafSize(root->_left);int rightSize = _leafSize(root->_right);return leftSize + rightSize;}

5. 二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

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

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

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log_2 N

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：frac{N}{2}

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


http://www.ppmy.cn/news/568872.html

相关文章

第十四章 Vision Transformer网络详解

第十四章 Vision Transformer网络详解

系列文章目录 第一章 AlexNet网络详解 第二章 VGG网络详解 第三章 GoogLeNet网络详解 第四章 ResNet网络详解 第五章 ResNeXt网络详解 第六章 MobileNetv1网络详解 第七章 MobileNetv2网络详解 第八章 MobileNetv3网络详解 第九章 ShuffleNetv1网络详解 第十章…
阅读更多...
电视盒子显示服务器未连接,你家的电视盒子直播总是卡，解决方法全都在这里...

电视盒子显示服务器未连接,你家的电视盒子直播总是卡，解决方法全都在这里...

原标题&#xff1a;你家的电视盒子直播总是卡&#xff0c;解决方法全都在这里 这两年随着科技的进步&#xff0c;越来越多的出现在客厅之中。但是许多人在用的时候老是出现播放不流畅&#xff0c;此情此景着实令人无奈&#xff0c;但有什么办法能解决此类问题呢。根据使用了解到…
阅读更多...
Sharding-JDBC之RangeShardingAlgorithm（范围分片算法）

Sharding-JDBC之RangeShardingAlgorithm（范围分片算法）

目录 一、简介二、maven依赖三、数据库3.1、创建数据库3.2、创建表 四、配置&#xff08;二选一&#xff09;4.1、properties配置4.2、yml配置 五、范围分片算法六、实现6.1、实体层6.2、持久层6.3、服务层6.4、测试类6.4.1、保存订单数据6.4.2、根据时间范围查询订单 一、简介…
阅读更多...
《C++高级编程》读书笔记（十一：理解灵活而奇特的C++）

《C++高级编程》读书笔记（十一：理解灵活而奇特的C++）

1、参考引用 C高级编程&#xff08;第4版&#xff0c;C17标准&#xff09;马克葛瑞格尔 2、建议先看《21天学通C》 这本书入门&#xff0c;笔记链接如下 21天学通C读书笔记&#xff08;文章链接汇总&#xff09; 1. 引用 在 C 中&#xff0c;引用是另一个变量的别名&#xff0…
阅读更多...
母婴情报局 | 得母婴者得东南亚？带你剧透母婴市场未来热销趋势

母婴情报局 | 得母婴者得东南亚？带你剧透母婴市场未来热销趋势

Lazada 9.9大促畅销正酣&#xff0c;新一波的消费者数据即将出炉。在拥有人口红利的东南亚跨境业务&#xff0c;母婴跨市场兼具增量与存量&#xff0c;如何做好母婴类目选品和运营&#xff0c;本期情报局带你提前剧透母婴市场未来热销趋势。 Lazada 9.9大促畅销正酣&#xff0c…
阅读更多...
那些年我发现的圈子（6）母婴品牌圈

那些年我发现的圈子（6）母婴品牌圈

母婴品牌圈 母婴品牌圈,孕婴童品牌圈,母婴用品品牌论坛与点评,孕婴品牌导购与价格点评互动交流。 这个网站我感觉很有个性&#xff0c;说是圈子吧他名字的确带圈字。仔细一观察&#xff0c;他的每个圈子就是一个品牌也很有意思。
阅读更多...
【报告分享】2021母婴行业洞察报告-宝宝树（附下载）

【报告分享】2021母婴行业洞察报告-宝宝树（附下载）

摘要:超过七成的一孩年轻家庭&#xff08;含怀孕&#xff09;有生育二孩/三孩意愿&#xff1b;超过六成生育适龄人群表示生育奖励金及补贴、夫妻共同产假等配套福利能够提升其生育意愿。暂不考虑生二孩和三孩的原因略有不同&#xff0c;一孩家庭人群主要考虑养育成本和教育责任…
阅读更多...
【报告分享】2021母婴人群新消费洞察报告-妈妈网 （附下载）

【报告分享】2021母婴人群新消费洞察报告-妈妈网 （附下载）

摘要:新一代消费群体的消费观正在向“只买对的不买贵的”快速转变&#xff0c;当代妈妈群体也同样。报告显示&#xff0c;超过九成妈妈在选择母婴产品前会做大量功课&#xff0c;贵的就是好的已经不在有说服力。购买前&#xff0c;妈妈们会通过多个角度去了解、判断产品是不是真…
阅读更多...
最新文章

Copyright @ 2022~2023