您的位置:首页 > 教程 > 服务端类 > Golang > C++详解数据结构中的搜索二叉树

C++详解数据结构中的搜索二叉树

2022-04-15 15:12:15 来源:易采站长站 作者:

C++详解数据结构中的搜索二叉树

目录
定义查找某个元素构造搜索二叉树往搜索二叉树中插入元素搜索二叉树删除节点

定义

搜索二叉树,也称有序二叉树,排序二叉树,是指一棵空树或者具有下列性质的二叉树:

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

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

3、任意节点的左右子树也称为二叉查找树。

4、没有键值相等的节点。

5、搜索二叉树中序遍历为有序数组。

结构代码实现

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

查找某个元素

在搜索二叉树b中查找x的过程

若树是一个空树,则搜索失败,否则:若x等于b的根节点的键值,则查找成功;否则:若x小于b的根节点的键值,则搜索左子树;否则:若x大于b的根节点的键值,则搜索右子树。

非递归实现

typrdef BSTreeNode<K> Node;
​
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;
}

递归实现

typrdef BSTreeNode<K> Node;
​
Node* _findr(Node* root,const K& key)
{
    if(root==nullptr)
    {
        return nullptr;
    }
    if(root->_key<key)
    {
        return _findr(root->_right);
    }
    else if(root->_key>key)
    {
        return _findr(root->_left);
    }
    else
        return 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;
    }
    cur=new Node(key);
    if(parent->_key<key)
    {
        parent->_right=cur;
    }
    else
        parent->_left=cur;
    return true;
}

递归实现:

bool _insertR(Node* &root,const K&key)
{
    if(root==NULL)
    {
        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;
}

往搜索二叉树中插入元素

向一个二叉搜索树b中插入一个节点s的算法,过程为:

若b是空树,则将s所指结点作为根节点插入,否则:若s->data等于b的根节点的数据域之值,则返回,否则:若s->data小于b的根节点的数据域之值,则把s所指节点插入到左子树中,否则:把s所指节点插入到右子树中。(新插入节点总是叶子节点)

搜索二叉树删除节点

重难点

二叉搜索树的结点删除比插入较为复杂,总体来说,结点的删除可归结为三种情况:

如果结点z没有孩子节点,那么只需简单地将其删除,并修改父节点,用NULL来替换z;如果结点z只有一个孩子,那么将这个孩子节点提升到z的位置,并修改z的父节点,用z的孩子替换z;如果结点z有2个孩子,那么查找z的后继y,此外后继一定在z的右子树中,然后让y替换z

非递归实现

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)
                    {
                        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;
                    }
                }
            }
            else   //左右都不为空
            {
                Node* minRight=cur->_right;
                while(minRight->_left)
                {
                    minRight=minRight->_left;
                }
                k min = minRight->_key;
                this->Erase(min);
                
                cur->_key=min;
            }
            return true;
        }
    }
    return false;
}

递归实现

// 如果树中不存在key,返回false
// 存在,删除后,返回true
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
    {
        //找到了,root就是要删除的节点
        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* minRight=root->_right;
            while(minRight->_left)
            {
                minRight=minRight->_left;
            }
            K min=minRight->_key;
            
            //转化为root的右子树删除min
            _EraseR(root->_right,min);
            root->_key=min;
            
        }
        return true;
    }
}

到此这篇关于C++ 详解数据结构中的搜索二叉树的文章就介绍到这了,更多相关C++ 搜索二叉树内容请搜索易采站长站以前的文章或继续浏览下面的相关文章希望大家以后多多支持易采站长站!

如有侵权,请联系QQ:279390809 电话:15144810328

