【算法】查找——二叉排序树
admin
2024-03-12 11:42:46
0

当线性表作为查找表的组织形式时,可以有三种查找法,其中以二分查找效率最高。但由于二分查找要求表中结点按其关键字有序组织,且不能用链表作为存储结构,因此,当表的元素插入或删除操作频繁时,为维护表的有序性,势必要移动表中大量的结点,这种由移动结点引起的额外的时间开销,就会抵消二分查找的优点。在这种情况下,可采用二叉树作为存储结构,在此将它们统称为树表。

二叉排序树

(1)二叉排序树又称为二叉查找树,是一种特殊的二叉树。其定义为:

(1)若它的左子树非空,则左子树上所有的结点的值均小于根结点的值

(2)若它的右子树非空,则右子树上所有的结点的值均大于根结点的值

(3)左、右子树本身又各是一棵二叉排序树 

(2)二叉排序树定义:

typedef struct node{
    KeyType key;

    Datatype other;

    struct node *lchild,*rchild;

}BSTNode;

1.二叉排序树的插入和生成

①在二叉排序树中插入新的结点,只要保证插入后仍符合二叉排序树的定义即可。插入过程如下:

(1)若二叉排序树为空,则待插入结点*s作为根结点插入到空树中

(2)当二叉树非空,将待插入结点的关键字s->key和树根的关键字t->key进行比较,若s->key=t->key,则说明此树中已有此结点,无需插入;若s->keykey,则将待插入结点*s插入到根的左子树中,否则将*s插入根的右子树中

(3)子树中的插入过程与步骤(1)(2)相同,直到把结点*s作为新的结点插入二叉排序树中,或直到发现该树中已有此*s结点为止。

②二叉排序树的插入算法

BSTNode *INSERTBST(BSTNode *s,BSTNode t){
    BSTNode *f,*p;
    if(t==NULL) return s;
    p=t;
    while(p!=NULL){
        f=p;
        if(s->key==p->key) return t;
        if(s->keykey) p=p->lchild;
        else p=p->rchild;
    }
    if(s->keykey) f->lchild=s;
    else f->rchild=s;
    return t;
}

③二叉排序树的生成算法 

BSTNode *CREATBST(){
    BSTNode *t,*s;
    KeyType key,endflag=0;
    DataType data;
    t=NULL;
    scanf("%d",&key);
    while(k!=endflag){
        s=malloc(BSTNode *)malloc(sizeof(BSTNode));
        s->lchild=s->rchild=NULL;
        s->key=key;
        scanf("%d",data);
        s->other=data;
        t=INSERTBST(t,s);
        scanf("%d",&key);
    }
    return 0;

2. 二叉排序树的查找 

①二叉排序树的查找算法

BSTNode *BSTSearch(BSTNode *t,KeyType t){
    BSTNode *p=t;
    while(p!=NULL){
        if(p->key==k) return p;
        if(p->key>k)
        p=p->lchild;
        else p=p->rchild;
    }

②显然,在二叉排序树上进行查找,若查找成功,则是从根结点出发走一条从根到待查结点的路径;若查找不成功,则是从根结点出发走一条从根到某个叶子结点的路径。因此,与二分法类似,和关键字比较的次数不超过树的深度。 

相关内容

热门资讯

【MySQL】锁 锁 文章目录锁全局锁表级锁表锁元数据锁(MDL)意向锁AUTO-INC锁...
【内网安全】 隧道搭建穿透上线... 文章目录内网穿透-Ngrok-入门-上线1、服务端配置:2、客户端连接服务端ÿ...
GCN的几种模型复现笔记 引言 本篇笔记紧接上文,主要是上一篇看写了快2w字,再去接入代码感觉有点...
数据分页展示逻辑 import java.util.Arrays;import java.util.List;impo...
Redis为什么选择单线程?R... 目录专栏导读一、Redis版本迭代二、Redis4.0之前为什么一直采用单线程?三、R...
【已解决】ERROR: Cou... 正确指令: pip install pyyaml
关于测试,我发现了哪些新大陆 关于测试 平常也只是听说过一些关于测试的术语,但并没有使用过测试工具。偶然看到编程老师...
Lock 接口解读 前置知识点Synchronized synchronized 是 Java 中的关键字,...
Win7 专业版安装中文包、汉... 参考资料:http://www.metsky.com/archives/350.htm...
3 ROS1通讯编程提高(1) 3 ROS1通讯编程提高3.1 使用VS Code编译ROS13.1.1 VS Code的安装和配置...
大模型未来趋势 大模型是人工智能领域的重要发展趋势之一,未来有着广阔的应用前景和发展空间。以下是大模型未来的趋势和展...
python实战应用讲解-【n... 目录 如何在Python中计算残余的平方和 方法1:使用其Base公式 方法2:使用statsmod...
学习u-boot 需要了解的m... 一、常用函数 1. origin 函数 origin 函数的返回值就是变量来源。使用格式如下...
常用python爬虫库介绍与简... 通用 urllib -网络库(stdlib)。 requests -网络库。 grab – 网络库&...
药品批准文号查询|药融云-中国... 药品批文是国家食品药品监督管理局(NMPA)对药品的审评和批准的证明文件...
【2023-03-22】SRS... 【2023-03-22】SRS推流搭配FFmpeg实现目标检测 说明: 外侧测试使用SRS播放器测...
有限元三角形单元的等效节点力 文章目录前言一、重新复习一下有限元三角形单元的理论1、三角形单元的形函数(Nÿ...
初级算法-哈希表 主要记录算法和数据结构学习笔记,新的一年更上一层楼! 初级算法-哈希表...
进程间通信【Linux】 1. 进程间通信 1.1 什么是进程间通信 在 Linux 系统中,进程间通信...
【Docker】P3 Dock... Docker数据卷、宿主机与挂载数据卷的概念及作用挂载宿主机配置数据卷挂载操作示例一个容器挂载多个目...