【数据结构】——二叉搜索树

article/2025/8/25 3:17:13

目录

前言

二叉搜索树的概念

二叉搜索树的操作

 树的节点实现

 搜索树的基本结构

插入数据

查找

删除

拷贝构造函数

  二叉搜索树的应用

前言

在c++中的容器里map和set的学习需要二叉搜索树的铺垫，也为后边的的红黑树和AVL树做铺垫，也就是说，今天主要讲搜索树的基本结构和应用。

二叉搜索树的概念

所有的根节点大于左子树的节点，小于右子树的节点的二叉树就叫做二叉搜索树。

二叉搜索的性质：

  • 如果左子树不为空，则左子树上的所有节点都小于根节点。
  • 如果右子树不为空，则右子树上的所有节点都大于根节点。
  • 左右子树也为搜索二叉树。

 假设我们要查找8，我们从根节点开始查找，这该怎样查找呢？

首先我们先与根节点5对比，发现比根节点5大，所以我们就到它的右子树查找，根节点就变为7，然后我们再与根节点7对比，发现比根节点大，再到根节点7的右子树查找，根节点就变为8，找到该节点之后我们在返回。

二叉搜索树的搜索的时间复杂度：

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

对于同一个元素的集合，如果元素的插入顺序不同的，则会出现不同结构的二叉搜索树，也就是说树的结构与元素插入的顺序有关。

搜索效率最优的情况下:完全二叉树，其平均比较的次数是O (logN)。

搜索效率最坏的情况:单支二叉树，其平均的比较次数是O（N) 

所以搜索二叉树的搜索的时间复杂度是O(N),时间复杂度看的是最坏的情况。

树的搜索次数与树的层次有关.

 

二叉搜索树的操作

 树的节点实现

template<class T>
struct TreeNode
{TreeNode* _left;TreeNode* _right;T _key;TreeNode(const T& x):_key(x),_left(nullptr),_right(nullptr){}
};

 搜索树的基本结构

template<class T>
class BinarySearchTree
{public:typedef  TreeNode<T> Node ;//需要构造函数将根节点初始化为空BinarySearchTree():_root(nullptr){}.....private://为什么是定义Node变量？//1.插入删除时，好判断该节点是否为空。//2.节点的左右孩子都是指针，方便赋值Node* _root;//根节点    
};

插入数据

a.树为空，则直接插入

 

b.树不为空，按二叉树搜索的性质插入的位置，插入的位置都会是叶子节点。 

 c.如果插入的数据在树中已存在，则不将数据插入到树中，并返回false。搜索树的数据都是独一无二的。

 

代码实现：

非递归版本

	bool _Insert( const T& key){//如果树中已存在key，则返回falseif (_root == nullptr){_root = new Node(key);return true;}//遍历搜索树Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key<key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}//创建节点，这里用了匿名对象cur = new Node(key);//判断cur节点要连接到parent的哪个节点if (parent->_key > key){parent->_left = cur;}else if (parent->_key < key){parent->_right = cur;}return true;}

递归的版本：

	//注意root是指针的引用bool _InsertR(Node* &root, const T& key){//如果节点为空，则创建节点给给它if (root == nullptr){root = new Node(key);}if (root->_key > key){_InsertR(root->_left, key);}else if(root->_key<key){_InsertR(root->_right, key);}else {return false;}return true;}bool InsertR(const T& key){return _InsertR(_root, key);}

 _Insert是在private里面的，而Insert是public里的。

查找

找到了就返回该节点的地址，找不到就返回空。

	Node* find(const T& key){if (_root == nullptr)return nullptr;Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else {return cur;}}return nullptr;}

 

删除

   当我们要删除搜索树中某个节点的时候，删除后的树的结构也需要保持着搜索的性质，所以删除有有以下4种情况、

  • 要删除的节点无孩子节点。例如 0 4 6 9 

只要我们找到该值，直接删除掉就行。

  • 要删除的节点有左孩子的节点。例如 1

找到该值，先让该值的父亲节点区连接它的左孩子节点，然后再删除掉。父亲节点要连接该值的左孩子节点时，需要判断孩子节点是连接在父亲的左边还是右边

 

 

 

  • 要删除的节点有右孩子的节点。例如 8

找到该值，先让该值的父亲节点区连接它的右孩子节点，然后再删除掉。父亲节点要连接该值的右孩子节点时，需要判断孩子节点是连接在父亲的左边还是右边

 

  • 要删除的节点有左右孩子的节点。例如 3 5 7

如果我们直接删除这样的节点时，就会让使它的左右子树没有根节点，所以我们怎样删除这样的节点，并保持搜索二叉树的特性？

