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

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

文章目录

前言

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

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

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

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

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

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

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

八.总结与验证

前言

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

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

typedef int ElemType;
//二叉排序树左>根>右,树中没有重复值
//二叉排序树的数据结构
typedef struct BSTNode {
	ElemType data;//数据节点类型为int
	struct 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) {//没找到返回0
		return 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;//数据节点类型为int
	struct 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) {//没找到返回0
		return 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 999999
	BSTree 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;
}

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

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

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

相关文章

Mysql：重点且常用的操作和理论知识整理 ^_^

Mysql：重点且常用的操作和理论知识整理 ^_^

目录 1 基础的命令操作 2 DDL 数据库定义语言 2.1 数据库操作 2.2 数据表操作 2.2.1 创建数据表 2.2.2 修改和删除数据表 2.2.3 添加外键 3 DML 数据库操作语言 3.1 插入语句(INSERT) 3.2 修改语句(UPDATE) 3.3 删除语句 3.3.1 DELETE命令 3.3.2 TRUNCATE命令 4 …
阅读更多...
探索C++中std::string的弱点：你可能未曾注意到的缺点

探索C++中std::string的弱点：你可能未曾注意到的缺点

C中std::string的弱点&#xff1a;你可能未曾注意到的缺点 一、背景二、性能方面的局限三、可变性带来的问题四、内存管理和指针操作五、Unicode和多字节字符集的支持六、其他替代方案七、总结 一、背景 C中std::string是一个非常重要的类&#xff0c;用于表示和处理字符串数据…
阅读更多...
前端开发必备 HTML的常用标签（二）

前端开发必备 HTML的常用标签（二）

目录 一、HTML语言 二、水平线标签 三、字体样式标签 四、注释和特殊符号 一、HTML语言 HTML&#xff08;Hypertext Markup Language&#xff09;是一种标记语言&#xff0c;用于创建网页的结构和内容。它由一系列的标签组成&#xff0c;这些标签定义了网页中各个元素的结…
阅读更多...
如何防护网站存在的sql注入攻击漏洞

如何防护网站存在的sql注入攻击漏洞

SQL注入攻击是最危险的Web漏洞之一&#xff0c;危害性极大&#xff0c;造成的后果不堪设想&#xff0c;因此受到了大家的高度重视。那么你知道SQL注入攻击防范方法有哪些吗? SQL注入是一种网站的攻击方法。它将SQL代码添加到网站前端GET POST参数中&#xff0c;并将其传递给my…
阅读更多...
MSPM0L1306例程学习-UART部分(2)

MSPM0L1306例程学习-UART部分(2)

MSPM0L1306例程学习系列 1.背景介绍 写在前边的话&#xff1a; 这个系列比较简单&#xff0c;主要是围绕TI官网给出的SDK例程进行讲解和注释。并没有针对模块的具体使用方法进行描述。所有的例程均来自MSPM0 SDK的安装包&#xff0c;具体可到官网下载并安装: https://www.ti…
阅读更多...
【 Qt 快速上手】-②- Qt 环境搭建

【 Qt 快速上手】-②- Qt 环境搭建

文章目录 1. Qt 开发工具概述1.1 Qt Creator 介绍1.2 Visual Studio 介绍1.3 Eclipse 介绍 2. Qt SDK 的下载与安装2.1 Qt SDK 的下载2.2 Qt SDK 的安装2.3 验证 Qt SDK 安装是否成功2.4 Qt 环境变量配置 1. Qt 开发工具概述 Qt 开发环境需要安装三个部分&#xff1a; C编译器…
阅读更多...
从零开始，自己搭建一个autonomous mobile robot做gazebo仿真（1）：mobile robot建模与添加差速控制器

从零开始，自己搭建一个autonomous mobile robot做gazebo仿真（1）：mobile robot建模与添加差速控制器

这样一个简单的mobile robot模型 首先写xacro文件&#xff0c;创建 link joint transmission <?xml version"1.0"?> <robot xmlns:xacro"http://www.ros.org/wiki/xacro" name"whill_modelc" ><xacro:property name"PI&q…
阅读更多...
JS-元素尺寸与位置

JS-元素尺寸与位置

通过js的方式&#xff0c;得到元素在页面中的位置 获取宽高 元素.offsetWidth 元素.offsetHeight 1&#xff09;获取元素的自身宽高、包括元素自身设置的宽高paddingborder 2&#xff09;获取出来的是数值&#xff0c;方便计算 3&#xff09;注意&#xff1a;获取的是可视…
阅读更多...
（2023版）斯坦福CS231n学习笔记：DL与CV教程 (14) | 强化学习（Robot Learning）

（2023版）斯坦福CS231n学习笔记：DL与CV教程 (14) | 强化学习（Robot Learning）

前言 &#x1f4da; 笔记专栏&#xff1a;斯坦福CS231N&#xff1a;面向视觉识别的卷积神经网络&#xff08;23&#xff09;&#x1f517; 课程链接&#xff1a;https://www.bilibili.com/video/BV1xV411R7i5&#x1f4bb; CS231n: 深度学习计算机视觉&#xff08;2017&#xf…
阅读更多...
【Unity】URP报错Object reference not set to an instance of an object

