【数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
目录😋
任务描述
相关知识
测试说明
我的通关代码:
测试结果:
任务描述
本关任务:实现二叉排序树的基本算法。
相关知识
为了完成本关任务,你需要掌握:二叉树的创建、查找和删除算法。具体如下:
(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;
}
测试结果:


相关文章:
【数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
目录😋 任务描述 相关知识 测试说明 我的通关代码: 测试结果: 任务描述 本关任务:实现二叉排序树的基本算法。 相关知识 为了完成本关任务,你需要掌握:二叉树的创建、查找和删除算法。具体如下: (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]: # 如果要求非严格递增,将此行 …...
LeetCode - #158 用 Read4 读取 N 个字符 II
文章目录 摘要描述题目描述方法定义 题解答案题解代码题解代码分析示例测试及结果示例测试代码示例运行结果 时间复杂度空间复杂度总结关于我们 摘要 本文将详细解读一道与文件读取相关的编程问题:如何使用 read4 实现按需读取 n 个字符的 read 方法。我们不仅会提…...
C++(进阶) 第2章 多态
C(进阶) 第2章 多态 文章目录 前言一、多态的概念二、多态的定义及实现1.虚函数2.虚函数的重写3.多态的条件4.多态的细节 三、析构函数的重写四、重载/重写/隐藏的对比五、抽象类抽象类 六、相关题目题目1题目2 七、const修饰八、多态原理九、虚函数放在地方总结 前…...
mac删除程序坞(Dock)中“无法打开的程序“
参考: Mac删除软件之后图标还在怎么办?https://blog.csdn.net/weixin_46500474/article/details/124284161Mac程序坞中软件删除出现残留“?”图标无法删除解决方法: 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 已加载插件:fastestmirror, langpacks /var/run/yum.pid 已被锁定,PID 为 2611 的另一个程序正在运行。 Another app is currently holding the yum lock; waiting for it to exit... [root…...
OpenMMlab导出MaskFormer/Mask2Former模型并用onnxruntime和tensorrt推理
onnxruntime推理 使用mmdeploy导出onnx模型: 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 和达梦(DM)依赖2、在 application-druid.yml 中配置达梦(DM)数据源3、在 DruidConfig 类中配置多数据源信息4、在 Service 层或方法级别切换数据源4.1 在 Service 类上切换到从库数据源4.2 在方法级别切换…...
一些前端组件介绍
wangEditor : 一款开源 Web 富文本编辑器,可用于 jQuery Vue React等 https://www.wangeditor.com/ Handsontable:一款前端可编辑电子表格https://blog.csdn.net/carcarrot/article/details/108492356mitt:Mitt 是一个在 Vue.js 应…...
python学opencv|读取图像(九)用numpy创建黑白相间灰度图
【1】引言 前述学习过程中,掌握了用numpy创建矩阵数据,把所有像素点的BGR取值设置为0,然后创建纯黑灰度图的方法,具体链接为: python学opencv|读取图像(八)用numpy创建纯黑灰度图-CSDN博客 在…...
AtCoder Beginner Contest 383
C - Humidifier 3 Description 一个 h w h \times w hw 的网格,每个格子可能是墙、空地或者城堡。 一个格子是好的,当且仅当从至少一个城堡出发,走不超过 d d d 步能到达。(只能上下左右走,不能穿墙)&…...
20. 内置模块
一、random模块 random 模块用来创建随机数的模块。 random.random() # 随机生成一个大于0且小于1之间的小数 random.randint(a, b) # 随机生成一个大于等于a小于等于b的随机整数 random.uniform(a, b) …...
《知识拓展 · 统一建模语言UML》
📢 大家好,我是 【战神刘玉栋】,有10多年的研发经验,致力于前后端技术栈的知识沉淀和传播。 💗 🌻 CSDN入驻不久,希望大家多多支持,后续会继续提升文章质量,绝不滥竽充数…...
计算机网络-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与表格识别助力医疗化验单快速处理
在医疗行业,化验单作为重要的诊断依据和数据来源,涉及大量的文字和表格信息,传统的手工输入和数据处理方式不仅繁琐,而且容易出错,给医院的运营效率和数据准确性带来较大挑战。随着人工智能技术的快速发展,…...
1.2.3计算机软件
一个完整的计算机系统由硬件和软件组成,用户使用软件,而软件运行在硬件之上,软件进一步的划分为两类:应用软件和系统软件。普通用户通常只会跟应用软件打交道。应用软件是为了解决用户的某种特定的需求而研发出来的。除了每个人都…...
二、uni-forms
避坑指南:uni-forms表单在uni-app中的实践经验-CSDN博客...
Android13开机向导
文章目录 前言需求-场景第三方资料说明需求思路按照平台 思路 从配置上去 feature换个思路,去feature。SimMissingActivity 判断跳过逻辑SetupWizardUtils 判断SIM 、 hasSystemFeature FEATURE_TELEPHONYPackageManager.FEATURE_TELEPHONYApplicationPackageManage…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
