西南交通大学【数据结构实验8】

实验内容及要求： 

编写控制台应用程序，提供以下菜单项：

  1. 插入元素

从键盘输入若干两两互不相同的非0整数，直到输入0时停止。将输入的所有非0整数按输入次序插入二叉排序树(初始时是空树)。

插入某个非0整数时，若该整数已在二叉排序树中，则插入该整数失败(应显示提示信息)。

全部整数插入结束后，显示成功插入的整数个数。

  1. 删除元素

输入一个整数，若它在二叉排序树中，则删除它（提示删除成功与失败）。

  1. 输出

输出二叉排序树的先序和中序递归遍历结点访问次序。

  1. 结束程序

实验目的：掌握二叉排序树插入、删除元素的基本算法。

数据结构设计简要描述：

将int型作为此次实验的关键字，通过自定义二叉排序树节点结构存储二叉排序树

// 将int作为元素类型typedef int elem;// 自定义二叉排序树节点类型typedef struct node{elem data;// 左子树 右子树struct node* lchild, * rchild;}BSTNode, * BSTree;

算法设计简要描述：

创建二叉排序树采用逐个读取value值创建二叉排序树节点，然后逐个插入进二叉树。在插入时先判断此节点的值是否已存在，若存在则插入失败并释放该节点空间。若不存在则通过逐个与树中各节点比较值大小不断向下，得到插入位置，进行节点的插入。

删除节点时先对预删除的节点的值进行查找，若查找失败则删除失败。若查找成功则分为三种情况删除：左右子树均存在、只存在左子树或右子树、叶子结点。后两种情况较为简单不需复杂的变换：叶子结点直接删除，只有一方子树的将子树接到删除节点位置即可。若是左右子树均存在，需找到删除节点左子树中的最大值节点，将此节点接到删除节点的位置，将删除节点的右子树接到此节点的右子树上。

遍历操作采用中序递归遍历和先序递归遍历。

输入/输出设计简要描述：

输入：直接在控制台输入全部整数，两两之间用空格间隔，以0作为结尾代表输入结束。

输出：根据输入操作的不同将不同的结果展示在控制台

编程语言说明：

    使用Visual Studio Code编程。 主要代码采用C语言实现 ；动态存储分配采用C++的new和delete操作符实现；输入与输出采用C++的文件流对象和cout流；程序注释采用C/C++规范。  

主要函数说明：

// 在二叉排序树中查找BSTNode* SearchBST(BSTree bt, elem key);// 在二叉排序树中插入void Insert(BSTree& bt, BSTNode* p, int& count);// 创建二叉排序树void CreBst(BSTree& bt);// 删除二叉排序树中的节点void erase(BSTree& bt, elem key);// 中序递归遍历void Inorder(BSTree T);// 先序递归遍历void Preorder(BSTree T);// 删除功能void Delete(BSTree& bt);// 释放二叉排序树空间void clear(BSTree& bt);

程序测试简要报告：

测试样例（1）

程序输入

二叉排序树示意图

功能测试

结论

程序输出结果与期望输出结果相符。

测试样例（2）

程序输入

二叉排序树示意图

功能测试

结论

程序输出结果与期望输出结果相符。

源程序代码：