相关文章

  • golang用什么开发工具?

    golang用什么开发工具?

    golang用的开发工具有:1、Go Revive,是一个Go语言的代码质量检测工具;2、Go Callvis,可以用来可视化Go程序的调用图;3、Gaia,高效,快速,轻量级,并且对开发人员友好。golang用的开发工具有:1、Go Reviverevive 是一个 Go 语言的代码质量检测工具(Linter for Go),具有快速、可配置、可扩展、灵活和美观等特性,可作为 golint 的替
    2020-08-07
  • golang是多线程模式吗?

    golang是多线程模式吗?

    golang是多线程模式的,golang的线程模型是M P G模型,整体上Go程与内核线程是多对多对应的,因此首先来讲就一定是多线程的。golang是多线程模式。 由于gmp中的p与m是将p绑定与m内核线程上,而后p的最大数量有GOPROCESS确定,而M内核线程的数量会由go去限制为10K个,但是由于内核原因做不到这么多,所以这个限制就当做没有吧。拿个图明确一下Golang有些所谓的M比N模型,
    2020-08-07
  • golang用什么开发工具?

    golang用什么开发工具?

    golang用的开发工具有:1、Go Revive,是一个Go语言的代码质量检测工具;2、Go Callvis,可以用来可视化Go程序的调用图;3、Gaia,高效,快速,轻量级,并且对开发人员友好。golang用的开发工具有:1、Go Reviverevive 是一个 Go 语言的代码质量检测工具(Linter for Go),具有快速、可配置、可扩展、灵活和美观等特性,可作为 golint 的替
    2020-08-07
  • golang是单进程的吗?

    golang是单进程的吗?

    golang不是单进程的,而是多线程;golang的线程模型是M P G模型,整体上Go程与内核线程是多对多对应的,因此首先来讲就一定是多线程的。golang不是单进程的,而是多线程。Golang有些所谓的M比N模型,M个线程下可以创建N个go routine,一般而言N远大于M,本质上属于多线程模型,但是协程的调度由Go的runtime决定,强调开发者应该使用channel进行协程之间的同步。至
    2020-08-07
  • 代码详解使用Go基于WebSocket构建视频直播弹幕系统

    代码详解使用Go基于WebSocket构建视频直播弹幕系统

    (1)业务复杂度介绍开门见山,假设一个直播间同时500W人在线,那么1秒钟1000条弹幕,那么弹幕系统的推送频率就是: 500W * 1000条/秒=50亿条/秒 ,想想B站2019跨年晚会那次弹幕系统得是多么的NB,况且一个大型网站不可能只有一个直播间!使用Go做WebSocket开发无非就是三种情况:使用Go原生自带的库,也就是 golang.org/x/net ,但是这个官方库真是出了奇Bu
    2020-08-07
  • PHP语法和Go语法有什么差异?对比介绍

    PHP语法和Go语法有什么差异?对比介绍

    本篇文章给大家对比一下PHP语法和Go语法,带大家了解一下PHP语法和Go语法之间的差异。有一定的参考价值,有需要的朋友可以参考一下,希望对大家有所帮助。Go 是由 Google 设计的一门静态类型的编译型语言。它有点类似于 C,但是它包含了更多的优点,比如垃圾回收、内存安全、结构类型和并发性。它的并发机制使多核和网络机器能够发挥最大的作用。这是 GoLang 的最佳卖点之一。此外,Go 速度快,
    2020-08-07
  • golang需要什么基础?

    golang需要什么基础?

    golang需要什么基础?golang需要的基础是:Go语言语法特别简单简洁,有C的底子更好,差一些也没关系。前提是你要真心想学,才有足够的动力去学。1、初学Go语言首先弄懂基础语法和概念:基本数据类型、Struct、Array、map、Slice、指针、接口、map、内置函数,常用工具包等,还有接口和Slice的底层数据结构。这些不需要弄特别懂,能自己理解并自己描述我觉得就可以了,关键在实践和应
    2020-08-07
  • golang为什么那么火?

    golang为什么那么火?

    golang为什么那么火?golang那么火的原因:1, Concurrency的原生支持通过语言原生的Goroutine和Channel,很好的支持了Concurrency。你可以把Goroutine理解为非常轻量级的Thread。一个Goroutine只占用2KB的内存,但是一个Thread要占用1MB的内存。Goroutine的创建、销毁和切换的开销,相对于线程来说特别低。你可以随时起上千个
    2020-08-07