c++的学习之路:24、 二叉搜索树概念

摘要

本章主要是讲一下二叉搜索树的实现

目录

摘要

 一、二叉搜索树概念

二、 二叉搜索树操作

1、二叉搜索树的查找

2、二叉搜索树的插入

3、二叉搜索树的删除

三、二叉搜索树的实现

1、插入

2、中序遍历

3、删除

4、查找

四、二叉搜索树的递归实现

1、插入

2、删除

3、查找

五、代码

test.c

BSTree.h

六、思维导图


 一、二叉搜索树概念

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

1、若它的左子树不为空,则左子树上所有节点的值都小于根节点的值

2、若它的右子树不为空,则右子树上所有节点的值都大于根节点的值

3、它的左右子树也分别为二叉搜索树

如下图所示的图片就是一个二叉搜索树。

二、 二叉搜索树操作

这个就是不在附图了,就是上面那个图,他的数值就是int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};这个数组所示的数值。

1、二叉搜索树的查找

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

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

2、二叉搜索树的插入

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

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

如下图所示

3、二叉搜索树的删除

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

a、要删除的结点无孩子结点

b、要删除的结点只有左孩子结点

c、要删除的结点只有右孩子结点

d、要删除的结点有左、右孩子结点

根据上述情况有下面几种情况b:删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除,情况c:删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除,情况d:在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题--替换法删除,也就是找个保姆

三、二叉搜索树的实现

1、插入

想要插入首先要构建节点,如下方块种代码,就是申请一个节点,这个就不用多说了,第二个快的代码就是申请插入,就是如果没有也就是空的时候就申请一个节点,然后判断需要插入的数值,如果大于跟节点就给给左,如果小于就是右边,然后在循环中进行下去,直到找到合适的位置进行插入,如果有相同的就返回false,测试插入成功在中序遍历进行打印查看。

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

typedef BSTreeNode<K> Node;
    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->_left;
            }
            else if (cur->_key < key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                return false;
            }
        }
        cur = new Node(key);
        if (parent->_key > key)
        {
            parent->_left = cur;
        }
        else
        {
            parent->_right = cur;
        }
        return true;
    } 

2、中序遍历

在下方块种的代码就是测试中序的,这个就没啥说的就是递归打印,但是有一点要注意,root节点是私密的在外面访问不到,没法使用,这里需要借用一个没有参数的函数进行打印,如下方代码所示,测试结果如图。

void InOrder()
    {
        _InOrder(_root);
    }
    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;
        _InOrder(root->_left);
        cout << root->_key << ' ';
        _InOrder(root->_right);
    }

3、删除

这个就是优点麻烦了,他就是和上面所写操作中的三种情况,根据这三种情况进行写,首先就是寻找相等的,这个就没啥说的了,找到后就是判断左边为空和右边为空的两种情况,找到相等的时候,然后进行判断是否需要链接,这里是不管需不需要都进行链接,因为一种是后续有节点进行连接,一种是没有直接连接为空,刚好解决这两中情况,然后就是左右都不为空的时候,这个需要找个托孤的,就有点像我学Linux的时候遇到的孤儿进程被1号进程托孤一样,这里就是左边最大节点和右边最小节点,然后进行换一下,在进行删除,这里代码如下,测试如图。

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 (parent->_left == cur)//如果cur在父节点的左边,就把cur右边的值托孤给父,如果是空,刚好是空节点给父
                        {
                            parent->_left = cur->_right;
                        }
                        else//如果cur在父节点的右边,就把cur左边的值托孤给父
                        {
                            parent->_right = cur->_right;
                        }

                    }
                    delete cur;
                }
                //右为空
                else if (cur->_right == nullptr)
                {
                    if (cur == _root)//如果是根节点,右边都是空,只有左边有值
                    {
                        _root = cur->_left;
                    }
                    else//不是根节点
                    {
                        if (parent->_left = cur)//如果cur在父节点的左边,就把cur右边的值托孤给父,如果是空,刚好是空节点给父
                        {
                            parent->_left = cur->_left;
                        }
                        else//如果cur在父节点的右边,就把cur左边的值托孤给父
                        {
                            parent->_right = cur->_left;
                        }

                    }
                    delete cur;
                }
                else
                {
                    // 找右树最小节点替代,也可以是左树最大节点替代
                    Node* pminRight = cur;
                    Node* minRight = cur->_right;
                    while (minRight->_left)
                    {
                        pminRight = minRight;
                        minRight = minRight->_left;
                    }

                    cur->_key = minRight->_key;

                    if (pminRight->_left == minRight)
                    {
                        pminRight->_left = minRight->_right;
                    }
                    else
                    {
                        pminRight->_right = minRight->_right;
                    }
                    delete minRight;
                }
                return true;
            }
        }
        return false;
    }

