数据结构:二叉树的实现
目录
二叉树的遍历方式
前序遍历:
中序遍历:
后序遍历:
二叉树的基本结构和功能
基本结构:
基本功能:
二叉树功能的实现思路
二叉树功能的实现
1、构建一个二叉树
2、二叉树的销毁
3、计算二叉树里的节点个数
4、得到二叉树的子叶节点个数
5、得到二叉树第K层节点个数
6、查找二叉树值为X的节点
7、二叉树的前/中/后序遍历
前序遍历
中序遍历
后序遍历
8、层序遍历
9、判断二叉树是否为完全二叉树
二叉树的遍历方式
二叉树有三种遍历方式,不同的遍历方式有不同的效果和作用。(实现二叉树的代码)
前序遍历:
根->左子树->右子树。
(如上图所示)用前序遍历这个二叉树的结果是: 1 2 4 8 5 3 6 9 7
如果加上空的子树,结果是:1 2 4 N 8 N N 5 N N 3 6 9 N N N 7 N N(为了方便理解,同一种颜色的是根的子树)
中序遍历:
左子树->根->右子树。
(如上图所示)用前序遍历这个二叉树的结果是: 4 8 2 5 1 9 6 3 7
如果加上空的子树,结果是:N 4 N 8 N 2 N 5 N 1 N 9 N 6 N 3 N 7 N(为了方便理解,同一种颜色的是根的子树)
后序遍历:
左子树->右子树->根。
(如上图所示)用前序遍历这个二叉树的结果是: 8 4 5 2 9 6 7 3 1
如果加上空的子树,结果是:N N N 8 4 N N 5 2 N N 9 6 N N 7 3 1(为了方便理解,同一种颜色的是根的子树)
二叉树的基本结构和功能
基本结构:
我们知道二叉树里有一个值和指向两个子树的指针构成,所以我们可以用下面的结构体来作为一个节点。
typedef char BTDataType;//为了便于以后因不同需求而更改。
//节点
typedef struct BinaryTreeNode
{BTDataType _data;//存放值struct BinaryTreeNode* _left;//一个指向左子树的指针struct BinaryTreeNode* _right;//一个指向右子树的指针
}BTNode;
基本功能:
- 通过一个关于二叉树遍历的字符串来构建出一个二叉树
- 二叉树的销毁
- 得到二叉树的节点个数
- 得到二叉树的子叶节点个数
- 得到二叉树第K层节点个数
- 查找二叉树值为X的节点
- 二叉树的前序遍历
- 二叉树的中序遍历
- 二叉树的后序遍历
- 层序遍历
- 判断二叉树是否为完全二叉树
二叉树功能的实现思路
(二叉树的大部分功能的实现都需要用到递归,所以我们要对递归一定熟练度)当我们要构建一个二叉树的时候,可以用递归的方式来连接一个一个的节点。其他的功能最主要的也是用递归
实现的。
二叉树功能的实现
1、构建一个二叉树
当我们要构建一个二叉树,我们首先要确定它的构建方式——前序、中序还是后序。(这里以前序遍历为例)
前序遍历的方式是根->左子树->右子树。
若我们要通过前序遍历的数组" A B D # # E # H # # C F # # G # # "构建二叉树,我们首先可以先画出构建好的二叉树的图形(如下图所示),这回让你对你要创建的二叉树有更深的理解。
利用递归的性质,我们只要遇到 ' # '就返回,反之,就创建节点,然后使其链接左子树和右子树。
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{//当遇到' # '就返回if (a[*pi] == '#'){(*pi)++;return NULL;}//创建一个节点BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail");return NULL;}root->_data = a[*pi];(*pi)++;root->_left = BinaryTreeCreate(a, pi);//链接左子树root->_right = BinaryTreeCreate(a, pi);//链接右子树//最后返回根return root;
}
如果我们想要用其他的遍历方式来构建二叉树可以调整一下链接左子树的时机。(记得字符串里的内容要是对应的遍历方式)
2、二叉树的销毁
要销毁一个二叉树,我们首先要确定销毁方式,因二叉树的结构只能用后序遍历(左子树->右子树->根)的方式来销毁二叉树。
假如我们用前序(左子树->根->右子)或中序(左子树->根->右子树)的方式销毁二叉树,我们都会先销毁根,导致我们找不到后续的子树,所以我们只能用后序的方式来销毁二叉树。
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}//先遍历到子叶再开始销毁BinaryTreeDestory(&(*root)->_left);BinaryTreeDestory(&(*root)->_right);free(*root);*root = NULL;
}
3、计算二叉树里的节点个数
计算节点个数,我们只需要遇到空指针就返回,反之就加左子树和右子树之和再加1(本身)即可。
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
4、得到二叉树的子叶节点个数
遇到空就返回0,如果本身非空且有左子树则加1,如果本身非空且有右子树则加1,这样我们就可以得到二叉树的子叶节点个数了。
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root && root->_left == NULL)return 1;if (root && root->_right == NULL)return 1;return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}
5、得到二叉树第K层节点个数
我们先设根节点为第一层,则第二层就为k-1层,然后推导,当k == 1的时候就是我们需要计算节点个数的层数。若该二叉树没有第k层呢?我们只需当k == 0时就返回0即可。
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;//当k == 1时就返回1if (k == 1)return 1;return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
6、查找二叉树值为X的节点
在二叉树里查找一个值的时候,我们首先要确定查找方式,(这里以前序为例),我们用前序查找,如果左子树有这个值就返回该节点,没有就返回NULL,然后再查找右子树,若也没有就返回NULL。
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->_data == x)return root;BTNode* left = BinaryTreeFind(root->_left, x);return left != NULL ? left : BinaryTreeFind(root->_right, x);
}
如果不在左子树,那就只有两种可能,一个是在右子树,一个是没有这个值。这里的left都为空的话,那只能去右子树里去找了。
7、二叉树的前/中/后序遍历
这三种遍历方式在二叉树的实现都差不多,只是要区分先后顺序。
前序遍历
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){ printf("# ");return;}printf("%c ", root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);
}
中序遍历
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}BinaryTreePrevOrder(root->_left);printf("%c ", root->_data);BinaryTreePrevOrder(root->_right);
}
后序遍历
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("# ");return;}BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);printf("%c ", root->_data);
}
8、层序遍历
层序遍历就与上面的遍历有所不同,这里我们要利用队列来存储节点的指针来达到层序遍历。
这里的层序遍历的结构是:A B C D E F G H
首先,我们要清楚队列的性质,队列是由链表构成,先进先出的方式来进出队列。开始先入一个根节点,每当出一个二叉树的节点就得要入它的左子树节点和右子树节点。遇到不是空节点就入队列。这样我们就可以实现二叉树的层序遍历。(这里避免过于臃肿就不写队列的过程了,如果想了解一下队列可以看看这篇文章详解栈和队列的实现以及它们的相互实现)
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if(root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);printf("%c", front->_data);if(front->_left)QueuePush(&q, front->_left);if (front->_right)QueuePush(&q, front->_right);QueuePop(&q);}printf("\n");
}
9、判断二叉树是否为完全二叉树
判断二叉树是否为完全二叉树的实现,跟上面基本同理,当与到空的时候就直接break去判断后面还有没有其他的数,无,则是完全二叉树,反之,不是完全二叉树。
原理:(将空指针视为 N )如果一个二叉树是完全二叉树,将像上面入队列的时候,队列中存储的数据到N的时候后面就只有N了。但如果还有其他的数,那就不可能是完全二叉树。
// 判断二叉树是否是完全二叉树
bool BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if(root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if( front == NULL)break;if(front->_left)QueuePush(&q, front->_left);if (front->_right)QueuePush(&q, front->_right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if( front){QueueDistory(&q);return false;}} return true;
}
(完)
相关文章:

数据结构:二叉树的实现
目录 二叉树的遍历方式 前序遍历: 中序遍历: 后序遍历: 二叉树的基本结构和功能 基本结构: 基本功能: 二叉树功能的实现思路 二叉树功能的实现 1、构建一个二叉树 2、二叉树的销毁 3、计算二叉树里的节点个数 4、得…...

Helm离线部署Rancher2.7.10
环境依赖: K8s集群、helm 工具 Rancher组件架构 Rancher Server 包括用于管理整个 Rancher 部署的所有软件组件。 下图展示了 Rancher 2.x 的上层架构。下图中,Rancher Server 管理两个下游 Kubernetes 集群 准备Rancher镜像推送到私有仓库 cat >…...
Linux目录的作用和常用指令
目录结构及其详细作用 / (根目录) Linux文件系统的起点,所有文件和目录都在其下。 /bin 存放系统启动和运行时所需的基本命令,如 ls, cp, mv, rm,这些命令在单用户模式下或系统崩溃时仍然可用。 /boot 包含启动引导加载器的文件和Linux内核…...

Nvidia/算能 +FPGA+AI大算力边缘计算盒子:隧道和矿井绘图设备
RockMass 正在努力打入采矿业和隧道工程利基市场。 这家位于多伦多的初创公司正在利用 NVIDIA AI 开发一款绘图平台,帮助工程师评估矿井和施工中的隧道稳定性。 目前,作为安全预防措施,地质学家和工程师会站在离岩石五米远的地方࿰…...
MySQL物理备份
目录 备份策略 全量备份 (Full Backup) 增量备份 (Incremental Backup) 差异备份 (Differential Backup) 使用 Percona XtraBackup 全量备份 步骤 1:全量备份 步骤 2:备份后处理(应用日志) 步骤 3:恢复备份 验…...

AWT常用组件
AWT中常用组件 前言一、基本组件组件名标签(Label类)Label类的构造方法注意要点 按钮(Button)Button的构造方法注意要点 文本框(TextField)TextField类的构造方法注意要点 文本域(TextArea)TextArea 的构造方法参数scrollbars的静态常量值 复选框&#x…...

