排序二叉树

参考

Binary Search Tree Visualization (usfca.edu)

一、构建排序二叉树

注意引用 tree

/**
 * 构造二叉排序树
 * @param tree
 * @param x
 */
void buildTree(BSTree &tree,ElementType &x){
    if (tree==NULL){
        tree=(BSTree) calloc(1, sizeof(BSTNode));
        tree->data=x;
        //注意
        return;
    }
    if (x>tree->data){
        buildTree(tree->rchild,x);
    }
    if (x<tree->data){
        buildTree(tree->lchild,x);
    }
    if (x==tree->data){
        return;
    }
}

二、查询排序二叉树的目标节点

注意引用 tree

//查找
int getPosition(BSTree &tree,int postion,ElementType x){
    if (tree!=NULL&&x==tree->data){
        return tree->data;
    }
    if (x>tree->data){
        return getPosition(tree->rchild,0,x);
    } else{
        return getPosition(tree->lchild,0,x);
    }
}

三、删除二叉排序树的节点

注意引用

注意左子树右子树都不为空的情况  删除的时候递归删除 因为我们不知道它的父亲节点

注意记得删除前改变被删除的位置的地址

//删除节点
void delTNode(BSTree &tree,ElementType x){
    if (tree==NULL){
        return;
    }
    BSTNode *temp=tree;
    if (x>temp->data){
        delTNode(tree->rchild,x);
    }
    if (x<temp->data){
        delTNode(tree->lchild,x);
    }
    if (x==temp->data){
        if (temp->lchild==NULL&&temp->rchild!=NULL){
            //注意记得改变此时被删除的位置的地址
            tree=temp->rchild;
            free(temp);
        }
        if (temp->rchild==NULL&&temp->lchild!=NULL){
            //注意记得改变此时被删除的位置的地址
            tree=temp->lchild;
            free(temp);
        }
        if (temp->lchild==NULL&&temp->rchild==NULL){
            //注意记得改变此时被删除的位置的地址
            tree=NULL;
            free(temp);
        }
        if (temp->lchild!=NULL&&temp->rchild!=NULL){
            //左右子树都不为空
            //找左子树的左右边
            //或者找右子树的最左边来代替
            temp=temp->lchild;
            while (temp->rchild!=NULL){
                temp=temp->rchild;
            }
            tree->data=temp->data;
            //因为这时候有俩个一样的值了 我们要确认我们要删除的是哪个值
            //因此这里应该删除这个节点的左子树上那个替死鬼
            delTNode(tree->lchild,temp->data);
        }
    }
}

 四、完整代码

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

typedef struct BSTNode{
    ElementType data;
    BSTNode *rchild;
    BSTNode *lchild;
}BSTNode,*BSTree;

/**
 * 构造二叉排序树
 * @param tree
 * @param x
 */
void buildTree(BSTree &tree,ElementType &x){
    if (tree==NULL){
        tree=(BSTree) calloc(1, sizeof(BSTNode));
        tree->data=x;
        //注意
        return;
    }
    if (x>tree->data){
        buildTree(tree->rchild,x);
    }
    if (x<tree->data){
        buildTree(tree->lchild,x);
    }
    if (x==tree->data){
        return;
    }
}

//查找
int getPosition(BSTree &tree,int postion,ElementType x){
    if (tree!=NULL&&x==tree->data){
        return tree->data;
    }
    if (x>tree->data){
        return getPosition(tree->rchild,0,x);
    } else{
        return getPosition(tree->lchild,0,x);
    }
}

//删除节点
void delTNode(BSTree &tree,ElementType x){
    if (tree==NULL){
        return;
    }
    BSTNode *temp=tree;
    if (x>temp->data){
        delTNode(tree->rchild,x);
    }
    if (x<temp->data){
        delTNode(tree->lchild,x);
    }
    if (x==temp->data){
        if (temp->lchild==NULL&&temp->rchild!=NULL){
            //注意记得改变此时被删除的位置的地址
            tree=temp->rchild;
            free(temp);
        }
        if (temp->rchild==NULL&&temp->lchild!=NULL){
            //注意记得改变此时被删除的位置的地址
            tree=temp->lchild;
            free(temp);
        }
        if (temp->lchild==NULL&&temp->rchild==NULL){
            //注意记得改变此时被删除的位置的地址
            tree=NULL;
            free(temp);
        }
        if (temp->lchild!=NULL&&temp->rchild!=NULL){
            //左右子树都不为空
            //找左子树的左右边
            //或者找右子树的最左边来代替
            temp=temp->lchild;
            while (temp->rchild!=NULL){
                temp=temp->rchild;
            }
            tree->data=temp->data;
            //因为这时候有俩个一样的值了 我们要确认我们要删除的是哪个值
            //因此这里应该删除这个节点的左子树上那个替死鬼
            delTNode(tree->lchild,temp->data);
        }
    }
}

