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

二叉树进阶

news 来源：原创 2024/9/26 22:07:23

目录

1. 二叉搜索树实现

1.1 二叉搜索树概念

2.2 二叉搜索树操作

​编辑

​编辑

2.3 二叉搜索树的实现

2.3.0  Destroy()   + 析构

2.3.1 Insert（）插入

2.3.2 InOrder（） 打印搜索二叉树

​编辑​编辑

2.3.3 Find() 查找

2.3.4  Erase()  删除

​编辑

​编辑

​编辑

2.3.5 完整代码

3. ⼆叉搜索树key和key/value使⽤场景

3.1 key搜索场景：

 3.2 key/value搜索场景：

1. 二叉搜索树实现

1.1 二叉搜索树概念


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

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

2.2 二叉搜索树操作

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

1. 二叉搜索树的查找

  • a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
  • b、最多查找高度次，走到到空，还没找到，这个值不存在。

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

  • a. 树为空，则直接新增节点，赋值给root指针
  • b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

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

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

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

  • 情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
  • 情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
  • 情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点
  • 中，再来处理该结点的删除问题--替换法删除

2.3 二叉搜索树的实现

#pragma once
template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}};
template<class K>
class BSTree
{using Node = BSTNode<K>;//等价于 typedef BsTNode<K>;public:bool Insert(const K& key){}
private:Node* _root = nullptr;
};

2.3.0  Destroy()   + 析构

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

2.3.1 Insert（）插入

插⼊的具体过程如下：

  • 1. 树为空，则直接新增结点，赋值给root指针
  • 2. 树不空，按⼆叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位
  • 置，插入新结点。
  • 3. 如果支持插⼊相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑⼀致性，插入相等的值不要一会往右走，一会往左⾛）

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

2.3.2 InOrder（） 打印搜索二叉树

	//提供Get（）函数，访问内部私有函数void InOrder(){_InOrder( _root);}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}

测试用例 

#include"FileName.h"
int main()
{BSTree<int> t;int a[] = { 8,3,1,10,1,6,4,7,14,13 };for (auto e : a){t.Insert(e);}t.InOrder();return 0;
}

2.3.3 Find() 查找

  • 1. 从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。
  • 2. 最多查找高度次，走到到空，还没找到，这个值不存在。
  • 3. 如果不支持插入相等的值，找到x即可返回
  • 4. 如果支持插入相等的值，意味着有多个x存在，一般要求查找中序的第一个x。如下图，查找3，要找到1的右孩子的那个3返回

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;
}

2.3.4  Erase()  删除


首先查找元素是否在二叉搜索树中，如果不存在，则返回false。
如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）

  • 1. 要删除结点N左右孩子均为空
  • 2. 要删除的结点N左孩子位空，右孩子结点不为空
  • 3. 要删除的结点N右孩子位空，左孩子结点不为空
  • 4. 要删除的结点N左右孩子结点均不为空

对应以上四种情况的解决方案：
1. 把N结点的父亲对应孩子指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是一样的）


2. 把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点
3. 把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点
4. 无法直接删除N结点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值最大结点
R(最右结点)或者N右子树的值最小结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的
位置，都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结
点，R结点符合情况2或情况3，可以直接删除。

bool Erase(const K& key)
{Node* parent = _root;Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}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->_left;}}delete cur;}else{右子树的最左节点Node* repalace = cur->_right;Node* repalaceParent = nullptr;while (repalace->_left){   repalaceParent = repalace;repalace = repalace->_left;}cur->_key = repalace->_key;repalaceParent->_left = repalace->_right;delete repalace;}return true;}}
}

 测试用例

#include"FileName.h"
int main()
{BSTree<int> t;int a[] = { 8,3,1,10,1,6,4,7,14,13 };for (auto e : a){t.Insert(e);}t.InOrder();t.Erase(3);cout << endl;t.InOrder();return 0;
}

2.3.5 完整代码

#pragma once
#include<iostream>
using namespace std;
template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}};
template<class K>
class BSTree
{using Node = BSTNode<K>;//等价于 typedef Node BsTNode<K> ;public:~BSTree(){Destroy(_root);_root = nullptr;}bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;//用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;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent-> _left= cur;}return true;}//提供Get（）函数，访问内部私有函数void InOrder(){_InOrder( _root);}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 = _root;Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}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->_left;}}delete cur;}else{右子树的最左节点Node* repalace = cur->_right;Node* repalaceParent = nullptr;while (repalace->_left){   repalaceParent = repalace;repalace = repalace->_left;}cur->_key = repalace->_key;repalaceParent->_left = repalace->_right;delete repalace;}return true;}}}
private:void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}
private:Node* _root = nullptr;
};

3. ⼆叉搜索树key和key/value使⽤场景


3.1 key搜索场景：


只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的⼆叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。


场景1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进⼊。
场景2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在⼆叉搜索树中，不在则波浪线标红提⽰。

 3.2 key/value搜索场景：


每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，修改key破坏搜索树结构了，可以修改value。


场景1：简单中英互译字典，树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时输入英文，则同时查找到了英文对应的中文。
场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，⽤当前时间-入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。
场景3：统计一篇文章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第一次出现，（单词，1），单词存在，则++单词对应的次数。

查字典

