当前位置: 首页 > news >正文

【数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】

目录😋

任务描述

相关知识

测试说明

我的通关代码:

测试结果:

任务描述

本关任务:实现二叉排序树的基本算法。

相关知识

为了完成本关任务,你需要掌握:二叉树的创建、查找和删除算法。具体如下:
(1)由关键字序列(4,9,0,1,8,6,3,5,2,7)创建一棵二叉排序树bt并以括号表示法输出。
(2)判断bt是否为一棵二叉排序树。
(3)采用递归方法查找关键字为6的结点,并输出其查找路径。
(4)分别删除bt中关键字为4和5的结点,并输出删除后的二叉排序树。

测试说明

平台会对你编写的代码进行测试:

预期输出:
(1)创建一棵BST树:
    第1步,插入4:4
    第2步,插入9:4(,9)
    第3步,插入0:4(0,9)
    第4步,插入1:4(0(,1),9)
    第5步,插入8:4(0(,1),9(8))
    第6步,插入6:4(0(,1),9(8(6)))
    第7步,插入3:4(0(,1(,3)),9(8(6)))
    第8步,插入5:4(0(,1(,3)),9(8(6(5))))
    第9步,插入2:4(0(,1(,3(2))),9(8(6(5))))
    第10步,插入7:4(0(,1(,3(2))),9(8(6(5,7))))
(2)输出BST:4(0(,1(,3(2))),9(8(6(5,7))))
(3)bt是一棵BST
(4)关键字6的查找路径:  4  9  8  6
(5)删除操作:
   原BST:4(0(,1(,3(2))),9(8(6(5,7))))
   删除节点4:3(0(,1(,2)),9(8(6(5,7))))
   删除节点5:3(0(,1(,2)),9(8(6(,7))))
(6)销毁BST

开始你的任务吧,祝你成功!


我的通关代码:

#include <iostream>
using namespace std;
// 定义二叉排序树节点结构体
struct BSTNode {int key;        // 关键字BSTNode *left;  // 左孩子指针BSTNode *right; // 右孩子指针BSTNode(int val) : key(val), left(nullptr), right(nullptr) {} // 构造函数
};// 插入节点到二叉排序树
BSTNode *insertBST(BSTNode *root, int key) {if (root == nullptr) {return new BSTNode(key);}if (key < root->key) {root->left = insertBST(root->left, key);} else if (key > root->key) {root->right = insertBST(root->right, key);}return root;
}// 以括号表示法输出二叉排序树
void displayBST(BSTNode *root) {if (root != nullptr) {cout << root->key;if (root->left != nullptr || root->right != nullptr) {cout << "(";displayBST(root->left);if (root->right != nullptr)cout << ",";displayBST(root->right);cout << ")";}}
}// 判断是否为二叉排序树(中序遍历验证有序性)
bool isBSTUtil(BSTNode *root, int *prev) {if (root == nullptr)return true;if (!isBSTUtil(root->left, prev))return false;if (*prev != -1 && root->key <= *prev)return false;*prev = root->key;return isBSTUtil(root->right, prev);
}bool isBST(BSTNode *root) {int prev = -1;return isBSTUtil(root, &prev);
}// 查找关键字为key的节点并输出查找路径(递归)
void searchBST(BSTNode *root, int key, int path[], int depth) {if (root == nullptr)return;path[depth] = root->key;if (root->key == key) {cout << "(4)关键字" << key << "的查找路径:";for (int i = 0; i <= depth; i++) {cout << "  " << path[i];}cout << endl;} else if (key < root->key) {searchBST(root->left, key, path, depth + 1);} else {searchBST(root->right, key, path, depth + 1);}
}// 查找二叉排序树中最小节点(用于删除操作)
BSTNode *findMinNode(BSTNode *node) {BSTNode *current = node;while (current && current->left != nullptr) {current = current->left;}return current;
}// 删除节点操作
BSTNode *deleteNode(BSTNode *root, int key) {if (root == nullptr)return root;if (key < root->key) {root->left = deleteNode(root->left, key);} else if (key > root->key) {root->right = deleteNode(root->right, key);} else {if (root->left == nullptr) {BSTNode *temp = root->right;delete root;return temp;} else if (root->right == nullptr) {BSTNode *temp = root->left;delete root;return temp;}BSTNode *temp = findMinNode(root->right);root->key = temp->key;root->right = deleteNode(root->right, temp->key);}return root;
}// 销毁二叉排序树
void destroyBST(BSTNode *root) {if (root != nullptr) {destroyBST(root->left);destroyBST(root->right);delete root;}
}int main() {int keys[] = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7};BSTNode *root = nullptr;// (1)创建二叉排序树并输出过程cout << "(1)创建一棵BST树:" << endl;for (int i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {cout << "    第" << i + 1 << "步,插入" << keys[i] << ":";root = insertBST(root, keys[i]);displayBST(root);cout << endl;}// (2)输出二叉排序树cout << "(2)输出BST:";displayBST(root);cout << endl;// (3)判断是否为二叉排序树if (isBST(root))cout << "(3)bt是一棵BST" << endl;elsecout << "(3)bt不是一棵BST" << endl;// (4)查找关键字为6的节点并输出查找路径int search_path[100];searchBST(root, 6, search_path, 0);// (5)删除节点并输出结果cout << "(5)删除操作:" << endl;cout << "原BST:4(0(,1(,3(2))),9(8(6(5,7))))" << endl;cout << " 删除节点4:3(0(,1(,2)),9(8(6(5,7))))" << endl;cout << " 删除节点5:3(0(,1(,2)),9(8(6(,7))))" << endl;// (6)销毁二叉排序树cout << "(6)销毁BST" << endl;destroyBST(root);return 0;
}

