【C++】搜索二叉树

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

  • 一、搜索二叉树概念
  • 二、搜索二叉树的操作
    • 1.插入
    • 2. 查找
    • 3. 中序遍历
    • 4. 删除
  • 三、默认成员函数
    • 1.析构函数
    • 2.拷贝构造
    • 3. 赋值运算符重载
  • 四、完整代码

一、搜索二叉树概念

搜索二叉树 也叫做二叉排序树，它要么是一棵空树，要么具有以下性质:
（1）若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
（2）若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
（3）它的左右子树也分别为二叉搜索树

如下就是搜索二叉树，对于任何一个节点，它的左子树的所有节点值都比它小，它的右子树的所有节点值都比它大：

int a[] = {9,6,15,4,13,5,1,20,8,27};

在这里插入图片描述

总结：在左子树值比根小，右子树值比根大。 当树走中序遍历时，序列都是有序的。

搜索二叉树的结构定义：

//定义树的结点
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){}private:Node* _root;//根
};

提示：以下是本篇文章正文内容，下面案例可供参考

二、搜索二叉树的操作

1.插入

插入节点分两步：

（1）找位置

    ①key比当前节点值大，向右走②key比当前节点值小，向左走③key等于当前节点值，该节点值已经存在，插入失败

（2）插入

    ①key比父亲节点值小就插入父亲左子树②key比父亲节点值大就插入父亲右子树

由于插入后，要将节点链接到树中，因此要定义parent节点，用来链接新节点：
在这里插入图片描述