//中序遍历 对于二叉排序树来说中序遍历就是从小到大依次排序
void inOrder(BSTree tree){
    if (tree==NULL){
        return;
    }
    inOrder(tree->lchild);
    printf("%3d",tree->data);
    inOrder(tree->rchild);
}

int main() {
    BSTree tree;
    ElementType str[7]={56,20,30,1,3,78,9};
    //注意
    tree=(BSTree) calloc(1, sizeof(BSTNode));
    tree->data=56;
    for (int i = 1; i < 7; ++i) {
        buildTree(tree,str[i]);
    }
    ElementType x;
    x=getPosition(tree,0,1);
    printf("%d\n",x);
    delTNode(tree,1);
    inOrder(tree);
    return 0;
}

 五、折半查找OJ练习

读取10个元素 87  7 60 80 59 34 86 99 21  3，然后建立二叉查找树，
中序遍历输出3  7 21 34 59 60 80 86 87 99，
针对有序后的元素，存入一个长度为10的数组中，通过折半查找找到21的下标（下标为2），
然后输出2

//折半查找
int getPosition(ElementType A[],ElementType x,int low,int high){
    if (low>=high){
        return -1;
    }
    int mid=(low+high)/2;
    if (A[mid]==x){
        return mid;
    }
    if (x>A[mid]){
        return getPosition(A,x,mid+1,high);
    } else{
        return getPosition(A,x,low,mid-1);
    }
}

完整代码 

#include <stdio.h>
#include <stdlib.h>

/**
 * 读取10个元素 87  7 60 80 59 34 86 99 21  3，然后建立二叉查找树，
 * 中序遍历输出3  7 21 34 59 60 80 86 87 99，
 * 针对有序后的元素，存入一个长度为10的数组中，通过折半查找找到21的下标（下标为2），然后输出2
 */

typedef int ElementType;

typedef struct BSTNode{
    ElementType data;
    BSTNode *rchild;
    BSTNode *lchild;
}BSTNode,*BSTree;

/**
 * 构造二叉排序树
 * @param tree
 * @param x
 */
void buildTree(BSTree &tree,ElementType &x){
    if (tree==NULL){
        tree=(BSTree) calloc(1, sizeof(BSTNode));
        tree->data=x;
        //注意
        return;
    }
    if (x>tree->data){
        buildTree(tree->rchild,x);
    }
    if (x<tree->data){
        buildTree(tree->lchild,x);
    }
    if (x==tree->data){
        return;
    }
}

//查找
int getPosition(BSTree &tree,int postion,ElementType x){
    if (tree!=NULL&&x==tree->data){
        return tree->data;
    }
    if (x>tree->data){
        return getPosition(tree->rchild,0,x);
    } else{
        return getPosition(tree->lchild,0,x);
    }
}

//删除节点
void delTNode(BSTree &tree,ElementType x){
    if (tree==NULL){
        return;
    }
    BSTNode *temp=tree;
    if (x>temp->data){
        delTNode(tree->rchild,x);
    }
    if (x<temp->data){
        delTNode(tree->lchild,x);
    }
    if (x==temp->data){
        if (temp->lchild==NULL&&temp->rchild!=NULL){
            //注意记得改变此时被删除的位置的地址
            tree=temp->rchild;
            free(temp);
        }
        if (temp->rchild==NULL&&temp->lchild!=NULL){
            //注意记得改变此时被删除的位置的地址
            tree=temp->lchild;
            free(temp);
        }
        if (temp->lchild==NULL&&temp->rchild==NULL){
            //注意记得改变此时被删除的位置的地址
            tree=NULL;
            free(temp);
        }
        if (temp->lchild!=NULL&&temp->rchild!=NULL){
            //左右子树都不为空
            //找左子树的左右边
            //或者找右子树的最左边来代替
            temp=temp->lchild;
            while (temp->rchild!=NULL){
                temp=temp->rchild;
            }
            tree->data=temp->data;
            //因为这时候有俩个一样的值了 我们要确认我们要删除的是哪个值
            //因此这里应该删除这个节点的左子树上那个替死鬼
            delTNode(tree->lchild,temp->data);
        }
    }
}