#include <iostream>using namespace std;// 将int作为元素类型typedef int elem;// 自定义二叉排序树节点类型typedef struct node{elem data;// 左子树 右子树struct node* lchild, * rchild;}BSTNode, * BSTree;// 在二叉排序树中查找BSTNode* SearchBST(BSTree bt, elem key) {// 若bt不为空且bt不是要查找的值while (bt && bt->data != key){// 如果key比bt小则转到左子树if (key < bt->data) {bt = bt->lchild;}else {// 否则转到右子树bt = bt->rchild;}}// 返回bt 若返回的是NULL则表示未找到return bt;}// 在二叉排序树中插入void Insert(BSTree& bt, BSTNode* p, int& count) {// bt为二叉排序树 p为要插入的节点 count记录已插入的个数// flag为查找p的值是否已在排序二叉树中 若为NULL表示不在可以插入BSTNode* flag = SearchBST(bt, p->data);if (!flag) {// parent为双亲节点BSTNode* parent = NULL;// pt为插入的位置节点BSTNode* pt = bt;// 通过p的值不断和二叉排序树中的值不断比较找出ptwhile (pt){parent = pt;if (p->data < pt->data) {pt = pt->lchild;}else {pt = pt->rchild;}}// 如果parent为空表示二叉排序树是空树if (parent) {// 比parent小则是左子树if (p->data < parent->data) {parent->lchild = p;}else {// 否则是右子树parent->rchild = p;}}else {bt = p;}// 个数加一count++;}else {// 如果flag不为空说明p值已在二叉排序树中存在 插入失败cout << p->data << "插入失败" << endl;delete p;}}// 创建二叉排序树void CreBst(BSTree& bt) {int value;int count = 0;cout << "请输入整数: ";cin >> value;// 如果value不为0 则插入while (value != 0){// 创建以value为值的节点BSTNode* temp = new BSTNode;temp->data = value;temp->lchild = NULL;temp->rchild = NULL;// 插入Insert(bt, temp, count);// 继续读取valuecin >> value;}cout << "成功插入 " << count << " 个数" << endl;}// 删除二叉排序树中的节点void erase(BSTree& bt, elem key) {// f为p的双亲节点BSTNode* f = NULL;// p为位置节点BSTNode* p = bt;// 通过不断比较查找到pwhile (p && key != p->data){f = p;if (key < p->data) {p = p->lchild;}else {p = p->rchild;}}// 如果p为空 说明不存在key值节点 删除失败if (!p) {cout << "查找失败 删除失败" << endl;return;}// pl为删除节点的左子树BSTNode* pl = p->lchild;// pr为删除节点的右子树BSTNode* pr = p->rchild;BSTNode* ps;// 替代p节点位置的节点BSTNode* s;// 如果左右子树都存在 查找左子树中最大值if (pl && pr) {ps = NULL;s = pl;while (s->rchild){ps = s;s = s->rchild;}if (!ps) {pl = s->lchild;}else {ps->rchild = s->lchild;}s->lchild = pl;s->rchild = pr;}else if (pl) {// 只存在左子树s = pl;}else {// 只存在右子树s = pr;}// 如果f为空 说明删除根节点if (!f) {bt = s;}else if (f->lchild == p) {f->lchild = s;}else {f->rchild = s;}delete p;cout << "删除成功" << endl;}// 中序递归遍历void Inorder(BSTree T) {/*此算法采用递归方式实现中序遍历*/if (T) {Inorder(T->lchild);cout << T->data << " ";Inorder(T->rchild);}}// 先序递归遍历void Preorder(BSTree T) {/*此算法采用递归方式实现先序遍历*/if (T) {cout << T->data << " ";Preorder(T->lchild);Preorder(T->rchild);}}// 删除功能void Delete(BSTree& bt) {int value;cout << "请输入一个整数: ";cin >> value;erase(bt, value);}// 释放二叉排序树空间void clear(BSTree& bt) {if (bt) {clear(bt->lchild);clear(bt->rchild);delete bt;}}int main(void) {// 选项变量int choose;BSTree bt = NULL;// 标志变量 控制循环int flag = 1;while (flag){cout << "------------------------------------------------------" << endl;cout << "-      1.插入元素                                    -" << endl;cout << "-      2.删除元素                                    -" << endl;cout << "-      3.输出                                        -" << endl;cout << "-      4.结束程序                                    -" << endl;cout << "------------------------------------------------------" << endl;cout << "请输入选项: ";cin >> choose;// 防止选项输入导致出错if (cin.fail()) {cin.clear();cin.ignore(10, '\n');}switch (choose){case 1:CreBst(bt);system("pause");system("cls");break;case 2:if (!bt) {cout << "二叉排序树是空树" << endl;}else {Delete(bt);}system("pause");system("cls");break;case 3:cout << "先序顺序: ";Preorder(bt);cout << "\n中序顺序: ";Inorder(bt);cout << endl;system("pause");system("cls");break;case 4:flag = 0;clear(bt);break;default:cout << "请输入有效选项!!!" << endl;system("pause");system("cls");break;}}return 0;}

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

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

相关文章

Python从入门到精通九：Python异常、模块与包

Python从入门到精通九：Python异常、模块与包

了解异常 什么是异常 当检测到一个错误时&#xff0c;Python解释器就无法继续执行了&#xff0c;反而出现了一些错误的提示&#xff0c;这就是所谓的“异常”, 也就是我们常说的BUG bug单词的诞生 早期计算机采用大量继电器工作&#xff0c;马克二型计算机就是这样的。 19…
阅读更多...
matlab 最小二乘拟合平面（拉格朗日乘子法）