#pragma once
#include<iostream>
using namespace std;
namespace key {template<class K, class V>struct BSTNode{K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key, const V& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};template<class K, class V>class BSTree{using Node = BSTNode<K, V>;//等价于 typedef Node BsTNode<K> ;public://强制生成构造BSTree() = default;BSTree(const BSTree& t){_root = Copy(t._root);}BSTree& operator=(BSTree tmp){swap(_root, tmp._root);return *this;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}~BSTree(){Destroy(_root);_root = nullptr;}bool Insert(const K& key,const V& _value){if (_root == nullptr){_root = new Node(key,_value);return true;}Node* parent = nullptr;Node* cur = _root;//用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 cur;}}cur = new Node(key,_value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}//提供Get（）函数，访问内部私有函数void InOrder(){_InOrder(_root);}Node* 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 cur;}}return  nullptr;}bool Erase(const K& key){Node* parent = _root;Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}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->_left;}}delete cur;}else{右子树的最左节点Node* repalace = cur->_right;Node* repalaceParent = nullptr;while (repalace->_left){repalaceParent = repalace;repalace = repalace->_left;}cur->_key = repalace->_key;repalaceParent->_left = repalace->_right;delete repalace;}return true;}}}private:void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ":" << _root->_value << endl;_InOrder(root->_right);}private:Node* _root = nullptr;};
}

#include"FileName.h"
int main()
{key::BSTree<string, string> dict;//BSTree<string, string> copy = dict;dict.Insert("left", "左边");dict.Insert("right", "右边");dict.Insert("insert", "插⼊");dict.Insert("string", "字符串");string str;while (cin >> str){auto ret = dict.Find(str);if (ret){cout << "->" << ret->_value << endl;}else{cout << "无此单词，请重新输入" << endl;}}return 0;}

 查水果数量

#include"FileName.h"
int main()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };key::BSTree<string, int> countTree;for (const auto& str : arr){// 先查找⽔果在不在搜索树中// 1、不在，说明⽔果第⼀次出现，则插⼊<⽔果, 1>// 2、在，则查找到的结点中⽔果对应的次数++//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if (ret == NULL){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();return 0;
}

相关文章：

  • MySQL 中删除重复的数据并只保留一条
  • Pandas和matplotlib实现同期天气温度对比
  • 【计算机网络 - 基础问题】每日 3 题（二十三）
  • ArcGIS Desktop使用入门（三）常用工具条——拓扑（下篇：地理数据库拓扑）
  • 【机器学习】13-决策树2——决策树生成、剪枝
  • Ubuntu上如何优雅下载huggingface上某个gguf模型文件
  • 解决 ValueError: did not find HDF5 headers----安装netCDF4报错
  • Elasticsearch分布式搜索引擎入门
  • Anaconda虚拟环境创建和配置以使用PyTorch和DGL
  • 机器学习课程学习周报十三
  • LLM - 使用 XTuner 指令微调 多模态大语言模型(InternVL2) 教程
  • OJ在线评测系统 后端 判题机模块预开发 架构分析 使用工厂模式搭建
  • 【在Linux世界中追寻伟大的One Piece】进程间通信
  • Rapid品牌SSL证书通配符单域名申请窍门
  • 背景图鼠标放上去切换图片过渡效果
  • 【mysql】环境安装、服务启动、密码设置
  • angular2开源库收集
  • CentOS 7 防火墙操作
  • LeetCode算法系列_0891_子序列宽度之和
  • Promise面试题，控制异步流程
  • ReactNative开发常用的三方模块
  • Sass Day-01
  • VUE es6技巧写法（持续更新中~~~）
  • vue从创建到完整的饿了么（11）组件的使用（svg图标及watch的简单使用）
  • 搭建gitbook 和 访问权限认证
  • 分布式熔断降级平台aegis
  • 爬虫模拟登陆 SegmentFault
  • 如何进阶一名有竞争力的程序员?
  • 一个JAVA程序员成长之路分享
  • 用element的upload组件实现多图片上传和压缩
  • 用jQuery怎么做到前后端分离
  • 原创：新手布局福音！微信小程序使用flex的一些基础样式属性（一）
  • 阿里云移动端播放器高级功能介绍
  • ​什么是bug？bug的源头在哪里？
  • (AngularJS)Angular 控制器之间通信初探
  • （苍穹外卖）day03菜品管理
  • （二）JAVA使用POI操作excel
  • （五）Python 垃圾回收机制
  • （原创）boost.property_tree解析xml的帮助类以及中文解析问题的解决
  • (转)setTimeout 和 setInterval 的区别
  • (轉貼) 蒼井そら挑戰筋肉擂台 (Misc)
  • **《Linux/Unix系统编程手册》读书笔记24章**
  • .bat批处理（三）：变量声明、设置、拼接、截取
  • .net 7和core版 SignalR
  • .Net 8.0 新的变化
  • .NET C# 使用 SetWindowsHookEx 监听鼠标或键盘消息以及此方法的坑
  • .net core 6 集成 elasticsearch 并 使用分词器
  • .NET CORE Aws S3 使用
  • .Net Core 笔试1
  • .net core 连接数据库，通过数据库生成Modell
  • .Net Core 生成管理员权限的应用程序
  • .Net 高效开发之不可错过的实用工具
  • .net2005怎么读string形的xml，不是xml文件。
  • .NET国产化改造探索（三）、银河麒麟安装.NET 8环境
  • .NET设计模式（2）：单件模式（Singleton Pattern）