首页 > 其他分享 >Inplementation of Binary Search Tree using iteration-local version 2【1月23日学习笔记】

Inplementation of Binary Search Tree using iteration-local version 2【1月23日学习笔记】

时间:2024-01-23 16:11:51浏览次数:35  
标签:Node Binary Search run 23 travptr NULL data 指针

点击查看代码
#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node* left;
    Node* right;
};

Node* newNode(int x)
{
    Node* temp = new Node;
    temp->data = x;
    temp->left = temp->right = nullptr;

    return temp;
}

/*************************wrong code*********8***************************

void insert(Node** headref, int data)
{
    Node* travptr = *headref;
    //travptr是局部变量,副本,修改副本指针的指向不会改变原指针
   
    while (travptr != NULL)             
    {
        travptr = (data > travptr->data) ? travptr->right : travptr->left;
    }

    travptr = newNode(data);
    //只能通过指向原指针的另一个指针取修改原指针
}
***************************************************************************/

void insert(Node** headref, int data)//可能跟头指针操作相关
{

    if (*headref == NULL)
    {
        *headref = newNode(data);
        return;
    }//跟头指针操作相关
     //直接修改原指针

    Node* travptr = *headref;
    Node*  run= NULL;//初始化为空

    while (travptr != NULL)//当travptr指向NULL时结束,条件更简单
    {
        run = travptr;
        travptr = (data > travptr->data) ? travptr->right : travptr->left;
    }//关键是 run,结束时 run指向待插入节点

    if (data > run->data)
        run->right = newNode(data);

    else
        run->left = newNode(data);//利用 run修改待插入节点左右link
                                            //只能通过指向原指针的另一个指针取修改原指针
}//时间复杂度:O(logn)in best case(balanced bst)

bool search(Node* travptr, int data)//没有与头指针相关操作,可以用形参(副本)
{
    while (travptr != NULL && travptr->data != data)//关注结束时
        travptr = (data > travptr->data) ? travptr->right : travptr->left;
    //结束情况:travptr指向NULL,或找到目标值

    if (travptr == NULL)
    {
        return false;
    }
    return true;//判定具体情况
}//时间复杂度:O(logn)in best case(balanced bst)

int main()
{
    Node* head = NULL;

    insert(&head, 1);
    insert(&head, 2);
    insert(&head, 3);
    insert(&head, 4);
    cout << search(head, 3) << "\t" << search(head, 10);
    return 0;
}

标签:Node,Binary,Search,run,23,travptr,NULL,data,指针
From: https://www.cnblogs.com/whvivy/p/17982700

相关文章

  • 2023京东零售技术年度盘点
    过去一年,围绕开放生态建设、低价心智等主要方向,京东零售技术团队持续攻坚。从百亿补贴、调整流量分配机制为用户提供低价品质好货,到简化商家进驻流程、优化商家体验,带动商家数量增长和平台生态活跃,再到将大模型结合到内部大量业务场景,探索效率提升……快速响应、助力业务的同时,京东......
  • macOS Sonoma 14.3 (23D56) 正式版发布,ISO、IPSW、PKG 下载 (重大更新)
    macOSSonoma14.3(23D56)正式版发布,ISO、IPSW、PKG下载(重大更新)本站下载的macOS软件包,既可以拖拽到Applications(应用程序)下直接安装,也可以制作启动U盘安装,或者在虚拟机中启动安装。另外也支持在Windows和Linux中创建可引导介质。作者主页:sysin.org更新摘要:mac......
  • macOS Sonoma 14.3 (23D56) 正式版 Boot ISO 原版可引导镜像下载 (重大更新)
    macOSSonoma14.3(23D56)正式版BootISO原版可引导镜像下载(重大更新)本站下载的macOS软件包,既可以拖拽到Applications(应用程序)下直接安装,也可以制作启动U盘安装,或者在虚拟机中启动安装。另外也支持在Windows和Linux中创建可引导介质。作者主页:sysin.org更新摘......
  • 用CI/CD工具Vela部署Elasticsearch + C# 如何使用
    Vela除了可以帮我们编译、部署程序,利用它的docker部署功能,也能用来部署其他线上的docker镜像,例如部署RabbitMQ、PostgreSql、Elasticsearch等等,便于集中管理。部署Elasticsearch创建文件夹并赋予权限:mkdir/usr/local/es/datamkdir/usr/local/es/pluginschmod777/usr/......
  • 2023京东零售技术年度盘点
    过去一年,围绕开放生态建设、低价心智等主要方向,京东零售技术团队持续攻坚。从百亿补贴、调整流量分配机制为用户提供低价品质好货,到简化商家进驻流程、优化商家体验,带动商家数量增长和平台生态活跃,再到将大模型结合到内部大量业务场景,探索效率提升……快速响应、助力业务的同时,京......
  • 【专题】2023年大语言模型综合评测报告PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=33624原文出处:拓端数据部落公众号自2022年年末以来,人工智能大模型已成为技术领域甚至全球创新领域最受关注的话题。以ChatGPT为代表的大模型产品发展迅速,预测数据显示,到2030年,AIGC市场规模有望超过万亿元。2023年,国内主要厂商也相继推出自研的大语......
  • LOJ3990/LG9602 IOI2023 足球场 题解 (区间DP+精简无用状态)
    首先考虑一个足球场长啥样才是合法的。发现一个点能只拐弯一次到达另一个点,可以分为两种情况:先左右走,再上下走或先上下走,后左右走。无论哪种情况,都要求我们走一步使得和目标点一个轴相同,再走一步使得另一个轴也相同,所以加入把每一行选择的格子看成一个区间(因为如果不连续显然是......
  • 【专题】2023年新能源汽车、智能汽车、车险行业报告汇总PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=34910本文主要研究了汽车品牌的影响力以及汽车行业的营销新增量。通过调研新能源汽车及用户需求、特点和偏好,分析了中国新能源汽车市场的发展趋势和内容生态。同时,探讨了智能汽车的发展趋势、云服务和数字化人才需求。此外,还分析了中国汽车出海、新......
  • macOS Sonoma 14.3 (23D56) 正式版 Boot ISO 原版可引导镜像下载 (重大更新)
    macOSSonoma14.3(23D56)正式版BootISO原版可引导镜像下载(重大更新)本站下载的macOS软件包,既可以拖拽到Applications(应用程序)下直接安装,也可以制作启动U盘安装,或者在虚拟机中启动安装。另外也支持在Windows和Linux中创建可引导介质。请访问原文链接:https://sys......
  • 2024-1-23AJAX的概念
    目录AJAX的概念小知识点箭头函数AJAX的作用axios的使用AJAX的概念简单可以理解为想指定的url获取指定的数据。小知识点箭头函数箭头函数是一种新的函数语法,旨在提供一种更简洁的方式来编写函数。它与传统的function相比比较容易传统函数格式varsum=function(a,b){r......