我们可以找出该值左子树最大的节点或者右子树最小的节点，去替换根节点，然后将替换的节点给删除掉。（左子树最大的节点或者右子树最小的节点去替换的根节点依旧可以保持着搜索二叉树的性质）。

删除5这个数据的过程;，找出左子树最大的值，也就是左子树最右的值，替换到根节点，然后直接将 替换的节点删除即可。

 

删除3的过程，找出左子树最大的值，也就是左子树最右的值。

代码：

	bool _erase(const T key){if (_root == nullptr)return false;//找出key的节点Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else {break;}}//第一种：删掉的是叶子节点//第二种：删掉只有一个孩子的节点//第三种：删掉的是有两个孩子的节点//删除只有右孩子的节点if (cur->_left == nullptr){if (parent==nullptr){_root = cur->_right;delete cur;return true;}if (parent->_left == cur){parent->_left = cur->_right;}else if (parent->_right == cur){parent->_right = cur->_right;}delete cur;}//删除只有左孩子的节点else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;delete cur;return true;}if (parent->_left == cur){parent->_left = cur->_left;}else if (parent->_right == cur){parent->_right = cur->_left;}delete cur;}//删除有左右孩子的节点else{//第三种情况Node* leftmax = cur->_left;Node* leftmaxparent = cur;//左子树最大节点//找出左子树最大的节点while (leftmax->_right){leftmaxparent = leftmax;leftmax = leftmax->_right;}//赋给根节点cur->_key = leftmax->_key;//删除节点if (leftmaxparent->_left == leftmax){leftmaxparent->_left = leftmax->_left;}else {leftmaxparent->_right = leftmax->_left;}delete leftmax;return true;}return false;}

 

这段代码的含义：

 

 递归版本：

	bool _eraseR(Node* &root,const T key){//查找key相对应的值if (root == nullptr)return false;if (root->_key < key)_eraseR(root->_right, key);else if (root->_key > key)_eraseR(root->_left, key);else {if (root->_left == nullptr){Node* tmp = root;root = root->_right;delete tmp;}else if (root->_right == nullptr){Node* tmp = root;root = root->_left;delete tmp;}else{//第三种情况Node* leftmax = root->_left;Node* leftmaxparent = root;//找出左子树最大的节点while (leftmax->_right){leftmaxparent = leftmax;leftmax = leftmax->_right;}//赋给根节点root->_key = leftmax->_key;//删除节点if (leftmaxparent->_left == leftmax){leftmaxparent->_left = leftmax->_left;}else {leftmaxparent->_right = leftmax->_left;}delete leftmax;return true;}}return false;}bool eraseR(const T& x){return _eraseR(_root, x);}

_eraseR是private里面的，eraseR是public里面的。 

 

 

eraseR是对_eraseR的封装，方便被调用。

拷贝构造函数

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;	}BinarySearchTree(BinarySearchTree<T>& t){_root=_copy(t._root);}

 赋值重载函数

 

 析构函数：

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

2.4 二叉搜索树的应用

1.K模型：K模型只有key作为关键码，也就是定义树的节点只需要存_key一个即可，关键码即为搜索到的值。如上我们写的搜索树就是k模型，因为树的节点就只有一个key可以存储数据。

 

比如：我们要进学校的图书馆就需要刷我们的学生卡，通过磁感应将门打开。如下：

 此时我们就需要先将学生的学号录入到该门的管理系统，然后将数据建立起搜索树，我们的学号在学校是唯一的，当我们刷卡的时候，就会去管理系统快速查找我们的学号，找到了门就开了。

k模型在实际应用中就是就是查找在不在的问题。

2.kv模型:每一个关键码key都有一个对应的value值，也就是说树的节点中有两个值，一个是key，一个是value的值，我们通过key找到对应的节点，然后将相对应的value给映射出来。也就是说，我们增删查改的时候也是按key进行插入或者删除。只是创建节点，增加了一个value值。

 场景1：我们去网上买高铁票，每张高铁票的信息都有与一个身份证号绑定在一起的，当我们进高铁站都需要刷身份证在搜索树中查找有没有你的身份证号，找到了，通过身份证号映射你的高铁信息，看看有没有你的班次，门才是否可以被开。在这里_key是身份证，它是独一无二的，_value是高铁信息，通过身份证将它给映射出来。

 场景2：

英汉词典就是英文与中文的对应关系，我们只需要查找有没有该英文，找到了，就通过映射关系，将该英文的单词的中文给映射出来。

用kv模型的搜索树写一个简单的词典：

int main()
{BinarySearchTree<string ,string> v;v._Insert("string","字符串");v._Insert("apple","苹果");v._Insert("automate", "n.自动化，v.使自动化");v._Insert("voluntary", "adj.自愿的主动的，n.志愿者");string s;while (cin>>s){struct TreeNode<string,string>* ret = v.find(s);if (ret == nullptr){cout << "没有找到该单词" << endl;}else{cout <<endl << "	中文:" << ret->_value << endl;}}return 0;
}

运行结果： 

 

场景3：

统计水果次数。

如下

int main()
{const string str[] = { "苹果","西瓜","芒果","苹果","西瓜","西瓜","西瓜","苹果","芒果" };BinarySearchTree<const string, int> count;for (auto s : str){auto ret = count.find(s);if (ret == nullptr){count._Insert(s, 1);}else {ret->_value++;}}count.Inorder();return 0;
}

输出结果：

其中Inorder是将树中所有的节点都给打印出来，代码如下：

	void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << ":" << root->_value << endl;_Inorder(root->_right);}void Inorder(){_Inorder(_root);}

 _Inorder是private里面的，而Inorder是public里面的。