【Unity】URP报错Object reference not set to an instance of an object

使用URP之后&#xff0c;Unity报错&#xff1a;显示不正常 NullReferenceException: Object reference not set to an instance of an object UnityEngine.Rendering.Universal.UniversalAdditionalCameraData.get_cameraStack () (at Library/PackageCache/com.unity.render-p…
阅读更多...
富士康在印度受挫，在郑州建设新能源汽车工厂，还是中国制造可靠

富士康在印度受挫，在郑州建设新能源汽车工厂，还是中国制造可靠

日前消息指富士康宣布在郑州建设新能源汽车工厂&#xff0c;此前它一直推动印度制造&#xff0c;如此做法形成了鲜明对比&#xff0c;这显示出富士康在印度多番努力之后&#xff0c;终于还是认清了现实&#xff0c;印度难以担起富士康的事业。 此前富士康大举向印度转移的是手机…
阅读更多...
可视化k8s页面（Kubepi）

可视化k8s页面（Kubepi）

Kubepi是一个简单高效的k8s集群图形化管理工具&#xff0c;方便日常管理K8S集群&#xff0c;高效快速的查询日志定位问题的工具 随便在哪个节点部署&#xff0c;我这里在主节点部署 docker pull kubeoperator/kubepi-server docker run --privileged -itd --restartunless-st…
阅读更多...
探索curl的高级应用：HTTP请求的大师级技巧

探索curl的高级应用：HTTP请求的大师级技巧

探索curl的高级应用&#xff1a;HTTP请求的大师级技巧 引言高级用法概览1. HTTP请求与响应处理2. 身份验证与安全3. 进阶技巧4. Cookie管理与会话保持5. 脚本自动化 HTTP请求与响应处理1. 自定义请求头2. 发送数据3. 处理响应 身份验证与安全1. 基本认证2. 摘要认证3. HTTPS安全…
阅读更多...
力扣：494. 目标和（动态规划）（01背包）

力扣：494. 目标和（动态规划）（01背包）

题目&#xff1a; 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘’ 或 ‘-’ &#xff0c;然后串联起所有整数&#xff0c;可以构造一个 表达式 例如&#xff0c;nums [2, 1] &#xff0c;可以在 2 之前添加 ‘’ &#xff0c;在 1 之前添加…
阅读更多...
独立服务器和云服务器的区别

独立服务器和云服务器的区别

独立服务器和云服务器的区别是很多用户在选择服务器时要做的课程&#xff0c;那么独立服务器和云服务器的区别有哪些呢? 独立服务器和云服务器是两种不同的服务器部署方式&#xff0c;它们在性能、成本、资源利用、安全性和维护等方面存在显著差异。 1. **性能对比**&#xff…
阅读更多...
【CentOS 7联网】手把手解决CentOS7虚拟机的网络连接问题

【CentOS 7联网】手把手解决CentOS7虚拟机的网络连接问题

在安装CentOS7虚拟机之后发现连不上网络&#xff0c;捣鼓了好久都没有弄好&#xff0c;一路上走了很多弯路&#xff0c;希望我的经验能够帮助到大家。这里我是通过NAT连接配置静态网络的方式来连接的。 本机&#xff1a;windows1 虚拟机&#xff1a;centos7 x86_64 网络连接…
阅读更多...
Java 应用部署包优化经验分享

Java 应用部署包优化经验分享

背景 最近接手了一个 2018 年的老项目&#xff0c;因为太久远了&#xff0c;功能上的代码不敢乱动&#xff0c;虽然是老项目&#xff0c;但最近一年也在持续加功能&#xff0c;功能不稳定&#xff0c;于是我就进入了救火式改 Bug 的状态。 功能不能妄动&#xff0c;但是这个项…
阅读更多...
yum配置文件及NFS共享

yum配置文件及NFS共享

一 yum配置文件及命令 1 /etc/yum.conf //主配置文件 2 /etc/yum.repos.d/*.repo //yum仓库文件位置 写错一个字母就不行&#xff0c;可以ping www.google.com 测试网络 3 /var/log/yum.log //日志文件 二 yum命令 1 [rootlocalhost ~…
阅读更多...
“盲盒+互联网”模式下的盲盒小程序带来了哪些机遇？

“盲盒+互联网”模式下的盲盒小程序带来了哪些机遇？

近几年&#xff0c;盲盒逐渐兴起&#xff0c;深受大众的喜爱。盲盒中拥有各类随机商品&#xff0c;包括玩偶手办等&#xff0c;让消费者无法自拨。盲盒拥有神秘感和不确定性&#xff0c;消费者在购买前并不知道盲盒中是什么商品&#xff0c;因此具有较大的惊喜感&#xff0c;能…
阅读更多...
SpringBoot+beetl idea热更新解决方案

SpringBoot+beetl idea热更新解决方案

SpringBootbeetl idea热更新解决方案 第一在application中开启&#xff1a; beetl:resource-auto-check: true #热加载beetl模板&#xff0c;开发时候用第二在application中开启&#xff1a; devtools: 这个部分专门用于配置Spring Boot DevTools的相关参数。DevTools…
阅读更多...
最新文章

Copyright @ 2022~2023