数据结构——二叉搜索树详解

一、二叉搜索树定义

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

1.非空左子树上所有节点的值都小于根节点的值。

2.非空右子树上所有节点的值都大于根节点的值。

3.左右子树也都为二叉搜索树。

如下图所示：

二、二叉搜索树的操作

二叉搜索树结构：

template<class k>struct BSTreeNode {typedef BSTreeNode<k> Node;Node* _left;//左子树指针Node* _right;//右子树指针k _key;//节点数据};

2.1 二叉搜索树的查找

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

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

非递归查找：

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 _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.2 二叉搜索树的插入

插入的具体过程如下：

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

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

插入key值为9的节点，如下图所示：

非递归插入：

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);//以key值开辟节点if (parent->_key < key) {//新节点>父亲节点，在父亲的右边parent->_right = cur;}if (parent->_key > key) {//新节点<父亲节点，在父亲的左边parent->_left = cur;}return true;}

递归插入：

bool _InsertR(Node*& root, const k& key){//递归查找传参指针的引用，修改原指针，让原指针直接指向当前节点if (root == nullptr)//root节点为空，开辟新结点{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;}}

2.3 二叉搜索树的删除

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

1. 要删除的结点无孩子结点 2. 要删除的结点只有左孩子结点 3. 要删除的结点只有右孩子结点 4.要删除的结点有左、右孩子结点

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

1.删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除。

2.删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除。 

3.查找删除结点的右子树的最左节点或者左子树的最右节点（距离删除节点最近，替换后不影响其他节点位置），用它的值填补到被删除节点中，再来处理该结点的删除问题--替换法删除。下面用右子树的最左节点进行替换。

非递归删除：

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{if (cur->_left == nullptr)//删除节点左边为空{if (cur == _root){//删除根节点_root = cur->_right;}else{if (cur == parent->_right){//判断删除节点是parent的left还是rightparent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_right){//判断删除节点是parent的left还是rightparent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;return true;}else {//左右子树均有节点，将删除节点替换为其右子树的最左节点（左子树的最右节点）Node* rightMinParent = cur;//考虑右子树的根节点为最左节点，不进循环Node* rightMin = cur->_right;while (rightMin->_left) {rightMinParent = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMin == rightMinParent->_left) {rightMinParent->_left = rightMin->_right;//rightMin（右子树最左）为替换节点，替换后删除，rightMinParent的左或右指向rightMin的right}else {rightMinParent->_right = rightMin->_right;}delete rightMin;return true;}}}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* rightMin = root->_right;while (rightMin->_left){rightMin = rightMin->_left;}swap(root->_key, rightMin->_key);//交换删除节点和右子树节点的key值return _EraseR(root->_right, key);//交换后，删除节点为右子树最左节点，走left为空时情况}delete del;return true;}}

三、二叉搜索树的模拟实现

//二叉搜索树的模拟实现
namespace rab {template<class k>struct BSTreeNode {typedef BSTreeNode<k> Node;Node* _left;Node* _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;//拷贝构造函数BSTree(const BSTree<k>& t){_root = Copy(t._root);//传入拷贝对象的根节点}//析构函数~BSTree() {Destroy(_root);}//插入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;}if (parent->_key > key) {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{//删除节点左边为空if (cur->_left == nullptr){if (cur == _root){//删除根节点_root = cur->_right;}else{if (cur == parent->_right){//判断删除节点是parent的left还是rightparent->_right = cur->_right;}else{parent->_left = cur->_right;}}delete cur;return true;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_right){//判断删除节点是parent的left还是rightparent->_right = cur->_left;}else{parent->_left = cur->_left;}}delete cur;return true;}else {//左右子树均有节点，将删除节点替换为其右子树的最左节点（左子树的最右节点）Node* rightMinParent = cur;//考虑右子树的根节点为最左节点，不进循环Node* rightMin = cur->_right;while (rightMin->_left) {rightMinParent = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMin == rightMinParent->_left) {rightMinParent->_left = rightMin->_right;//rightMin（右子树最左）为替换节点，替换后删除，rightMinParent的左或右指向rightMin的right}else {rightMinParent->_right = rightMin->_right;}delete rightMin;return true;}}}return false;}/二叉搜索树的递归实现//递归查找bool FindR(const k& key){return _FindR(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;}private://递归中序遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}//递归销毁搜索二叉树void Destroy(Node* root) {if (root == nullptr) {return;}Destroy(root->_left);Destroy(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;}//递归查找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;}}//递归插入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* rightMin = root->_right;while (rightMin->_left){rightMin = rightMin->_left;}swap(root->_key, rightMin->_key);return _EraseR(root->_right, key);//交换后，删除节点为右子树最左节点，走left为空时情况}delete del;return true;}}private:Node* _root = nullptr;};}

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

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

相关文章

振弦采集仪在预防地质灾害监测中的作用与应用前景

振弦采集仪在预防地质灾害监测中的作用与应用前景

振弦采集仪在预防地质灾害监测中的作用与应用前景 振弦采集仪&#xff08;String Vibrating Sensor&#xff0c;简称SVM&#xff09;是一种用于地质灾害监测的重要仪器&#xff0c;它通过测量地面振动信号来预测和预警地质灾害的发生。SVM的作用在于提供实时、准确的地质灾害监…
阅读更多...
vue3+ts+element home页面侧边栏+头部组件+路由组件组合页面教程

vue3+ts+element home页面侧边栏+头部组件+路由组件组合页面教程

文章目录 效果展示template代码script代码样式代码 效果展示 template代码 <template><el-container class"home"><el-aside class"flex" :style"{ width: asideDisplay ? 70px : 290px }"><div class"aside-left&q…
阅读更多...
深度学习语义分割篇——DeepLabV1原理详解篇

深度学习语义分割篇——DeepLabV1原理详解篇

&#x1f34a;作者简介&#xff1a;秃头小苏&#xff0c;致力于用最通俗的语言描述问题 &#x1f34a;专栏推荐&#xff1a;深度学习网络原理与实战 &#x1f34a;近期目标&#xff1a;写好专栏的每一篇文章 &#x1f34a;支持小苏&#xff1a;点赞&#x1f44d;&#x1f3fc;、…
阅读更多...
数据库是怎么做到事务回滚的呢？

数据库是怎么做到事务回滚的呢？

数据库实现事务回滚的原理涉及到数据库管理系统&#xff08;DBMS&#xff09;如何维护事务的一致性和持久性。 基本原理&#xff1a; ACID属性&#xff1a;事务的原子性&#xff08;Atomicity&#xff09;、一致性&#xff08;Consistency&#xff09;、隔离性&#xff08;Iso…
阅读更多...
【Linux】从零开始认识进程 — 中下篇

【Linux】从零开始认识进程 — 中下篇

送给大家一句话&#xff1a; 人一切的痛苦&#xff0c;本质上都是对自己无能的愤怒。而自律&#xff0c;恰恰是解决人生痛苦的根本途径。—— 王小波 从零认识进程 1 进程优先级1.1 什么是优先级1.2 为什么要有优先级1.3 Linux优先级的特点 && 查看方式1.4 其他概念 2…
阅读更多...
c++的学习之路：5、类和对象（1）

c++的学习之路：5、类和对象（1）

一、面向对象和面向过程 在说这个定义时&#xff0c;我就拿c语言举例&#xff0c;在c语言写程序的时候&#xff0c;基本上就是缺什么函数&#xff0c;就去手搓一个函数&#xff0c;写的程序也只是调用函数的&#xff0c;而c就是基于面向对象的开发&#xff0c;他关注的不再是单…
阅读更多...
picgo启动失败解决

picgo启动失败解决

文章目录 报错信息原因分析解决方案 报错信息 打开Picgo&#xff0c;显示报错 A JavaScript error occurred in the main process Uncaught Exception: Error:ENOENT:no such file or directory,open ‘C:\Users\koko\AppData\Roaming\picgo\data.json\picgo.log’ 原因分析…
阅读更多...
[iOS]GCD(一)

[iOS]GCD(一)

[iOS]GCD(一) 文章目录 [iOS]GCD(一)GCD的概要GCD的APIDispatch Queuedispatch_queue_createMain Dispatch Queue和 Global Dispatch Queue.Main Dispatch_set_target_queuedispatch_afterDispatch Groupdispatch_barrier_asyncdispatch_applydispatch_applydispatch_suspend/d…
阅读更多...
【功能实现】新年贺卡（蓝桥）

【功能实现】新年贺卡（蓝桥）

题目分析&#xff1a; 想要实现一个随机抽取功能 功能拆解&#xff1a;题目给了数组&#xff0c;我们采用生成随机数的方式&#xff0c;随机数作为数组的索引值访问数组的值。 并返回获取到的值&#xff0c;将获取到的值插入到页面中。 document.addEventListener(DOMConten…
阅读更多...
哪款软件适合做书单的背景图片？安利这3款

哪款软件适合做书单的背景图片？安利这3款

哪款软件适合做书单的背景图片&#xff1f;在数字化时代&#xff0c;书单作为推广阅读文化、分享书籍信息的重要载体&#xff0c;其视觉效果与内容的吸引力同等重要。一个精美的书单背景图片&#xff0c;不仅能够吸引读者的眼球&#xff0c;还能增强书单的传播效果。因此&#…
阅读更多...
Redis 教程系列之Redis 集群配置(十三)

Redis 教程系列之Redis 集群配置(十三)

1.Redis集群方案比较 主从模式 在软件的架构中，主从模式（Master-Slave）是使用较多的一种架构。主（Master）和从（Slave）分别部署在不同的服务器上，当主节点服务器写入数据时，同时也会将数据同步至从节点服务器，通常情况下，主节点负责写入数据，而从节点负责读取数据。…
阅读更多...
Java I/O

Java I/O

什么是 IO流&#xff1f; 存储和读取数据的解决方案 I: input O: output 流&#xff1a;像水流一样传输数据 IO流的作用&#xff1f; 用于读写数据&#xff08;本地文件&#xff0c;网络&#xff09; IO流从 传输方式 分类 字符是给人看的&#xff0c;字节是给计算机看的。 …
阅读更多...
八、C#计数排序算法

八、C#计数排序算法

简介 计数排序是一种非比较性的排序算法&#xff0c;适用于排序一定范围内的整数。它的基本思想是通过统计每个元素的出现次数&#xff0c;然后根据元素的大小依次输出排序结果。 实现原理 首先找出待排序数组中的最大值max和最小值min。 创建一个长度为max-min1的数组count…
阅读更多...
Java:反射 reflection ( 概念+相关类+使用方法)

Java:反射 reflection ( 概念+相关类+使用方法)

文章目录 一、反射(reflection)1.概念优点&#xff1a;缺点 2.反射的相关类1.Class类1.**反射机制的起源**2.获得类相关的方法3.获得类中属性的相关方法4.获得类中注解相关的方法5.获得类中构造器相关的方法6.获得类中方法相关的方法 2.获取Class对象的三种方法&#xff1a;1.使…
阅读更多...
【算法刷题】链表笔试题解析（1）

【算法刷题】链表笔试题解析（1）

一、链表分割 题目描述&#xff1a; 链接&#xff1a;链表分割 题目分析&#xff1a; 这题直接处理并不好做&#xff0c;我们可以构建前后两个链表&#xff0c;将小于x值的结点放在链表a内&#xff0c;将其它结点放在链表b内&#xff0c;这样将原链表遍历完后&#xff0c;原链…
阅读更多...
JAVA------基础篇

JAVA------基础篇

java基础 1.JDK JDK :java development kit JRE&#xff1a;java runtime environment JDK包含JRE java跨平台&#xff1a;因为java程序运行依赖虚拟机&#xff0c;虚拟机需要有对应操作系统的版本&#xff0c;而jre中有虚拟机。 当你想要在Linux系统下运行&#xff0c;则需要…
阅读更多...
（数据类型）前端八股文修炼Day1

（数据类型）前端八股文修炼Day1

1.JavaScript有哪些数据类型&#xff0c;它们的区别 JavaScript中有以下种数据类型&#xff1a; 基本数据类型&#xff08;Primitive Data Types&#xff09;&#xff1a; String&#xff1a;表示文本数据&#xff0c;用单引号&#xff08;&#xff09;或双引号&#xff08;…
阅读更多...
【C语言】strcmp 的使⽤和模拟实现

【C语言】strcmp 的使⽤和模拟实现

前言 这篇文章将要带我们去实现模拟一个strcmp函数 首先我们要知道strcmp函数的定义 strcmp()定义和用法 我们先看一下strcmp在cplusplus网站中的定义 链接: link int strcmp ( const char * str1, const char * str2 );比较两个字符串将 C 字符串 str1 与 C 字符串 str2 …
阅读更多...
4.Python数据分析—数据分析入门知识图谱索引(知识体系下篇)

4.Python数据分析—数据分析入门知识图谱索引(知识体系下篇)

4.Python数据分析—数据分析入门知识图谱&索引-知识体系下篇 一个人简介二机器学习基础2.1 监督学习与无监督学习2.1.1 监督学习&#xff1a;2.1.2 无监督学习&#xff1a; 2.2 特征工程2.3 常用机器学习算法概述2.3.1 监督学习算法&#xff1a;2.3.2 无监督学习算法&#…
阅读更多...
数据结构/C++：位图 布隆过滤器

数据结构/C++：位图 布隆过滤器

数据结构/C&#xff1a;位图 & 布隆过滤器 位图实现应用 布隆过滤器实现应用 哈希表通过映射关系&#xff0c;实现了O(1)的复杂度来查找数据。相比于其它数据结构&#xff0c;哈希在实践中是一个非常重要的思想&#xff0c;本博客将介绍哈希思想的两大应用&#xff0c;位图…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023