4、查找

这个就是直接进行查找就好了,比根节点大就去右边找,小就是左边找,如下代码所示,测试如图。

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

四、二叉搜索树的递归实现

1、插入

这里世界利用递归去插入,如果为空就创建一个节点,没有的判断是否比根小,小的话就去左边递归,大的就去右边递归,因为这个需要root节点所以和上面所说的中序一样进行利用函数进行使用直接传递key值就可以了,如下代码,这里的测试放在最后了,和上面测试一样的。

bool InsertR(const K& key)
    {
        return _InsertR(_root, key);
    }

bool InsertR(const K& key)
    {
        return _InsertR(_root, key);
    }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;
        }
    }

2、删除

这个删除和上面差不多也是三种情况,这里也是利用递归去查找,就是在最后一种需要注意下,这里是利用左边最大的节点交换,然后进行递归查找,但是需要注意这里需要利用引用传值进行删除。

bool EraseR(const K& key)
    {
        return _EraseR(_root, key);
    }

    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* maxleft = root->_left;
                while (maxleft->_right)
                {
                    maxleft = maxleft->_right;
                }

                swap(root->_key, maxleft->_key);

                return _EraseR(root->_left, key);
            }

            delete del;

            return true;
        }
    }

3、查找

这个递归的查找就是判断,如果没有找到节点为空的时候就返回false,找到了就返回true,然后大于的话就去左边,小于就去右边,如下方代码所示,测试如图。

bool FindR(const K& key)
    {
        return _FindR(_root, key);
    }

    bool _FindR(Node* root, const K& key)
    {
        if (root == nullptr)
            return false;

        if (root->_key == key)
            return true;

        if (root->_key < key)
            return _FindR(root->_right, key);
        else
            return _FindR(root->_left, key);
    }

五、代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
#include "BSTree.h"//void Test()
//{
//	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
//	BSTree<int> t1;
//	
//	for (auto e : a)
//	{
//		t1.Insert(e);
//	}
//	t1.Find(8);
//	t1.InOrder();
//	cout << endl;
//
//	for (auto e : a)
//	{
//		t1.Erase(e);
//		t1.InOrder();
//		cout << endl;
//	}
//
//	t1.InOrder();
//	cout << endl;
//}void Test()
{int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> t1;for (auto e : a){t1.InsertR(e);}cout<<t1.FindR(8)<<endl;t1.InOrder();cout << endl;for (auto e : a){t1.EraseR(e);t1.InOrder();cout << endl;}t1.InOrder();cout << endl;
}int main()
{Test();return 0;
}

BSTree.h

#pragma oncetemplate<class T>
struct BSTreeNode
{BSTreeNode<T>* _left;BSTreeNode<T>* _right;T _key;BSTreeNode(const T& key):_left(nullptr), _right(nullptr), _key(key){}
};
template<class K>
class BSTree
{
public:typedef BSTreeNode<K> Node;BSTree() = default; // 制定强制生成默认构造BSTree(const BSTree<K>&t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}~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;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(key);if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;}bool Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur->_left;}else if(cur->_key<key){cur->_right;}else{cout << cur->_key << endl;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 (parent->_left == cur)//如果cur在父节点的左边,就把cur右边的值托孤给父,如果是空,刚好是空节点给父{parent->_left = cur->_right;}else//如果cur在父节点的右边,就把cur左边的值托孤给父{parent->_right = cur->_right;}}delete cur;}//右为空else if (cur->_right == nullptr){if (cur == _root)//如果是根节点,右边都是空,只有左边有值{_root = cur->_left;}else//不是根节点{if (parent->_left = cur)//如果cur在父节点的左边,就把cur右边的值托孤给父,如果是空,刚好是空节点给父{parent->_left = cur->_left;}else//如果cur在父节点的右边,就把cur左边的值托孤给父{parent->_right = cur->_left;}}delete cur;}else{// 找右树最小节点替代,也可以是左树最大节点替代Node* pminRight = cur;Node* minRight = cur->_right;while (minRight->_left){pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (pminRight->_left == minRight){pminRight->_left = minRight->_right;}else{pminRight->_right = minRight->_right;}delete minRight;}return true;}}return false;}void InOrder(){_InOrder(_root);}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;root = nullptr;}bool FindR(const K& key){return _FindR(_root, key);}bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key == key)return true;if (root->_key < key)return _FindR(root->_right, key);elsereturn _FindR(root->_left, key);}bool InsertR(const K& key){return _InsertR(_root, key);}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(const K& key){return _EraseR(_root, key);}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* maxleft = root->_left;while (maxleft->_right){maxleft = maxleft->_right;}swap(root->_key, maxleft->_key);return _EraseR(root->_left, key);}delete del;return true;}}
private:Node* _root = nullptr;
};