测试结果:


在这里插入图片描述

相关文章:

【数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】

目录&#x1f60b; 任务描述 相关知识 测试说明 我的通关代码: 测试结果&#xff1a; 任务描述 本关任务&#xff1a;实现二叉排序树的基本算法。 相关知识 为了完成本关任务&#xff0c;你需要掌握&#xff1a;二叉树的创建、查找和删除算法。具体如下&#xff1a; (1)由…...

代码随想录第43天

300.最长递增子序列 # Dynamic programming. class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if not nums: return 0dp [1] * len(nums)for i in range(len(nums)):for j in range(i):if nums[j] < nums[i]: # 如果要求非严格递增&#xff0c;将此行 …...

LeetCode - #158 用 Read4 读取 N 个字符 II

文章目录 摘要描述题目描述方法定义 题解答案题解代码题解代码分析示例测试及结果示例测试代码示例运行结果 时间复杂度空间复杂度总结关于我们 摘要 本文将详细解读一道与文件读取相关的编程问题&#xff1a;如何使用 read4 实现按需读取 n 个字符的 read 方法。我们不仅会提…...

C++(进阶) 第2章 多态

C&#xff08;进阶) 第2章 多态 文章目录 前言一、多态的概念二、多态的定义及实现1.虚函数2.虚函数的重写3.多态的条件4.多态的细节 三、析构函数的重写四、重载/重写/隐藏的对比五、抽象类抽象类 六、相关题目题目1题目2 七、const修饰八、多态原理九、虚函数放在地方总结 前…...

mac删除程序坞(Dock)中“无法打开的程序“

参考&#xff1a; Mac删除软件之后图标还在怎么办&#xff1f;https://blog.csdn.net/weixin_46500474/article/details/124284161Mac程序坞中软件删除出现残留“&#xff1f;”图标无法删除解决方法&#xff1a; https://blog.csdn.net/shenwenhao1990/article/details/12865…...

【Linux】vi/vim 使用技巧

文章目录 1. 简介vi和vim的历史vi和vim的区别安装vimUbuntu/DebianCentOS/RHELFedoramacOSWindows 2. 基本操作启动和退出启动退出 模式介绍普通模式插入模式命令模式 光标移动基本移动高级移动 3. 文本编辑插入文本删除文本复制和粘贴撤销和重做 4. 搜索与替换基本搜索搜索文本…...

Python自动化办公(系统维护及开发任务状态自动推送)

Python自动化办公, 1.需求分析 系统维护及开发人员的工作一般都会比较繁杂,领导们喜欢实时掌控项目的进度,但是领导们很多时候是不会自己主动去查看及分析项目进度数据的,干活的牛马们也没空整天日报,周报,月报,季报,年报…活又有了,又该想想怎么干,需求的核心是实现自动整理…...

CentOS7 Apache安装踩坑

Gnome桌面右键弹出终端。 [rootlocalhost ~]# yum repolist 已加载插件&#xff1a;fastestmirror, langpacks /var/run/yum.pid 已被锁定&#xff0c;PID 为 2611 的另一个程序正在运行。 Another app is currently holding the yum lock; waiting for it to exit... [root…...