matlab 最小二乘拟合平面（拉格朗日乘子法）

目录 一、算法原理二、代码实现三、结果展示本文由CSDN点云侠原创，原文链接。博客长期更新，爬虫自重。 一、算法原理 设拟合出的平面方程为： a x + b y &#
阅读更多...
各地加速“双碳”落地，数字能源供应商怎么选？

各地加速“双碳”落地，数字能源供应商怎么选？

作者 | 曾响铃 文 | 响铃说 随着我国力争2030年前实现“碳达峰”、2060年前实现“碳中和”的“双碳”目标提出&#xff0c;为各地区、各行业的低碳转型和绿色可持续发展制定“倒计时”时间表&#xff0c;一场围绕“数字能源”、“智慧能源”、“新能源”等关键词的创新探索进…
阅读更多...
HTML---列表.表格.媒体元素

HTML---列表.表格.媒体元素

文章目录 前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据总结 一.列表 无序列表 HTML中的无序列表&#xff08;Unordered List&#xff09;用于显示一组项目&#xff0c;每个项目之前没有特定的顺序或编号。无序列表使用<ul>标签来定义&#xff0c;每…
阅读更多...
Pearson、Spearman 相关性分析使用

Pearson、Spearman 相关性分析使用

介绍 Pearson 积差相关系数衡量了两个定量变量之间的线性相关程度。 用来衡量两个数据集的线性相关程度&#xff0c;仅当一个变量的变化与另一个变量的比例变化相关时&#xff0c;关系才是线性的。 Spearman等级相关系数则衡量分级定序变量之间的相关程度。斯皮尔曼相关系数不…
阅读更多...
GEE：重分类

GEE：重分类

作者：CSDN @ _养乐多_ 本文记录了在 Google Earth Engine（GEE）平台上对一副类别图像进行重分类的代码。并以 COPERNICUS/Landcover/100m/Proba-V-C3/Global 数据集中的土地利用数据为例。 结果如下图所示， 文章目录 一、核心函数二、示例代码三、代码链接一、核心函数 核…
阅读更多...
2-Spring

2-Spring

2-Spring 文章目录 2-Spring项目源码地址Spring概述Spring特点&#xff08;优点&#xff09;Spring相关学习网站基于Maven的Spring框架导入Spring的组成及拓展 Spring-IOC--原型理解IOC-原型--示例开发示例-常规开发示例-Set函数&#xff08;IOC原型&#xff09;开发示例-对比思…
阅读更多...
HTML实现页面

HTML实现页面

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>工商银行电子汇款单</title> </head> &…
阅读更多...
Windows使用selenium操作浏览器爬虫

Windows使用selenium操作浏览器爬虫

以前的大部分程序都是操作Chrome&#xff0c;很少有操作Edge&#xff0c;现在以Edge为例。 Selenium本身是无法直接控制浏览器的&#xff0c;不同的浏览器需要不同的驱动程序&#xff0c;Google Chrome需要安装ChromeDriver、Edge需要安装Microsoft Edge WebDriver&#xff0c…
阅读更多...
聚观早报 |一加12首销；华为智能手表释放科技温暖

聚观早报 |一加12首销；华为智能手表释放科技温暖

【聚观365】12月12日消息 一加12首销 华为智能手表释放科技温暖 卡尔动力获地平线战略投资 英伟达希望在越南建立基地 努比亚Z60 Ultra影像规格揭晓 一加12首销 现在有最新消息&#xff0c;近日一加12该机已于昨日开售&#xff0c;售价4299元起。 外观方面&#xff0c;全…
阅读更多...
源码角度简单介绍LinkedList

源码角度简单介绍LinkedList

LinkedList是一种常见的数据结构&#xff0c;但是大多数开发者并不了解其底层实现原理&#xff0c;以至于存在很多误解&#xff0c;在这篇文章中&#xff0c;将带大家一块深入剖析LinkedList的源码&#xff0c;并为你揭露它们背后的真相。首先想几个问题&#xff0c;例如&#…
阅读更多...
【启扬方案】启扬储能管理平板助力储能电站实现智能且高效化运行

【启扬方案】启扬储能管理平板助力储能电站实现智能且高效化运行