好了，今天分享的知识就到这里了，喜欢的小伙伴们，麻烦帮我点个三连，谢谢你们了。


http://chatgpt.dhexx.cn/article/vEO6HROm.shtml

相关文章

二叉搜索树(二叉排序树)

二叉搜索树(二叉排序树)

一.概念 二叉搜索树又称二叉排序树&#xff0c;具有以下性质&#xff1a; 若它的左子树不为空&#xff0c;则左子树上所有节点的值都小于根节点的值若它的右子树不为空&#xff0c;则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 注意&#xff1a;二…
阅读更多...
二叉排序树（二叉查找树、二叉搜索树）（图解+完整代码）

二叉排序树（二叉查找树、二叉搜索树）（图解+完整代码）

目录 ⚽1.什么是二叉排序树 &#x1f3d0;2.构建二叉排序树 &#x1f3c0;3.二叉排序树的查找操作 &#x1f94e;4.二叉排序树的删除 &#x1f3b1;5.完整代码 ⚽1.什么是二叉排序树 我们直接看它的性质&#xff1a; 若它的左子树不空&#xff0c;则左子树上所有结点的值…
阅读更多...
种树：二叉树、二叉搜索树、AVL树、红黑树、哈夫曼树、B树、树与森林

种树：二叉树、二叉搜索树、AVL树、红黑树、哈夫曼树、B树、树与森林

虽然今天不是植树节&#xff0c;但是我今天想种树。 文章目录 树&#xff0c;什么是树&#xff1f;二叉树定义二叉树的创建二叉树的前中后序遍历前序遍历&#xff1a;中序遍历后序遍历已知前序、中序遍历结果&#xff0c;还原二叉树已知后序、中序遍历结果&#xff0c;还原二叉…
阅读更多...
java lrucache_Java LruCache 的使用及原理

java lrucache_Java LruCache 的使用及原理

概述 LRU (Least Recently Used) 的意思就是近期最少使用算法&#xff0c;它的核心思想就是会优先淘汰那些近期最少使用的缓存对象。 在我们日常开发中&#xff0c;UI 界面进行网络图片加载是很正常的一件事情&#xff0c;但是当界面上的图片过于多的时候&#xff0c;不可能每次…
阅读更多...
LruCache和DiskLruCache

LruCache和DiskLruCache

前言 Android中的三级缓存主要就是内存缓存和硬盘缓存。 Lru(least recently used)意为最近最少使用算法&#xff0c;核心思想就是当缓存满时&#xff0c;会优先淘汰最近最少使用的缓存对象。 LruCache的使用 在Android中可以直接使用LruCache&#xff0c;算法原理是&#xff1…
阅读更多...
Android LruCache 缓存

Android LruCache 缓存

使用场景 1、场景一&#xff1a;图片缓存利器。 可以规定缓存大小、有效避免OOM、自动移除队尾不用的图片缓存、避免HashMap各种问题。 2、场景二&#xff1a;通信缓存 从服务端需要获取数据&#xff0c;但是当访问的数据比较大&#xff0c;比较多&#xff0c;并且是重复数…
阅读更多...
Java——LRUCache

Java——LRUCache

概念 简单来说&#xff0c;由于我们的空间是有限的&#xff0c;所以发明了这个数据结构&#xff0c;当我们的空间不够添加新的元素时&#xff0c;就会删除最近最少使用的元素。 其底层逻辑通过哈希表和链表共同实现。哈希表中存储链表的每一个元素&#xff0c;方便进行元素的…
阅读更多...
LruCache缓存

LruCache缓存

Lru算法&#xff1a; Lru 指的是“Least Recently Used-近期最少使用算法”。 1、那么LruCache到底是什么呢&#xff1f; LruCache 是对限定数量的缓存对象持有强引用的缓存&#xff0c;每一次缓存对象被访问&#xff0c;都会被移动到队列的头部。当有对象要被添加到已经达到数…
阅读更多...
LruCache 源码解析