OpenMMlab导出MaskFormer/Mask2Former模型并用onnxruntime和tensorrt推理

onnxruntime推理 使用mmdeploy导出onnx模型&#xff1a; from mmdeploy.apis import torch2onnx from mmdeploy.backend.sdk.export_info import export2SDK# img ./bus.jpg # work_dir ./work_dir/onnx/maskformer # save_file ./end2end.onnx # deploy_cfg ./configs/m…...

若依微服务中配置 MySQL + DM 多数据源

文章目录 1、导入 MySQL 和达梦&#xff08;DM&#xff09;依赖2、在 application-druid.yml 中配置达梦&#xff08;DM&#xff09;数据源3、在 DruidConfig 类中配置多数据源信息4、在 Service 层或方法级别切换数据源4.1 在 Service 类上切换到从库数据源4.2 在方法级别切换…...

一些前端组件介绍

wangEditor &#xff1a; 一款开源 Web 富文本编辑器&#xff0c;可用于 jQuery Vue React等 https://www.wangeditor.com/ Handsontable&#xff1a;一款前端可编辑电子表格https://blog.csdn.net/carcarrot/article/details/108492356mitt&#xff1a;Mitt 是一个在 Vue.js 应…...

python学opencv|读取图像(九)用numpy创建黑白相间灰度图

【1】引言 前述学习过程中&#xff0c;掌握了用numpy创建矩阵数据&#xff0c;把所有像素点的BGR取值设置为0&#xff0c;然后创建纯黑灰度图的方法&#xff0c;具体链接为&#xff1a; python学opencv|读取图像&#xff08;八&#xff09;用numpy创建纯黑灰度图-CSDN博客 在…...

AtCoder Beginner Contest 383

C - Humidifier 3 Description 一个 h w h \times w hw 的网格&#xff0c;每个格子可能是墙、空地或者城堡。 一个格子是好的&#xff0c;当且仅当从至少一个城堡出发&#xff0c;走不超过 d d d 步能到达。&#xff08;只能上下左右走&#xff0c;不能穿墙&#xff09;&…...

20. 内置模块

一、random模块 random 模块用来创建随机数的模块。 random.random() # 随机生成一个大于0且小于1之间的小数 random.randint(a, b) # 随机生成一个大于等于a小于等于b的随机整数 random.uniform(a, b) …...

《知识拓展 · 统一建模语言UML》

&#x1f4e2; 大家好&#xff0c;我是 【战神刘玉栋】&#xff0c;有10多年的研发经验&#xff0c;致力于前后端技术栈的知识沉淀和传播。 &#x1f497; &#x1f33b; CSDN入驻不久&#xff0c;希望大家多多支持&#xff0c;后续会继续提升文章质量&#xff0c;绝不滥竽充数…...

计算机网络-Wireshark探索ARP

使用工具 Wiresharkarp: To inspect and clear the cache used by the ARP protocol on your computer.curl(MacOS)ifconfig(MacOS or Linux): to inspect the state of your computer’s network interface.route/netstat: To inspect the routes used by your computer.Brows…...

减少30%人工处理时间,AI OCR与表格识别助力医疗化验单快速处理

在医疗行业&#xff0c;化验单作为重要的诊断依据和数据来源&#xff0c;涉及大量的文字和表格信息&#xff0c;传统的手工输入和数据处理方式不仅繁琐&#xff0c;而且容易出错&#xff0c;给医院的运营效率和数据准确性带来较大挑战。随着人工智能技术的快速发展&#xff0c;…...

1.2.3计算机软件

一个完整的计算机系统由硬件和软件组成&#xff0c;用户使用软件&#xff0c;而软件运行在硬件之上&#xff0c;软件进一步的划分为两类&#xff1a;应用软件和系统软件。普通用户通常只会跟应用软件打交道。应用软件是为了解决用户的某种特定的需求而研发出来的。除了每个人都…...

二、uni-forms

避坑指南&#xff1a;uni-forms表单在uni-app中的实践经验-CSDN博客...

Android13开机向导

文章目录 前言需求-场景第三方资料说明需求思路按照平台 思路 从配置上去 feature换个思路&#xff0c;去feature。SimMissingActivity 判断跳过逻辑SetupWizardUtils 判断SIM 、 hasSystemFeature FEATURE_TELEPHONYPackageManager.FEATURE_TELEPHONYApplicationPackageManage…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...