数据结构排序二叉树(下)

news/2024/7/27 15:52:16/文章来源:https://blog.csdn.net/qq_55383558/article/details/135635030

哎,调了几天深度学习模型,今天来更新排序二叉树

文章目录

前言

一、排序二叉树的结构定义

二、在排序二叉树添加数据

三、定义创建排序二叉树函数

四、查找一棵二叉排序树中的结点x的所在层数

五、删除二叉排序树中T关键字x的节点

六、查找二叉排序树中的所有小于key的关键字

七、已知二叉排序中每个节点值为整形,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的

八.总结与验证

前言

排序二叉树就这几个习题了,但实际上还有更难得几道习题,因为实现起来真的难,而且在使用中也难用到所以就给大家几道简单的例子,帮助大家来熟悉.

一、排序二叉树的结构定义

typedef int ElemType;
//二叉排序树左>根>右,树中没有重复值
//二叉排序树的数据结构
typedef struct BSTNode {ElemType data;//数据节点类型为intstruct BSTNode* lchild;struct BSTNode* rchild;
}BSTNode,*BSTree;

其实就是二叉树的数据结构只是对树中节点数据有约束.

二、在排序二叉树添加数据

//插入节点函数
void insertNode(BSTree& T, ElemType e) {if (T == NULL) {//找到合适的位置插入节点BSTNode* pNode = (BSTNode*)malloc(sizeof(BSTNode));assert(pNode);pNode->data = e;pNode->lchild = NULL;pNode->rchild = NULL;T = pNode;//别忘了链接上}else if (T->data > e) {//插入左子树insertNode(T->lchild, e);}else if (T->data < e) {//插入右子树insertNode(T->rchild, e);}
}

由于二叉树左>根>右所以在构建二叉树使需要满足要求.

算法思想:运用递归思想,将待插入数据与当前节点比较如果小于当前节点数据表明插入数据应插在当前节点的左子树,反之当如果插入数据比当前的节点数据大,则表明插入数据应插到当前数据的右子树,直到遇到空节点表示找到插入位置,申请节点插入即可.

三、定义创建排序二叉树函数

//定义创建二叉排序树函数
BSTNode* creatBSTree() {BSTNode* T = NULL;ElemType enternum = 999999;//999999表示退出输入printf("请输入序列(以999999作为结束标志):");while (scanf("%d", &enternum) && enternum != 999999) {insertNode(T, enternum);}return T;
}

就依次插入节点就可以了.

四、查找一棵二叉排序树中的结点x的所在层数

//例1:查找一棵二叉排序树中的结点x的所在层数
int nodelevel(BSTree T, int level,ElemType x) {if (T == NULL) {//没找到返回0return 0;}else if (T->data > x) {//左子树寻找return nodelevel(T->lchild, level+1, x);}else if (T->data < x) {//右子树寻找return nodelevel(T->rchild, level+1, x);}else {return level;//返回层次}
}

算法思想:采用递归的形式,但传参时传入一个层数,找到返回即可,注意这里层数是值传递,不是址传递.

五、删除二叉排序树中T关键字x的节点

//例2:删除二叉排序树中T关键字x的节点
//算法思想:首先找到节点x此时就要分情况讨论(1)节点既没有左孩子又没有右孩子,直接删去节点并将指针制空;
//(2)节点只有左孩子(或只有右孩子),指针指向左孩子(右孩子)并删除节点;
//(3)节点既有左孩子又有右孩子,此时有两种处理方案1.找到左子树的最大节点将右孩子链接到最大节点的右指针
//2.找到右子树的最小节点,将左孩子链接到最小节点的左指针
void deleteOperation(BSTree& T) {if (T == NULL) return;if (T->lchild == NULL && T->rchild == NULL) {free(T);T = NULL;}else if (T->lchild != NULL && T->rchild == NULL) {BSTNode* tmp = T;T = T->lchild;free(tmp);tmp = NULL;}else if (T->lchild == NULL && T->rchild != NULL) {BSTNode* tmp = T;T = T->rchild;free(tmp);tmp = NULL;}else {//既有左孩子又有右孩子BSTNode* pMaxnode = T->lchild;while (pMaxnode->rchild != NULL) {pMaxnode = pMaxnode->rchild;}pMaxnode->rchild = T->rchild;BSTNode* tmp = T;T = T->lchild;free(tmp);tmp = NULL;}
}
//查找并删除节点
void deletenode(BSTree &T,ElemType x) {if (T != NULL) {if (T->data == x) {deleteOperation(T);}else if (T->data < x) {deletenode(T->rchild, x);}else {deletenode(T->lchild, x);}}}

这个算法还有一个思想就是找到左子树最大的节点复制到删除节点上,递归在左子树删除左子树最大节点.

字有点丑见谅.

六、查找二叉排序树中的所有小于key的关键字

//例3:查找二叉排序树中的所有小于key的关键字
void getSmallerkey(BSTree T, ElemType key) {if (T != NULL) {getSmallerkey(T->lchild, key);if (T->data < key) {printf("%d ", T->data);getSmallerkey(T->rchild, key);}}
}

七、已知二叉排序中每个节点值为整形,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的

//例4:已知二叉排序中每个节点值为整形,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的节点
//定义递归删除树函数
void deleteFunc(BSTree& T) {//递归删除树if (T != NULL) {deleteFunc(T->lchild);deleteFunc(T->rchild);free(T);T = NULL;}
}
//定义删除小于x节点的函数(采用先序遍历的思想)
void deleteSmallernode(BSTree &T,ElemType x) {if (T != NULL) {if (T->data == x) {//根节点等于x说明左子树都小于x递归删除deleteFunc(T->lchild);}else if (T->data < x) {//根节点小于x左子树均小于x,删除根节点在递归删除右子树小于x的节点deleteFunc(T->lchild);BSTNode* tmp = T;T = T->rchild;free(tmp);tmp = NULL;deleteSmallernode(T, x);}else {//根节点大于x递归删除左子树小于x的节点deleteSmallernode(T->lchild, x);}}
}

八.总结与验证

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
typedef int ElemType;
//二叉排序树左>根>右,树中没有重复值
//二叉排序树的数据结构
typedef struct BSTNode {ElemType data;//数据节点类型为intstruct BSTNode* lchild;struct BSTNode* rchild;
}BSTNode,*BSTree;
//插入节点函数
void insertNode(BSTree& T, ElemType e) {if (T == NULL) {//找到合适的位置插入节点BSTNode* pNode = (BSTNode*)malloc(sizeof(BSTNode));assert(pNode);pNode->data = e;pNode->lchild = NULL;pNode->rchild = NULL;T = pNode;//别忘了链接上}else if (T->data > e) {//插入左子树insertNode(T->lchild, e);}else if (T->data < e) {//插入右子树insertNode(T->rchild, e);}
}
//定义创建二叉排序树函数
BSTNode* creatBSTree() {BSTNode* T = NULL;ElemType enternum = 999999;//999999表示退出输入printf("请输入序列(以999999作为结束标志):");while (scanf("%d", &enternum) && enternum != 999999) {insertNode(T, enternum);}return T;
}
//中序遍历二叉排序树
void inorderTraverse(BSTree T) {if (T != NULL) {inorderTraverse(T->lchild);printf("%d ", T->data);inorderTraverse(T->rchild);}
}
//先序遍历二叉排序树
void preorderTraverse(BSTree T) {if (T != NULL) {printf("%d ", T->data);preorderTraverse(T->lchild);preorderTraverse(T->rchild);}
}
//遍历二叉排序树(先,中)
void Traverse(BSTree T) {//这函数主要是用来验证printf("中序遍历结果:");inorderTraverse(T);printf("\n");printf("先序遍历结果:");preorderTraverse(T);printf("\n");
}
//例1:查找一棵二叉排序树中的结点x的所在层数
int nodelevel(BSTree T, int level,ElemType x) {if (T == NULL) {//没找到返回0return 0;}else if (T->data > x) {//左子树寻找return nodelevel(T->lchild, level+1, x);}else if (T->data < x) {//右子树寻找return nodelevel(T->rchild, level+1, x);}else {return level;//返回层次}
}
//例2:删除二叉排序树中T关键字x的节点
//算法思想:首先找到节点x此时就要分情况讨论(1)节点既没有左孩子又没有右孩子,直接删去节点并将指针制空;
//(2)节点只有左孩子(或只有右孩子),指针指向左孩子(右孩子)并删除节点;
//(3)节点既有左孩子又有右孩子,此时有两种处理方案1.找到左子树的最大节点将右孩子链接到最大节点的右指针
//2.找到右子树的最小节点,将左孩子链接到最小节点的左指针
void deleteOperation(BSTree& T) {if (T == NULL) return;if (T->lchild == NULL && T->rchild == NULL) {free(T);T = NULL;}else if (T->lchild != NULL && T->rchild == NULL) {BSTNode* tmp = T;T = T->lchild;free(tmp);tmp = NULL;}else if (T->lchild == NULL && T->rchild != NULL) {BSTNode* tmp = T;T = T->rchild;free(tmp);tmp = NULL;}else {//既有左孩子又有右孩子BSTNode* pMaxnode = T->lchild;while (pMaxnode->rchild != NULL) {pMaxnode = pMaxnode->rchild;}pMaxnode->rchild = T->rchild;BSTNode* tmp = T;T = T->lchild;free(tmp);tmp = NULL;}
}
//查找并删除节点
void deletenode(BSTree &T,ElemType x) {if (T != NULL) {if (T->data == x) {deleteOperation(T);}else if (T->data < x) {deletenode(T->rchild, x);}else {deletenode(T->lchild, x);}}}
//例3:查找二叉排序树中的所有小于key的关键字
void getSmallerkey(BSTree T, ElemType key) {if (T != NULL) {getSmallerkey(T->lchild, key);if (T->data < key) {printf("%d ", T->data);getSmallerkey(T->rchild, key);}}
}
//例4:已知二叉排序中每个节点值为整形,采用二叉链表存储,编写算法删除二叉排序树中所有关键字小于x的节点
//定义递归删除树函数
void deleteFunc(BSTree& T) {//递归删除树if (T != NULL) {deleteFunc(T->lchild);deleteFunc(T->rchild);free(T);T = NULL;}
}
//定义删除小于x节点的函数(采用先序遍历的思想)
void deleteSmallernode(BSTree &T,ElemType x) {if (T != NULL) {if (T->data == x) {//根节点等于x说明左子树都小于x递归删除deleteFunc(T->lchild);}else if (T->data < x) {//根节点小于x左子树均小于x,删除根节点在递归删除右子树小于x的节点deleteFunc(T->lchild);BSTNode* tmp = T;T = T->rchild;free(tmp);tmp = NULL;deleteSmallernode(T, x);}else {//根节点大于x递归删除左子树小于x的节点deleteSmallernode(T->lchild, x);}}
}
int main() {//创建一棵二叉排序树//8 5 4 7 9 10 999999BSTree T = creatBSTree();Traverse(T);printf("\n");int a = 10;printf("数据节点为%d的节点所在层次:%d\n", a,nodelevel(T, 1, a));printf("删除数据节点前树的结构\n");Traverse(T);deletenode(T, 5);printf("删除数据节点后树的结构\n");Traverse(T);printf("比8小的数据节点有:");getSmallerkey(T, 8);printf("\n");int b = 8;printf("删除比%d小的所有节点前\n",b);Traverse(T);deleteSmallernode(T, b);printf("删除比%d小的所有节点后\n", b);Traverse(T);return 0;
}

兄弟们马上要到图啦,最有意思的一部分要到啦.加油哦

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

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

相关文章

【小笔记】算法训练基础超参数调优思路

【小笔记】算法训练基础超参数调优思路

【学而不思则罔&#xff0c;思维不学则怠】 本文总结一下常见的一些算法训练超参数调优思路&#xff08;陆续总结更新&#xff09;&#xff0c;包括&#xff1a; batchsize学习率epochsdropout&#xff08;待添加&#xff09; Batch_size 2023.9.29 简单来说&#xff0c;较…
阅读更多...
Kotlin程序设计（二）面向对象

Kotlin程序设计（二）面向对象

Kotlin程序设计中级篇 我们在前面已经学习了Kotlin程序设计的基础篇&#xff0c;本章我们将继续介绍更多Kotlin特性&#xff0c;以及面向对象编程。 函数 其实函数我们在一开始就在使用了&#xff1a; fun main() {println("Hello World") }我们程序的入口点就是…
阅读更多...
day3：基于UDP模型的简单文件下载

day3：基于UDP模型的简单文件下载

思维导图 tftp文件下载客户端实现 #include <head.h> #define SER_PORT 69 #define SER_IP "192.168.125.223" int link_file() {int sfdsocket(AF_INET,SOCK_DGRAM,0);if(sfd-1){perror("socket error");return -1;}return sfd; } int filedownloa…
阅读更多...
【Spring Cloud Alibaba】Sentinel 服务熔断与流量控制

【Spring Cloud Alibaba】Sentinel 服务熔断与流量控制

目录 前言 一、Sentinel 入门 1.1 什么是 Sentinel ? 1.2 微服务集成 Sentinel 1.3 安装Sentinel控制台 二、Jmeter 压力测试工具 2.1 Jmeter 介绍 2.2 Jmeter 安装 2.3 接口测试 三、Sentinel 使用 3.1 限流规则 3.1.1 warm up(预热模式) 3.1.2 排队等待 3.1.3…
阅读更多...
mathtype2024版本下载与安装（mac版本也包含在内）

mathtype2024版本下载与安装（mac版本也包含在内）

安装包补丁主要是mathtype的安装包&#xff0c;与它的补丁。 详细安装过程&#xff1a; step1&#xff1a; 使用方法是下载完成后先安装MathType-win-zh.exe文件&#xff0c;跟着步骤走直接安装就行。 step2&#xff1a; 关闭之后&#xff0c;以管理员身份运行MathType7PJ.exe…
阅读更多...
【数据结构和算法】反转链表

【数据结构和算法】反转链表

其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 2.1 方法一&#xff1a;迭代&#xff08;双指针&#xff09; 2.2 方法二&#xff1a;递归 三、代码 3.…
阅读更多...
survey和surveyCV：如何用R语言进行复杂抽样设计、权重计算和10折交叉验证？

survey和surveyCV：如何用R语言进行复杂抽样设计、权重计算和10折交叉验证？

一、引言 在实际调查和研究中&#xff0c;我们往往面临着样本选择的复杂性。复杂抽样设计能够更好地反映真实情况&#xff0c;提高数据的代表性和可靠性。例如&#xff0c;多阶段抽样可以有效地解决大规模调查的问题&#xff0c;整群抽样能够在保证样本的随机性的同时减少资源消…
阅读更多...
网络安全全栈培训笔记（53-WEB攻防-通用漏洞跨域CORS资源JSONP回调域名接管劫持）

网络安全全栈培训笔记（53-WEB攻防-通用漏洞跨域CORS资源JSONP回调域名接管劫持）

第54天 WEB攻防-通用漏洞&跨域CORS资源&JSONP回调&域名接管劫持 知识点&#xff1a; 1、子域名接管检测&探针&利用 2、C0SP跨域资源检测&探针&利用 3、JSONP跨域回调-检侧&探针&利用 #前置知识点&#xff1a; 同源策路(SOP),“同源”包…
阅读更多...
centos7配置时间同步网络时间

centos7配置时间同步网络时间

centos7配置时间同步网络时间 1、安装 NTP 工具。 sudo yum install -y ntp2启动 NTP 服务。 sudo systemctl start ntpd3、将 NTP 服务设置为开机自启动。 sudo systemctl enable ntpd4、验证 date
阅读更多...
【特征工程】分类变量：MultiLabelBinarizer对多标签数据进行编码

【特征工程】分类变量：MultiLabelBinarizer对多标签数据进行编码

MultiLabelBinarizer 说明介绍 1. MultiLabelBinarizer 是什么&#xff1f; MultiLabelBinarizer是scikit-learn库中的一个用于处理多标签数据的编码器。通常用于将多标签的分类任务中的标签转化为二进制形式&#xff0c;便于机器学习模型的处理。该编码器的主要目标是将每个…
阅读更多...
【网络安全】【密码学】【北京航空航天大学】实验一、数论基础（上）【C语言和Java实现】

【网络安全】【密码学】【北京航空航天大学】实验一、数论基础（上）【C语言和Java实现】

实验一、数论基础&#xff08;上&#xff09; 一、实验目的 1、通过本次实验&#xff0c;熟悉相关的编程环境&#xff0c;为后续的实验做好铺垫&#xff1b; 2、回顾数论学科中的重要基本算法&#xff0c;并加深对其的理解&#xff0c;为本学期密码学理论及实验课程打下良好…
阅读更多...
《ARM Linux内核源码剖析》读书笔记——0号进程(init_task)的创建时机

《ARM Linux内核源码剖析》读书笔记——0号进程(init_task)的创建时机

最近在读《ARM Linux内核源码剖析》&#xff0c;一直没有看到0号进程&#xff08;init_task进程)在哪里创建的。直到看到下面这篇文章才发现书中漏掉了set_task_stack_end_magic(&init_task)这行代码。 下面这篇文章提到&#xff1a;start_kernel()上来就会运行 set_task_…
阅读更多...
如何用MetaGPT帮你写一个贪吃蛇的小游戏项目

如何用MetaGPT帮你写一个贪吃蛇的小游戏项目

如何用MetaGPT帮你写一个贪吃蛇的小游戏项目 MetaGPT是基于大型语言模型(LLMs)的多智能体写作框架&#xff0c;目前在Github开源&#xff0c;其Start数量也是比较高的&#xff0c;是一款非常不错的开源框架。 下面将带你进入MetaGPT的大门&#xff0c;开启MetaGPT的体验之旅。…
阅读更多...
大创项目推荐 深度学习手势识别算法实现 - opencv python

大创项目推荐 深度学习手势识别算法实现 - opencv python

文章目录 1 前言2 项目背景3 任务描述4 环境搭配5 项目实现5.1 准备数据5.2 构建网络5.3 开始训练5.4 模型评估 6 识别效果7 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习手势识别算法实现 - opencv python 该项目较为新颖…
阅读更多...
推荐一个页面引导库 driver.js

推荐一个页面引导库 driver.js

页面引导功能是 web 开发中常见的一个功能。通过页面引导功能&#xff0c;你可以让用户第一时间熟悉你的页面功能。今天给大家推荐一个页面引导库 driver.js。 简介 driver.js 是一款用原生 js 实现的页面引导库&#xff0c;上手非常简单&#xff0c;体积在 gzip 压缩下仅仅 5…
阅读更多...
MongoDB面试系列-01

MongoDB面试系列-01

1. MongoDB 是什么&#xff1f; MongoDB是由C语言编写的&#xff0c;是一个基于分布式文件存储的开源数据库系统。再高负载的情况下&#xff0c;添加更多的节点&#xff0c;可以保证服务器性能。MongoDB旨在给Web应用提供可扩展的高性能数据存储解决方案。 MongoDB将数据存储…
阅读更多...
Shopify绑定Facebook收费吗？付款方式是什么？-站斧浏览器

Shopify绑定Facebook收费吗？付款方式是什么？-站斧浏览器

Shopify绑定Facebook收费吗&#xff1f; 答案是&#xff1a;Shopify绑定Facebook并不收取额外费用。Shopify和Facebook之间的绑定是免费的&#xff0c;卖家可以充分利用这一功能来扩展他们的在线业务。通过将商店与Facebook Page相连接&#xff0c;卖家可以将产品目录同步到Fa…
阅读更多...
LeetCode 41 缺失的第一个正数

LeetCode 41 缺失的第一个正数

题目描述 缺失的第一个正数 给你一个未排序的整数数组 nums &#xff0c;请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,0] 输出&#xff1a;3示例 2&#xff…
阅读更多...
rabbitmq-java基础详解

rabbitmq-java基础详解

一、rabbitmq是什么&#xff1f; 1、MQ定义 MQ&#xff08;Message Queue&#xff09;消息队列 主要解决&#xff1a;异步处理、应用解耦、流量削峰等问题&#xff0c;是分布式系统的重要组件&#xff0c;从而实现高性能&#xff0c;高可用&#xff0c;可伸缩和最终一致性的架…
阅读更多...
NLP技术在搜索推荐场景中的应用

NLP技术在搜索推荐场景中的应用

NLP技术在搜索推荐中的应用非常广泛&#xff0c;例如在搜索广告的CTR预估模型中&#xff0c;NLP技术可以从语义角度提取一些对CTR预测有效的信息&#xff1b;在搜索场景中&#xff0c;也经常需要使用NLP技术确定展现的物料与搜索query的相关性&#xff0c;过滤掉相关性较差的物…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业