//中序遍历 对于二叉排序树来说中序遍历就是从小到大依次排序
void inOrder(BSTree tree){
    if (tree==NULL){
        return;
    }
    inOrder(tree->lchild);
    printf("%3d",tree->data);
    inOrder(tree->rchild);
}

int i=0;

//中序遍历 对于二叉排序树来说中序遍历就是从小到大依次排序
void inOrderI(BSTree tree,ElementType A[]){
    if (tree==NULL){
        return;
    }
    inOrderI(tree->lchild,A);
    A[i++]=tree->data;
    printf("%3d",tree->data);
    inOrderI(tree->rchild,A);
}

//折半查找
int getPosition(ElementType A[],ElementType x,int low,int high){
    if (low>=high){
        return -1;
    }
    int mid=(low+high)/2;
    if (A[mid]==x){
        return mid;
    }
    if (x>A[mid]){
        return getPosition(A,x,mid+1,high);
    } else{
        return getPosition(A,x,low,mid-1);
    }
}

int main() {
    BSTree tree;
    //注意
    tree=(BSTree) calloc(1, sizeof(BSTNode));
    ElementType x;
    scanf("%d",&x);
    tree->data=x;
    for (int i = 1; i <= 9; ++i) {
        scanf("%d",&x);
        buildTree(tree,x);
    }
    ElementType A[10];
    inOrderI(tree,A);
    printf("\n");
    int position=getPosition(A,21,0,9);
    printf("%d\n", position);
    return 0;
}

 

六、折半查找 （真题）中位数应用

注意最后是s / d  的位置的值

注意移动的时候数组长度是变化的 

1. 判断哪个中位数小  

保证消掉的元素个数是相等的

奇数个长度  消掉小的前面的所有元素  大的后面的所有元素

偶数个长度  消掉小的前面的所有元素及其它本身  大的后面的所有元素

2.退出循环的条件是 s1！=d1|| s2！=d2 --直到俩个数组中就s1d1都指向一个元素  s2d2同理

 

 

#include <stdio.h>

void NarrowScope(int n, int m1, int m2, int &s2, int &d1);

//不合并查找中位数--去掉数  --就是移动下标
int getMidA_B(int A[],int B[],int n){
    //分别为 A B的 首尾 中位数  所在下标位置
    int s1,s2,d1,d2,m1,m2;
    s1=s2=0;d1=d2=n-1;
    m1=(s1+d1)/2;
    m2=(s2+d2)/2;
    if (A[m1]==B[m2]){
        return A[m1];
    }
    //去掉小哪个中位数之前的数    注意分奇偶
    //去掉大的那个中位数之后的数  注意分奇偶
    //循环判断哪个中位数大--缩小范围--直到俩个数组中都只剩下一个数s1=d1 s2=d2时 小的那个即为中位数
    while (s1!=d1||s2!=d2){
        m1=(s1+d1)/2;
        m2=(s2+d2)/2;
        if (A[m1]==B[m2]){
            return A[m1];
        }
        if (A[m1]>B[m2]){
            if ((s1+d1)%2==0){
                //奇数个
                //去掉大的之后的所有数
                d1=m1;
                //去掉小的之前的所有数
                s2=m2;
            } else{
                //偶数个
                //去掉大的 之后的所有数
                d1=m1;
                //去掉小的 中位数及之前的所有数
                s2=m2+1;
            }
        }
        if (A[m1]<B[m2]){
            if ((s1+d1)%2==0){
                //奇数个
                //去掉大的之后的所有数
                d2=m2;
                //去掉小的之前的所有数
                s1=m1;
            } else{
                //偶数个
                //去掉大的 之后的所有数
                d2=m2;
                //去掉小的 中位数及之前的所有数
                s1=m1+1;
            }
        }
    }
    //注意这里 要的是s /  d  而不是m  因为最终s 与d会重合
    return A[s1]>B[s2]?B[s2]:A[s1];
}



int main() {
    int A[]={11,13,15,17,19};
    int B[]={2,4,6,8,20};
    int n=5;
    int mid=getMidA_B(A,B,n);
    printf("%d\n",mid);
    return 0;
}

 

 

 

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Python算法题集_搜索二维矩阵

Python算法题集_搜索二维矩阵

Python算法题集_搜索二维矩阵 题51&#xff1a;搜索二维矩阵1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【矩阵展开为列表二分法】2) 改进版一【行*列区间二分法】3) 改进版二【第三方模块】 4. 最优算法5. 相关资源 本文为Python算法题集之…
阅读更多...
bugku-misc隐写

bugku-misc隐写