CorelDRAW2024破解激活码序列号一步到位
亲们,今天给大家种草一个神奇的软件——CorelDRAW破解2024最新版!🎨这是一款专业级的矢量图形设计软件,无论你是平面设计师、插画师还是设计师,都能在这个软件中找到你需要的工具和功能。✨ 让我来给大家介绍一下这款软…...
Webpack前端打包工具详解
目录 Webpack前端打包工具详解一、Webpack 的作用二、Webpack 的安装和基本使用1. 安装 Webpack2. 创建 Webpack 配置文件3. 运行 Webpack 三、Webpack 核心概念1. 入口(Entry)2. 输出(Output)3. 加载器(Loaders&#…...

计网总结☞网络层
.................................................. 思维导图 ........................................................... 【Wan口和Lan口】 WAN口(Wide Area Network port): 1)用于连接外部网络,如互联…...

【全开源】云调查考试问卷系统(FastAdmin+ThinkPHP+Uniapp)
便捷、高效的在线调研与考试新选择 云调查考试问卷是一款基于FastAdminThinkPHPUniapp开发的问卷调查考试软件,可以自由让每一个用户自由发起调查问卷、考试问卷。发布的问卷允许控制问卷的搜集、回答等各个环节的设置,同时支持系统模板问卷ÿ…...

网络安全难学吗?2024该怎么系统学习网络安全?
学习网络安全需要循序渐进,由浅入深。很多人对网络安全进行了解以后,就打算开始学习网络安全,但是又不知道怎么去系统的学习。 网络安全本身的知识不难,但需要学习的内容有很多,其中包括Linux、数据库、渗透测试、等保…...
2 程序的灵魂—算法-2.4 怎样表示一个算法-2.4.6 用计算机语言表示算法
我们的任务是用计算机解题,就是用计算机实现算法; 用计算机语言表示算法必须严格遵循所用语言的语法规则。 【例 2.20】求 12345 用 C 语言表示。 main() {int i,t; t1; i2; while(i<5) {tt*i; ii1; } printf(“%d”,t); } 【例 2.21】求级数的…...

重生之我要精通JAVA--第八周笔记
文章目录 多线程线程的状态线程池自定义线程池最大并行数多线程小练习 网络编程BS架构优缺点CS架构优缺点三要素IP特殊IP常用的CMD命令 InetAddress类端口号协议UDP协议(重点)UDP三种通信方式 TCP协议(重点)三次握手四次挥手 反射…...

51单片机独立按键控制LED灯,按键按一次亮,再按一次灭
1、功能描述 独立按键控制LED灯,按键按一次亮,再按一次灭 2、实验原理 轻触按键:相当于是一种电子开关,按下时开关接通,松开时开关断开,实现原理是通过轻触按键内部的金属弹片受力弹动米实现接通和断开;…...

【上海大学计算机组成原理实验报告】七、程序转移机制
一、实验目的 学习实现程序转移的硬件机制。 掌握堆栈寄存器的使用。 二、实验原理 根据实验指导书的相关内容,实验箱系统的程序转移硬件机制在于,当LDPC有效时,如果此时DUBS上的值就是转移的目标地址,则此目标地址被打入PC&am…...

LLVM Cpu0 新后端7 第一部分 DAG调试 dot文件 Machine Pass
想好好熟悉一下llvm开发一个新后端都要干什么,于是参考了老师的系列文章: LLVM 后端实践笔记 代码在这里(还没来得及准备,先用网盘暂存一下): 链接: https://pan.baidu.com/s/1yLAtXs9XwtyEzYSlDCSlqw?…...
修复www服务trace漏洞
验证方式:curl -v -X TRACE ip:port,或使用其他接口调试工具如Postman 响应:状态行405 Method Not Allowed且响应体无内容 方案一:使用过滤器 若webserver是tomcat, 添加过滤器的方式有很多 Component public class TraceHttpMe…...

算法:101. 对称二叉树
对称二叉树 给你一个二叉树的根节点 root , 检查它是否轴对称。 示例 1: 输入:root [1,2,2,3,4,4,3] 输出:true示例 2: 输入:root [1,2,2,null,3,null,3] 输出:false提示: 树中节…...
wordpress 使用api发布文章
1.安装插件 在/wp-content/plugins/目录执行以下命令 $ sudo git clone https://github.com/WP-API/Basic-Auth.git 2.Python脚本 import requestsurl http://www.ziyuanwang.online/wp-json/wp/v2/postsuser adminpassword xxxxxheaders {Content-Type: application/j…...

《Brave New Words 》2.2 阅读理解的未来,让文字生动起来!
Part II: Giving Voice to the Social Sciences 第二部分:为社会科学发声 The Future of Reading Comprehension, Where Literature Comes Alive! 阅读理解的未来,让文字生动起来! Saanvi, a ninth grader in India who attends Khan World S…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...