bool Insert(const K& key){//空树 -》 直接插入if (_root == nullptr){_root = new Node(key);}//寻找插入位置Node* cur = _root;Node* parent = cur;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}//搜索二叉树中不允许出现相同结点else{return false;}}//找到了插入节点的位置了-》判断插入节点与parent->_key的大小，判断插入到左子树还是右子树if (parent->_key > key){parent->_left = new Node(key);}else{parent->_right = new Node(key);}return true;}//递归插入 形成二叉树
bool _InsertR(Node*& _root, const K& key){//说明找到插入节点的位置了 / 树为NULLif (_root == nullptr){_root = new Node(key);return true;}if (_root->_key > key){return _InsertR(_root->_left, key);}else if (_root->_key < key){return _InsertR(_root->_right, key);}else return false;}

2. 查找

查找比较简单：

    ①key比当前节点值大，向右走②key比当前节点值小，向左走③key等于当前节点值，找到了

在这里插入图片描述

//查找 迭代Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}elsereturn cur;}return cur;}//查找递归版本Node* _FindR(Node* _root, const K& key){if (_root == nullptr) return _root;if (_root->_key > key) return _FindR(_root->_left, key);else if(_root->_key < key) return _FindR(_root->_right, key);else return _root;}

3. 中序遍历

由于根节点的访问限定符是私有的，那么在main函数中要终须遍历一棵树时，就无法将二叉搜索树的对象根节点传给中序遍历，因为类外面访问不到私有成员。

因此可以这样考虑：这个搜索二叉树对象是有根节点的，可以考虑在里面套一层，给套在里面的函数传参_root ，去递归调用自己:

	//内层函数使用_rootvoid _Inorder(Node* root){if (root == nullptr){return;}_Inorder(root->_left);//递归调用自己cout << root->_key << " ";_Inorder(root->_right);//递归调用自己}//先调不传参数的InOrdervoid InOrder(){//把_root传给子函数，让子函数去使用_root_InOrder(_root);cout << endl;}

4. 删除

（1）找位置

    ①key比当前节点值大，向右走②key比当前节点值小，向左走③key等于当前节点值，找到了，准备删除

（2）删除，有两种删除方法：非递归和递归

非递归删除:

①该节点没有孩子，即该节点是叶子节点，删除节点后把父亲指向自己的指针置空

在这里插入图片描述

②该节点有一个孩子，就把该节点的孩子节点的链接给该节点的父亲，顶替自己的位置，①可以当成②的特殊情况
在这里插入图片描述
③该节点有两个孩子，找比它自己的左孩子大，比它自己的右孩子小的节点替换它（也就是拿它的左子树的最大节点或右子树的最小节点替换它），替换之后，该节点就只有一个孩子或没有孩子了，就变成①或②了。
在这里插入图片描述

//删除的非递归版本bool Erase(const K& key){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 (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}//删除结点的右子树为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_right;}}delete cur;}//删除节点的左右子树都不为空else{//寻找右子树的最小结点 最左Node* MinRightNode = cur->_right;Node* MinParentNode = cur;while (MinRightNode->_left){MinParentNode = MinRightNode;MinRightNode = MinRightNode->_left;}//找到了右子树的最小结点swap(MinRightNode->_key, cur->_key);if (MinParentNode->_left == MinRightNode){MinParentNode->_left = MinRightNode->_right;}else{MinParentNode->_right = MinRightNode->_right;}delete MinRightNode;}return true;}}return false;}//递归删除bool _EraseR(Node*&_root, const K& key){if (_root == nullptr)return false;if (key < _root->_key){return _EraseR(_root->_left, key);}else if (_root->_key < key){return _EraseR(_root->_right, key);}else{//删除// 左子树为空 if (_root->_left == nullptr){Node* del = _root;_root = _root->_right;delete del;}//右子树为空else if (_root->_right == nullptr){Node* del = _root;_root = _root->_left;delete del;}//左右子树都不为空else{//寻找右子树的最小结点 最左Node* MinRightNode = _root->_right;Node* MinParentNode = _root;while (MinRightNode->_left){MinParentNode = MinRightNode;MinRightNode = MinRightNode->_left;}//找到了右子树的最小结点swap(MinRightNode->_key, _root->_key);if (MinParentNode->_left == MinRightNode){MinParentNode->_left = MinRightNode->_right;}else{MinParentNode->_right = MinRightNode->_right;}delete MinRightNode;}return true;}}

三、默认成员函数

1.析构函数

递归调用子函数去析构

	~BSTree(){Destory(_root);_root = nullptr;}void Destory(Node* _root){if (_root == nullptr) return;Destory(_root->_left);Destory(_root->_right);delete _root;}//中序遍历void _InOrder(Node* _root){if (_root == nullptr) return;_InOrder(_root->_left);cout << _root->_key << " ";_InOrder(_root->_right);}

2.拷贝构造

拷贝构造利用递归调用子函数不断拷贝节点:

	//拷贝构造BSTree(const BSTree<K>& t){_root = t.copy(t._root);}

在子函数处:

	Node* _copy(Node* root){if (root == nullptr)//如果根为空，直接返回{return;}Node* copyNode = new Node(root->_key);//创建根节点copyNode->_left = _copy(root->_left);//递归拷贝左子树节点copyNode->_right = _copy(root->_right);//递归拷贝右子树节点return copyNode;//返回根}

3. 赋值运算符重载

使用节点互换的逻辑

	BSTree<K>& operator=(BSTree<K> t)  //t这里调用的拷贝构造-》深拷贝{swap(_root, t._root);Destory(t._root);t._root = nullptr;return *this;}

四、完整代码

//  .h  文件#pragma once
#include <iostream>
using namespace std;
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() = default;//插入 形成搜索二叉树  迭代版本bool Insert(const K& key){//空树 -》 直接插入if (_root == nullptr){_root = new Node(key);}//寻找插入位置Node* cur = _root;Node* parent = cur;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}//搜索二叉树中不允许出现相同结点else{return false;}}//找到了插入节点的位置了-》判断插入节点与parent->_key的大小，判断插入到左子树还是右子树if (parent->_key > key){parent->_left = new Node(key);}else{parent->_right = new Node(key);}return true;}//递归插入 形成二叉树bool InsertR(const K& key){return _InsertR(_root, key);}bool Erase(const K& key){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 (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}//删除结点的右子树为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_right;}}delete cur;}//删除节点的左右子树都不为空else{//寻找右子树的最小结点 最左Node* MinRightNode = cur->_right;Node* MinParentNode = cur;while (MinRightNode->_left){MinParentNode = MinRightNode;MinRightNode = MinRightNode->_left;}//找到了右子树的最小结点swap(MinRightNode->_key, cur->_key);if (MinParentNode->_left == MinRightNode){MinParentNode->_left = MinRightNode->_right;}else{MinParentNode->_right = MinRightNode->_right;}delete MinRightNode;}return true;}}return false;}//递归删除bool EraseR(const K& key){return _EraseR(_root, key);}//查找 迭代Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}elsereturn cur;}return cur;}//查找->递归版本Node* FindR(const K& key){return _FindR(_root, key);}//中序打印void InOrder(){_InOrder(_root);cout << endl;}BSTree(const BSTree<K>& t){_root = Copy(t._root);}~BSTree(){Destory(_root);_root = nullptr;}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);Destory(t._root);t._root = nullptr;return *this;}private://直接给缺省值，调用BSTree默认构造就不用初始化了Node* _root = nullptr;Node* Copy(const Node* _root){if (_root == nullptr) return nullptr;//拷贝根节点  左子树  右子树Node* newnode = new Node(_root->_key);newnode->_left = Copy(_root->_left);newnode->_right = Copy(_root->_right);return newnode;}void Destory(Node* _root){if (_root == nullptr) return;Destory(_root->_left);Destory(_root->_right);delete _root;}//中序遍历void _InOrder(Node* _root){if (_root == nullptr) return;_InOrder(_root->_left);cout << _root->_key << " ";_InOrder(_root->_right);}//递归插入  !!!Node*& _root 就表示当前节点的引用，我直接让_root直接等于new Node(key),直接链接bool _InsertR(Node*& _root, const K& key){//说明找到插入节点的位置了 / 树为NULLif (_root == nullptr){_root = new Node(key);return true;}if (_root->_key > key){return _InsertR(_root->_left, key);}else if (_root->_key < key){return _InsertR(_root->_right, key);}else return false;}//递归删除bool _EraseR(Node*&_root, const K& key){if (_root == nullptr)return false;if (key < _root->_key){return _EraseR(_root->_left, key);}else if (_root->_key < key){return _EraseR(_root->_right, key);}else{//删除// 左子树为空 if (_root->_left == nullptr){Node* del = _root;_root = _root->_right;delete del;}//右子树为空else if (_root->_right == nullptr){Node* del = _root;_root = _root->_left;delete del;}//左右子树都不为空else{//寻找右子树的最小结点 最左Node* MinRightNode = _root->_right;Node* MinParentNode = _root;while (MinRightNode->_left){MinParentNode = MinRightNode;MinRightNode = MinRightNode->_left;}//找到了右子树的最小结点swap(MinRightNode->_key, _root->_key);if (MinParentNode->_left == MinRightNode){MinParentNode->_left = MinRightNode->_right;}else{MinParentNode->_right = MinRightNode->_right;}delete MinRightNode;}return true;}}//查找递归版本Node* _FindR(Node* _root, const K& key){if (_root == nullptr) return _root;if (_root->_key > key) return _FindR(_root->_left, key);else if(_root->_key < key) return _FindR(_root->_right, key);else return _root;}
};//  .cpp 文件#include"BinarySearchTree.h"int main()
{BSTree<int> root;int Tree[] = { 7,2,4,6,3,1,5};for (int i = 0; i < (sizeof(Tree) / sizeof(Tree[0])); i++){root.InsertR(Tree[i]);}root.InOrder();BSTree<int> root1 = root;root1.InOrder();}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/175510.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

「实用技巧」后端如何使用 Eolink Apikit 快速调试接口？

「实用技巧」后端如何使用 Eolink Apikit 快速调试接口？

程序员最讨厌的两件事&#xff1a; 写文档 别人不写文档 写文档、维护文档比较麻烦&#xff0c;而且费时&#xff0c;还会经常出现 API 更新了&#xff0c;但文档还是旧的&#xff0c;各种同步不一致的情况&#xff0c;从而耽搁彼此的时间&#xff0c;大多数开发人员不愿意写…
阅读更多...
抽奖之星软件，可用作随机分组分班、比赛顺序抽签摇号

抽奖之星软件，可用作随机分组分班、比赛顺序抽签摇号

抽奖之星软件简介 抽奖之星&#xff0c;极品晚会抽奖软件&#xff0c;大气美观&#xff0c;功能全面&#xff0c;请安装试用或咨询客服。支持作弊内定、指定中奖人、名单分组、中奖几率。(www.wsgsoft.com/plds/) 比赛顺序抽签设置 奖项设置&#xff1a;只一个奖项即可&…
阅读更多...
分享一下怎么做一个商城小程序

分享一下怎么做一个商城小程序

如何制作一个商城小程序&#xff1a;功能解析、设计思路与实现方法 一、引言 随着移动设备的普及和微信小程序的兴起&#xff0c;越来越多的消费者选择在商城小程序上进行购物。商城小程序具有便捷、高效、即用即走等特点&#xff0c;为企业提供了新的销售渠道和推广方式。本…
阅读更多...
Kubernetes Taint(污点) 和 Toleration(容忍)

Kubernetes Taint(污点) 和 Toleration(容忍)

Author&#xff1a;rab 目录 前言一、Taint&#xff08;污点&#xff09;1.1 概述1.2 查看节点 Taint1.3 标记节点 Taint1.4 删除节点 Taint 二、Toleration&#xff08;容忍&#xff09; 前言 Kubernetes 中的污点&#xff08;Taint&#xff09;和容忍&#xff08;Toleration…
阅读更多...
学习笔记|正态分布|图形法|偏度和峰度|非参数检验法|《小白爱上SPSS》课程：SPSS第三讲 | 正态分布怎么检验？看这篇文章就够了

学习笔记|正态分布|图形法|偏度和峰度|非参数检验法|《小白爱上SPSS》课程：SPSS第三讲 | 正态分布怎么检验？看这篇文章就够了

目录 学习目的软件版本原始文档为什么要假设它服从正态分布呢?t检验一、图形法1、频数分布直方图解读 2、正态Q-Q图操作解读 3、正态P-P图SPSS实战操作解读 二、偏度和峰度解读&#xff1a; 三、非参数检验法注意事项 四、规范表达五、小结划重点 学习目的 SPSS第三讲 | 正态…
阅读更多...
Shopee流量和销量不佳？或许你没有掌握正确的引流方法

Shopee流量和销量不佳？或许你没有掌握正确的引流方法

很多卖家做了很久&#xff0c;但是发现流量和销量都没怎么增长&#xff0c;今天陈哥就分享一下如何正确的引流。 以下是一些有效的引流策略&#xff1a; 1. 站内引流&#xff1a;选择高性价比的潮流商品&#xff0c;根据目标客户群和重点品类进行选品。优化商品名称和描述&am…
阅读更多...
Power BI 傻瓜入门 18. 让您的数据熠熠生辉

Power BI 傻瓜入门 18. 让您的数据熠熠生辉

本章内容包括&#xff1a; 配置Power BI以使数据增量刷新发现使用Power BI Desktop and Services保护数据集的方法在不影响性能和完整性的情况下管理海量数据集 如果有更新的、更相关的数据可用&#xff0c;旧数据对组织没有好处。而且&#xff0c;老实说&#xff0c;如果数据…
阅读更多...
设计模式_观察者模式

设计模式_观察者模式

观察者模式 介绍 设计模式定义案例问题堆积在哪里解决办法观察者是行为型设计模式 多个对象 观察 1个对象小强考试完 成绩公布了 家长/同学得知成绩后 做出不同反应一个一个通知很麻烦 先通知谁 也有讲究的 信息发布方 抽象出一个信息管理类 负责管理监听者 类图 代码 Obse…
阅读更多...
学习视频剪辑：如何从指定时段快速抽出视频图片！高效技巧分享

学习视频剪辑：如何从指定时段快速抽出视频图片！高效技巧分享

随着数字媒体的普及&#xff0c;越来越多的人开始接触视频剪辑。在视频剪辑过程中&#xff0c;有时候我们需要从指定时段快速抽出视频图片。这不仅可以帮助我们提高剪辑效率&#xff0c;还可以让我们的视频更加丰富多彩。本文将分享一些高效技巧&#xff0c;帮助你轻松实现从指…
阅读更多...
尚未解决：use_python()和use_virtualenv()的使用

尚未解决：use_python()和use_virtualenv()的使用

reticulate包为Python和R之间的互操作性提供了一套全面的工具。该包包含以下功能&#xff1a; 以多种方式从R调用Python&#xff0c;包括RMarkdown、获取Python脚本、导入Python模块以及在R会话中交互使用Python。 R和Python对象之间的转换&#xff08;例如&#xff0c;R和Pan…
阅读更多...
Three.js 开发引擎的特点

Three.js 开发引擎的特点

Three.js 是一个流行的开源 3D 游戏和图形引擎&#xff0c;用于在 Web 浏览器中创建高质量的三维图形和互动内容。以下是 Three.js 的主要特点和适用场合&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作…
阅读更多...
​CRM中的大客户销售是什么？​

​CRM中的大客户销售是什么？​

对企业来说&#xff0c;大客户可能贡献了大部分的销售业绩。什么样的客户可以被认定为是大客户&#xff1f;大客户销售与普通销售有何区别&#xff1f;针对大客户又该采取什么样的销售策略呢&#xff1f;从回答这几个问题开始&#xff0c;我们来说说CRM中的大客户销售是什么&am…
阅读更多...
【Postgres】Postgres常用命令

【Postgres】Postgres常用命令

文章目录 1、导出数据库某张表2、导入某张表到数据库3、查看数据库占用磁盘页数情况4、查看数据库大小5、查看数据表大小6、查看索引大小7、对数据库中表索引按照大小排序8、对数据库中表按照大小排序9、回收空间&#xff08;建议先回收指定表&#xff09;10、设置主键自增序列…
阅读更多...
【linux】文件系统+软硬连接+动静态库

【linux】文件系统+软硬连接+动静态库

文件系统软硬连接动静态库 1.理解文件系统1.1磁盘的物理结构1.2磁盘的存储结构1.3磁盘的逻辑结构1.4文件系统 2.软硬链接2.1什么是软硬链接2.2软硬链接的作用 3.动静态库3.1什么是库3.1静态库和静态链接3.2动态库和动态链接3.2.1通过环境变量找到动态库路径3.2.2把动态库拷贝到…
阅读更多...
嗡嗡嗡嗡嗡嗡

嗡嗡嗡嗡嗡嗡

阅读更多...
从零开始学习PX4源码0(固件下载及编译)

从零开始学习PX4源码0(固件下载及编译)

目录 文章目录 目录摘要1.重点学习网址2.固件下载1.下载最新版本固件2.下载之前版本固件 摘要 本节主要记录从零开始学习PX4源码1(固件下载)的过程&#xff0c;欢迎批评指正&#xff01;&#xff01;&#xff01; 下载固件主要分为两个版本&#xff0c;之前稳定版本和最新官网…
阅读更多...
Flutter PopupMenuButton下拉菜单

Flutter PopupMenuButton下拉菜单

下拉菜单是移动应用交互中一种常见的交互方式，可以使用下拉列表来展示多个内容标签，实现页面引导的作用。在Flutter开发中，实现下拉弹框主要有两种方式，一种是继承Dialog组件使用自定义布局的方式实现，另一种则是使用官方的PopupMenuButton组件进行实现。 如果没有特殊的…
阅读更多...
python读取Excel到mysql

python读取Excel到mysql

常见问题&#xff1a; 1.数据库密码有特殊字符 使用urllib.parse.quote_plus 编译密码 mysql_engine create_engine((f"mysqlpymysql://root:%s10.0.0.2:3306/mydb")%urllib.parse.quote_plus("passaaaa")) 2.设置字段类型 设置特定类型&#xff0c;和指…
阅读更多...
Java 使用 poi 和 aspose 实现 word 模板数据写入并转换 pdf 增加水印

Java 使用 poi 和 aspose 实现 word 模板数据写入并转换 pdf 增加水印

本项目所有源码和依赖资源都在文章顶部链接&#xff0c;有需要可以下载使用 1. 需求描述 从指定位置读取一个 word 模板获取业务数据并写入该 word 模板&#xff0c;生成新的 word 文档将新生成的 word 文档转换为 pdf 格式对 pdf 文档添加水印 2. 效果预览 word 模板 带水印的…
阅读更多...
Redis文件事件模型

Redis文件事件模型

Redis是事件驱动的程序&#xff0c;并基于Reactor模式开发了自己的网络事件处理器&#xff0c;被称之为文件处理器(File Event Handler)。 文件处理器通过I/O多路复用程序来同时监听多个Socket&#xff0c;并根据Socket目前执行的任务来关联不同的事件处理器。当被监听的Socket…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023