C++实现二叉树基础操作:插入、查找与删除
126 浏览量
更新于2024-08-03
收藏 2KB TXT 举报
本资源是一份关于C语言实现二叉树基本操作的代码,主要包括插入、查找和删除节点的功能。首先,我们来看一下关键的部分:
1. **二叉树定义**:
`TreeNode` 结构体定义了一个包含整数值`val`的二叉树节点,以及指向左右子节点的指针`left`和`right`。构造函数`TreeNode(int x)`用于初始化一个值为`x`的新节点,其中`nullptr`表示默认没有子节点。
2. **插入节点(Insertion)**:
`insertNode(TreeNode* root, int val)`函数实现了向二叉搜索树中插入一个新节点的过程。如果根节点为空,就创建一个新的节点并返回;否则,根据新值与当前根节点值的大小关系,递归地将新值插入到左子树或右子树中。
3. **查找节点(Search)**:
`findNode(TreeNode* root, int val)`函数用于在已有的二叉树中查找指定值的节点。它通过比较目标值与当前节点值,如果相等或当前节点为空,则返回该节点;否则,继续在相应子树中递归查找。
4. **删除节点(Deletion)**:
`deleteNode(TreeNode* root, int val)`是删除具有指定值的节点的函数。首先检查根节点是否为空,然后依据删除节点的值与根节点值的关系,进行三种情况的处理:
- 如果要删除的值小于根节点,递归删除左子树。
- 如果要删除的值大于根节点,递归删除右子树。
- 如果找到要删除的节点,根据其是否有子节点来区分:
- 如果只有一个子节点,将其替换为另一个子节点,并删除原节点。
- 如果有两个子节点,找到右子树中的最小值节点(即右子树的最大节点),替换当前节点,然后删除找到的最小值节点。
这些代码展示了如何用C语言实现二叉树的常见操作,包括建立、搜索和调整数据结构以保持二叉搜索树的性质。它们对于理解二叉树的数据结构以及在实际编程中应用非常重要。理解这些操作有助于开发其他复杂的算法和数据结构,如排序、查找、遍历等。同时,这也有助于在面试或项目中展示对基础数据结构的扎实掌握。
2021-07-07 上传
2021-11-25 上传
2008-12-24 上传
2020-02-09 上传
2022-09-24 上传
2010-06-18 上传
2011-12-29 上传
2022-09-22 上传
2013-07-23 上传
cqtianxingkeji
- 粉丝: 2936
- 资源: 1596
最新资源
- ES管理利器:ES Head工具详解
- Layui前端UI框架压缩包:轻量级的Web界面构建利器
- WPF 字体布局问题解决方法与应用案例
- 响应式网页布局教程:CSS实现全平台适配
- Windows平台Elasticsearch 8.10.2版发布
- ICEY开源小程序:定时显示极限值提醒
- MATLAB条形图绘制指南:从入门到进阶技巧全解析
- WPF实现任务管理器进程分组逻辑教程解析
- C#编程实现显卡硬件信息的获取方法
- 前端世界核心-HTML+CSS+JS团队服务网页模板开发
- 精选SQL面试题大汇总
- Nacos Server 1.2.1在Linux系统的安装包介绍
- 易语言MySQL支持库3.0#0版全新升级与使用指南
- 快乐足球响应式网页模板:前端开发全技能秘籍
- OpenEuler4.19内核发布:国产操作系统的里程碑
- Boyue Zheng的LeetCode Python解答集