六、思维导图

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

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

相关文章

LLM推理框架Triton Inference Server学习笔记(二): Triton模型部署流程(stey by stey)

官方文档查阅: TritonInferenceServer文档 1. 写在前面 上一篇文章对triton inference server进行了一个整体的介绍&#xff0c;解答了三个经典问题what, why, how。 这篇文章就开始转入实践&#xff0c; 从实践的角度整理Triton模型部署的全流程&#xff0c; 如果我有一个训…

华为 2024 届实习招聘——硬件-电源机试题(四套)

华为 2024 届实习招聘——硬件-电源机试题&#xff08;四套&#xff09; 部分题目分享&#xff0c;完整版带答案(有答案&#xff0c;答案非官方&#xff0c;未仔细校正&#xff0c;仅供参考&#xff09;&#xff08;共四套&#xff09; 获取&#xff08;WX:didadidadidida313&…

AcWing 796. 子矩阵的和——算法基础课题解

AcWing 796. 子矩阵的和 题目描述 输入一个 n 行 m 列的整数矩阵&#xff0c;再输入 q 个询问&#xff0c;每个询问包含四个整数 x1,y1,x2,y2&#xff0c;表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 n&…

Easy GIS .NET GMap.Net

Easy GIS .NET & GMap.Net .NET 环境下非常简单的GIS地图开发库。 Easy GIS .NET 一个简单的GIS 桌面应用程序&#xff0c;实现了地图瓦片加载、shapefile文件和csv文件加载渲染、地图坐标系统设置及转换等等基本功能&#xff0c;非常简单易用。 Easy GIS .NET is an o…

Linux CentOS 安装 MySQL 服务教程

Linux CentOS 安装 MySQL 服务教程 1. 查看系统和GNU C库(glibc)版本信息 1.1 查询机器 glibc 版本信息 glibc&#xff0c;全名GNU C Library&#xff0c;是大多数Linux发行版中使用的C库&#xff0c;为系统和应用程序提供核心的API接口。在Linux系统中&#xff0c;特别是在…

基于Springboot+Vue+Spring-Security+高德地图API的校园出行管理系统

1介绍 1.1编写目的 明确系统功能与操作流程&#xff0c;说明书提供了详细的系统功能描述和操作指南&#xff0c;使得用户能够了解如何通过系统申请请假、审批流程以及如何管理和监控请假记录等。 1.2文档范围 该文档的目的是解决整个项目系统中“做什么”的问题。对于开发技…

Mybatis-plus中的分页操作

Mybatis-plus中的分页操作 1.导入Mybatis-plus依赖2.创建mybatis配置类3.参数 1.导入Mybatis-plus依赖 因为是一个springboot项目&#xff0c;其中的pom.xml文件内容如下&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <project xmlns&q…

YOLOv8 测试 5:Linux 中 Docker 部署 YOLOv8,Python 封装 API 接口,base64 图片处理

一、前言 记录时间 [2024-4-14] 系列文章简摘&#xff1a; Docker 学习笔记&#xff08;二&#xff09;&#xff1a;在 Linux 中部署 Docker&#xff08;Centos7 下安装 docker、环境配置&#xff0c;以及镜像简单使用&#xff09; API 接口简单使用&#xff08;二&#xff09;…

【HormonyOS4+NEXT】TypeScript基础语法详解

&#x1f64b;‍ 一日之际在于晨 ⭐本期内容&#xff1a;TypeScript基础语法详解 &#x1f3c6;系列专栏&#xff1a;鸿蒙HarmonyOS4NEXT&#xff1a;探索未来智能生态新纪元 文章目录 前言变量与类型函数类与接口类&#xff08;Class&#xff09;接口&#xff08;Interface&am…

Golang使用PGO优化程序性能