在储能领域&#xff0c;储能电站扮演着重要角色&#xff0c;储能电站技术的应用贯穿于电力系统发电、输电、配电、用电的各个环节。实现电力系统削峰填谷、可再生能源发电波动平滑与跟踪计划处理、高效系统调频&#xff0c;增加供电的可靠性。 但随着储能电⼒系统建设发展得越来…
阅读更多...
java开发的智能聊天机器人_超级AI_支持自动绘画功能

java开发的智能聊天机器人_超级AI_支持自动绘画功能

支持Web、Android、IOS、H5等多终端应用。它使用OpenAI的ChatGPT模型实现智能聊天机器人&#xff0c;并支持绘图自动生成Vincent图。未来还将接入国内大型AI模型&#xff0c;如文心一言、统一千问、MOSS等模型&#xff0c;并不断更新以满足用户需求。 AI大脑软件中的AI绘画功能…
阅读更多...
GNN 学习笔记

GNN 学习笔记

稍微看一下之后备用。 【图神经网络综述】GNN原理&#xff0b;落地应用实现框架全解_gnn实现-CSDN博客 GNN相比CNN最大的区别在于数据结构&#xff0c;CNN一般作用在二维、三维数据里&#xff0c;如图像、表格数据等&#xff0c;可以进行卷积操作。而GNN作用在一个由节点和边…
阅读更多...
Baumer工业相机堡盟工业相机如何通过BGAPISDK获取相机的各种信息如SN/ID等等（C#）

Baumer工业相机堡盟工业相机如何通过BGAPISDK获取相机的各种信息如SN/ID等等（C#）

Baumer工业相机堡盟工业相机如何通过BGAPISDK获取相机的各种信息如SN/ID等等&#xff08;C#&#xff09; Baumer工业相机Baumer工业相机通过SDK获取相关生产信息的技术背景通过SDK获取相机信息的代码分析获取Baumer工业相机相关信息Baumer工业相机相关参数信息获取的测试 Baume…
阅读更多...
2. 如何通过公网IP端口映射访问到设备的vmware虚拟机的ubuntu服务器

2. 如何通过公网IP端口映射访问到设备的vmware虚拟机的ubuntu服务器

文章目录 1. 主机设备是Windows 11系统2. 安装vmware虚拟机3. 创建ubuntu虚拟机&#xff08;据说CentOS 7 明年就不维护了&#xff0c;就不用这个版本的linux了&#xff09;4. 安装nginx服务:默认端口805. 安装ssh服务:默认端口226. 设置主机 -> ubuntu的端口映射7. 设置路由…
阅读更多...
kafka配置多个消费者groupid kafka多个消费者消费同一个partition（java）

kafka配置多个消费者groupid kafka多个消费者消费同一个partition（java）

目录 1- 单播模式&#xff0c;只有一个消费者组2- 广播模式&#xff0c;多个消费者组3- Java实践 kafka是由Apache软件基金会开发的一个开源流处理平台。kafka是一种高吞吐量的分布式发布订阅消息系统&#xff0c;它可以处理消费者在网站中的所有动作流数据。 kafka中partition…
阅读更多...
【Spark精讲】Spark作业执行原理

【Spark精讲】Spark作业执行原理

基本流程 用户编写的Spark应用程序最开始都要初始化SparkContext。 用户编写的应用程序中&#xff0c;每执行一个action操作&#xff0c;就会触发一个job的执行&#xff0c;一个应用程序中可能会生成多个job执行。一个job如果存在宽依赖&#xff0c;会将shuffle前后划分成两个…
阅读更多...
Redis系列之简单实现watchDog自动续期机制

Redis系列之简单实现watchDog自动续期机制

在分布锁的实际使用中&#xff0c;可能会遇到一种情况&#xff0c;一个业务执行时间很长&#xff0c;已经超过redis加锁的时间&#xff0c;也就是锁已经释放了&#xff0c;但是业务还没执行完成&#xff0c;这时候其它线程还是可以获取锁&#xff0c;那就没保证线程安全 项目环…
阅读更多...
指针浅谈(三）

指针浅谈(三）

在指针浅谈(二)http://t.csdnimg.cn/SKAkD中我们讲到了const修饰指针、指针运算、野指针、assert断言和传址调用的内容&#xff0c;今天我们继续学习有关数组名、指针访问数组、一维数组传参的本质相关的内容&#xff0c;内容比较深入&#xff0c;如果觉得哪里讲解的不行&#…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023