下载文件&#xff0c;解压得到图片 没看到信息&#xff0c;试着查看图片属性 看到图片宽高不一致&#xff0c;猜测可能需要改变图片长度或者宽度 试着把图片变大&#xff0c;十进制500转16进制 得到1f4 用010打开图片 第二行第一个为宽&#xff0c;第二个为高&#xff0c;A…
阅读更多...
【计网】TCP协议安全与风险：深入探讨网络通信的基石

【计网】TCP协议安全与风险：深入探讨网络通信的基石

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;Linux ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 &#x1f310;前言 &#x1f512;正文 TCP (Transmission Control Protocol): UDP (User Datagram Protocol): HTTP (Hypertext Transfer …
阅读更多...
WordPress建站入门教程：如何创建菜单和设置前端导航菜单？

WordPress建站入门教程：如何创建菜单和设置前端导航菜单？

前面我们跟大家分享了WordPress如何上传安装WordPress主题&#xff0c;但是启用主题后前端没有看到有导航菜单&#xff0c;这是因为我们还没有创建菜单和设置导航菜单。 JianYue主题导航菜单和右上角菜单 今天boke112百科就继续跟大家分享WordPress站点如何创建菜单和设置前端…
阅读更多...
java-抢红包一些简单概念

java-抢红包一些简单概念

抢红包&#xff0c;比如微信中抢红包&#xff0c;红包金额分配使用的是二倍均值算法。 二倍均值拆包&#xff1a; 拆包要求:所有人抢到的金额之和等于红包总额&#xff0c;每个人最少抢到 0.01 元&#xff0c;每个人抢到的红包金额不要相差太大二倍均值法:假设红包总金额是X&…
阅读更多...
2024最新版正规视频影视系统源码/APP+H5视频影视源码

2024最新版正规视频影视系统源码/APP+H5视频影视源码

全新魅思V20正规视频影视系统源码&#xff0c;APPH5视频影视源码。会员花费三千购入的&#xff0c;具体搭建教程放压缩包了&#xff01; 有兴趣的下载自行研究吧&#xff0c;搭建一共要用到3个域名&#xff0c;可以拿二级域名搭建。
阅读更多...
奖励建模（Reward Modeling）实现人类对智能体的反馈

奖励建模（Reward Modeling）实现人类对智能体的反馈

奖励建模&#xff08;Reward Modeling&#xff09;是强化学习中的一个重要概念和技术&#xff0c;它主要用于训练智能体&#xff08;如AI机器人或大型语言模型&#xff09;如何更有效地学习和遵循人类期望的行为。在强化学习环境中&#xff0c;智能体通过尝试不同的行为获得环境…
阅读更多...
4月9日至10日Hack.Summit 2024亚洲首秀：Web3开发者齐聚香港数码港

4月9日至10日Hack.Summit 2024亚洲首秀：Web3开发者齐聚香港数码港

Hack.Summit() 是一系列 Web3 开发者大会。本届活动将于 2024 年 4 月 9 日至 4 月 10 日在香港数码港举行。自十年前首次举办以来&#xff0c;此次会议标志着 Hack.Summit() 首次在亚洲举办&#xff0c;香港被选为首次亚洲主办城市&#xff0c;这对 Hack VC 和该地区都具有重要…
阅读更多...
【Servlet】Servlet 详解（使用+原理）

【Servlet】Servlet 详解（使用+原理）

文章目录 1. Servlet 介绍1.1 什么是 Servlet1.2 Servlet 的主要工作 2. Servlet 程序创建步骤2.1 创建项目2.2 引入依赖2.3 创建目录2.4 编写代码2.5 打包程序2.6 部署程序2.7 验证程序 3. 使用 Smart Tomcat 进行部署3.1 安装 Smart Tomcat3.2 配置 Smart Tomcat3.3 使用 Sma…
阅读更多...
React-Redux中actions

React-Redux中actions

一、同步actions 1.概念 说明&#xff1a;在reducers的同步修改方法中添加action对象参数&#xff0c;在调用actionCreater的时候传递参数&#xff0c;数会被传递到action对象payload属性上。 2.reducers对象 说明&#xff1a;声明函数同时接受参数 const counterStorecre…
阅读更多...
【Python】科研代码学习：三 PreTrainedModel, PretrainedConfig

【Python】科研代码学习：三 PreTrainedModel, PretrainedConfig

【Python】科研代码学习&#xff1a;三 PreTrainedModel, PretrainedConfig 前言Models : PreTrainedModelPreTrainedModel 中重要的方法 tensorflow & pytorch 简单对比Configuration : PretrainedConfigPretrainedConfig 中重要的方法 前言 HF 官网API 本文主要从官网AP…
阅读更多...
乐高EV3硬件编程