文章目录 参考文章PGO是什么使用PGO的好处PGO做了什么热函数内联什么是内联内联的好处Go默认的内联策略查看内联预算PGO的热函数内联 去虚拟化调用指令高速缓存 PGO有什么缺点可执行程序变大构建时间变长 PGO怎么使用典型的工作流程收集CPU配置文件生产环境启动PGO代码改动重新…

Go 自定义14位时间类型 yyyyMMddHHmmss

目录 功能 代码 功能 数据库或者接口时间类型&#xff0c;经常会使用14位的时间格式。每次都转换有点麻烦。可以自定义一个时间类型。 自定义类型需要实现json接口中的MarshalJSON与UnmarshalJSON两个函数&#xff0c;这样在做json编码解码时就会自动转为14位的时间格式了。…

Vue项目学习(一)-SQL闯关

Hello , 我是小恒不会java。今天来阅读一个Vue纯前端项目--SQL在线闯关 进步的方法除了文档书籍视频&#xff0c;学会阅读源代码&#xff0c;从代码中学会解决需求的方法也是必要的 已部署完成&#xff0c;在线体验&#xff1a;http://sql.yunduanjianzhan.cn 背景 简介 闯…

如何提升亚马逊店铺质量?住宅IP代理有何用处?

亚马逊作为全球最大的电子商务平台之一&#xff0c;吸引了无数卖家和买家参与其中。在这个竞争激烈的环境中&#xff0c;要想提升亚马逊店铺的质量和业绩&#xff0c;需要采取一系列有效的策略和工具。而住宅IP代理作为一个强大的网络工具&#xff0c;也在其中发挥着重要的作用…

最新的网易星球GEC挖矿系统修复版 章鱼星球挖矿系统源码 区块链虚拟币交易源码 基于ThinkPHP5开发

区块链系统介绍 2018.12.10更新增加聚合数据短信接口 2018.11.19更新增加短信宝接口 2018.08.17修复Linux系统搭建验证码不显示问题 2018.08.09修复后台某处溢出数据库账号密码BUG 2018.08.06修复票卷BUG 源码介绍&#xff1a; 区块链系统中用户共九个等级&#xff0c;依…

苹果系统如何使用CorelDRAW?coreldraw苹果版使用指南

有不少粉丝使用的是苹果的电脑或者笔记本&#xff0c;想要利用最新的M系列芯片带来的长续航便利&#xff0c;实现外出时进行创意设计的工作。 那如何才能在苹果系统使用CorelDRAW&#xff1f;2个方法分享给大家&#xff1a; 一、购买Mac版CorelDRAW 从2020版开始&#xff0c…

【热门话题】常见分类算法解析

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 常见分类算法解析1. 逻辑回归&#xff08;Logistic Regression&#xff09;2. 朴…

CSS文本属性与字体属性

目录 文本属性 文本颜色 文本对齐 修饰文本 文本缩进 行高 字体属性 字体系列 字体大小 字体粗细 字体样式 字体/文本综合属性写法 Chrome调试工具的使用 文本属性 文本颜色 在CSS中使用color 属性用于定义文本的颜色&#xff0c;使用background-color设置一个盒…

【教学类-50-06】20240410“数一数”4类星号图片制作PDF学具

作品展示&#xff1a; 背景需求&#xff1a; 前文遍历四个文件夹&#xff0c;分别将每个文件夹内的10个图片的左上角加入星号&#xff0c;显示难度系数 【教学类-50-05】20240410“数一数”4类图片添加“难度星号”-CSDN博客文章浏览阅读55次&#xff0c;点赞2次&#xff0c;…

ESXi 无法启动NTP守护进程

在VMware ESXi环境中如果遇到无法启动NTP&#xff08;Network Time Protocol&#xff09;守护进程的问题&#xff0c;可以通过以下步骤进行排查和解决&#xff1a; 步骤1&#xff1a;检查与修复配置文件 登录到ESXi Shell&#xff08;SSH&#xff09;。编辑 /etc/ntp.conf 配…

MAC: 自己制作https的ssl证书(自己签发免费ssl证书)(OPENSSL生成SSL自签证书)

MAC: 自己制作https的ssl证书(自己签发免费ssl证书)(OPENSSL生成SSL自签证书) 前言 现在https大行其道, ssl又是必不可少的环节. 今天就教大家用开源工具openssl自己生成ssl证书的文件和私钥 环境 MAC电脑 openssl工具自行搜索安装 正文 1、终端执行命令 //生成rsa私钥&…