LruCache 源码解析

1. 概述 对于 Android 开发者&#xff0c;LruCache 肯定不陌生&#xff0c;几乎所有的图片缓存框架都会用到它来实现内存缓存等&#xff0c;可见 LruCache 在 Android 开发中的重要性。LRU 是 Least Recently Used 的缩写&#xff0c;近期最少使用的意思。当我们进行缓存的时候…
阅读更多...
LruCache

LruCache

LruCache这个类是通过Glide得知的&#xff0c;不过它是自己又基于LRU算法自己写了个LruCache工具类&#xff0c;不过基本原理类似&#xff0c;都是基于LRU算法实现的 1.来源 一般来说&#xff0c;缓存策略主要包含缓存的添加、获取和删除这三类操作。如何添加和获取缓存这个比…
阅读更多...
Android基础-LruCache原理解析

Android基础-LruCache原理解析

一、Android中的缓存策略 一般来说&#xff0c;缓存策略主要包含缓存的添加、获取和删除这三类操作。如何添加和获取缓存这个比较好理解&#xff0c;那么为什么还要删除缓存呢&#xff1f;这是因为不管是内存缓存还是硬盘缓存&#xff0c;它们的缓存大小都是有限的。当缓存满了…
阅读更多...
LRUCache详解

LRUCache详解

1.概念 LRU是Least Recently Used的缩写&#xff0c;意思是最近最少使用&#xff0c;它是一种Cache替换算法。 Cache的容量有限&#xff0c;因此当Cache的容量用完后&#xff0c;而又有新的内容需要添加进来时&#xff0c; 就需要挑选并舍弃原有的部分内容&#xff0c;从而腾出…
阅读更多...
LRUCache 详解

LRUCache 详解

LRU算法详解 一、什么是 LRU 算法 就是一种缓存淘汰策略。 计算机的缓存容量有限&#xff0c;如果缓存满了就要删除一些内容&#xff0c;给新内容腾位置。但问题是&#xff0c;删除哪些内容呢&#xff1f;我们肯定希望删掉哪些没什么用的缓存&#xff0c;而把有用的数据继续…
阅读更多...
LRU Cache

LRU Cache

前言 哈喽&#xff0c;各位小伙伴大家好&#xff0c;本章内容为大家介绍计算机当中为了提高数据相互传输时的效率而引进的一种重要设计结构叫做LRU Cache,下面将为大家详细介绍什么是LRU Cache,以及它是如何是实现的&#xff0c;如何提升效率的。 1.什么是LRU Cache? LRU是L…
阅读更多...
uniapp日历原生插件

uniapp日历原生插件

<template><!-- 打卡日历页面 --><view classall><view class"bar"><!-- 上一个月 --><view class"previous" click"handleCalendar(0)"><button class"barbtn">上一月</button><…
阅读更多...
微信小程序使用日历插件

微信小程序使用日历插件

一&#xff0c;添加插件 1&#xff0c;在你的小程序关联的微信公众平台打开 设置》第三方服务》添加插件 2&#xff0c;直接AppID&#xff08;wx92c68dae5a8bb046&#xff09;搜索到该插件并申请授权&#xff0c;授权成功即可在小程序使用 二&#xff0c;小程序使用插件 app…
阅读更多...
日历组件

日历组件

日历组件&#xff1a; <template><div class"calendar" click.stop><div class"input-wrap"><inputtype"text"v-if"dateChangeSets":placeholder"placeholder"class"input dateChangeSets middle…
阅读更多...
vue-calendar基于vue的日历插件

vue-calendar基于vue的日历插件

本文转载于https://www.cnblogs.com/zwhgithub/p/8005414.html vue-calendar-component 基于 vue 2.0 开发的轻量&#xff0c;高性能日历组件占用内存小&#xff0c;性能好&#xff0c;样式好看&#xff0c;可扩展性强原生 js 开发&#xff0c;没引入第三方库 效果 Install …
阅读更多...
实用插件（一）日历插件——My97DatePicker

实用插件（一）日历插件——My97DatePicker

注&#xff1a;My97DatePicker插件仅限pc端使用&#xff0c;若是app项目&#xff0c;建议使用ICalendar或者Mobiscroll。 &#xff08;ICalendar插件在华为手机上存在兼容性问题&#xff0c;日期不能滚动&#xff0c;但使用很简单&#xff1b;Mobiscroll使用起来较为复杂&…
阅读更多...
sys-calendar.js带节假日的日历插件

sys-calendar.js带节假日的日历插件

下载地址 sys-calendar.js带节假日的日历插件&#xff0c;代码引用比较多。 dd:
阅读更多...
推荐文章

Copyright @ 2022~2023