乐高EV3硬件编程

文章目录&#xff1a; 一&#xff1a;软件 1.软件下载安装 2.软件的使用 二&#xff1a;乐高EV3电子元器件介绍 1.针对不同的版本 2.组合起来看 3.元器件栏 绿色部分&#xff1a;动作 橙色部分&#xff1a;流程控制 黄色部分&#xff1a;传感器 红色部分&#xff1…
阅读更多...
【PyTorch】进阶学习：探索BCEWithLogitsLoss的正确使用---二元分类问题中的logits与标签形状问题

【PyTorch】进阶学习：探索BCEWithLogitsLoss的正确使用---二元分类问题中的logits与标签形状问题

【PyTorch】进阶学习&#xff1a;探索BCEWithLogitsLoss的正确使用—二元分类问题中的logits与标签形状问题 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、Py…
阅读更多...
Python爬虫——scrapy-4

Python爬虫——scrapy-4

免责声明 本文章仅用于学习交流&#xff0c;无任何商业用途 部分图片来自尚硅谷 meta简介 在Scrapy框架中&#xff0c;可以使用meta属性来传递额外的信息。meta属性可以在不同的组件之间传递数据&#xff0c;包括爬虫、中间件和管道等。 在爬虫中&#xff0c;可以使用meta属…
阅读更多...
储能系统---交流充电桩（三）

储能系统---交流充电桩（三）

一、充电模式及其功能要求 关注公众号 --- 小Q下午茶 新国标在标准 GB/T 18487.1-2015《电动汽车传导充电系统 第1部分&#xff1a;通用要求》中规定了 4 种充电模式&#xff0c;下面将对这 4 种充电模式及其功能要求进行介绍。 1.1 、模式 1 模式 1 是指在充电系统中应使用…
阅读更多...
一次电脑感染Synaptics Pointing Device Driver病毒的经历，分享下经验

一次电脑感染Synaptics Pointing Device Driver病毒的经历，分享下经验

没想到作为使用电脑多年的老司机也会电脑中病毒&#xff0c;周末玩电脑的时候突然电脑很卡&#xff0c;然后自动重启&#xff0c;奇怪&#xff0c;之前没出现这个情况。 重启后电脑开机等了几十秒&#xff0c;打开任务管理器查看开机进程&#xff0c;果然发现有个Synaptics Po…
阅读更多...
LeetCode 2482.行和列中一和零的差值

LeetCode 2482.行和列中一和零的差值

给你一个下标从 0 开始的 m x n 二进制矩阵 grid 。 我们按照如下过程&#xff0c;定义一个下标从 0 开始的 m x n 差值矩阵 diff &#xff1a; 令第 i 行一的数目为 onesRowi 。 令第 j 列一的数目为 onesColj 。 令第 i 行零的数目为 zerosRowi 。 令第 j 列零的数目为 zer…
阅读更多...
用于审核、优化和跟踪的 18 种顶级 SEO 工具

用于审核、优化和跟踪的 18 种顶级 SEO 工具

DIY SEO工具 需要自己动手 &#xff08;DIY&#xff09; SEO 工具吗&#xff1f;以下是帮助您自己实现 SEO 目标的最佳工具&#xff1a; SEO Checker&#xff1a; 最适合评估和提高 SEO 性能。Google Analytics 4&#xff1a;最适合跟踪 SEO 结果。Moz Pro&#xff1a;最适合…
阅读更多...
清华大学1748页CTF竞赛入门指南，完整版开放下载！

清华大学1748页CTF竞赛入门指南，完整版开放下载！

CTF是一种针对信息安全领域的经济性挑战&#xff0c;旨在通过解决一系列的难题来寻找隐藏的“flag”。CTF比赛战队一般是以高校、科研单位、企业、信息安全从业者或社会团体组成。对于网安爱好者及从业者来说&#xff0c;拥有“CTF参赛经验”也是求职中的加分项。 前几天分享的…
阅读更多...
C++ Qt开发：QFileSystemWatcher文件监视组件

C++ Qt开发：QFileSystemWatcher文件监视组件

Qt 是一个跨平台C图形界面开发库&#xff0c;利用Qt可以快速开发跨平台窗体应用程序&#xff0c;在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置&#xff0c;实现图形化开发极大的方便了开发效率&#xff0c;本章将重点介绍如何运用QFileSystemWatcher组件实现对文件或…
阅读更多...
最新文章

Copyright @ 2022~2023