二叉树的基础---四种遍历方式的 Java 实现
0. 前言
大家好,我是多选参数的程序锅,一个正在“研究”操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇将带来的是二叉树的相关知识,知识提纲如图所示。
1. 基本介绍
树结构多种多样,但是最常用的还是二叉树。二叉树中每个节点最多有两个子节点,这两个节点分别是左子节点和右子节点。注意:不要求都有两个子节点,可以只有左子节点,也可以只有右子节点。
2. 二叉树的存储
2.1. 链式存储法
每个节点至少有三个字段,其中一个存储数据,另外两个是指向左右子节点的指针。这种存储方式比较常用,大部分二叉树代码都是通过这种结构来实现的。
2.2. 数组存储法
我们把根节点存储在下标 i=1 的位置,它的左子节点存储在下标为 2 * i 的位置,右子节点存储在下标为 2*i+1 的位置。以此类推,B 节点、C 节点的左右子节点都按照这种规律进行存储,最终如下图所示。
综上,如果节点 X 存储在数组中下标为 i 的位置,那么下标为 2*i 的位置存储的就是它的左子节点,下标为 2*i+1 的位置存储的就是它的右子节点。反过来,i/2 的位置存储的就是它的父节点。一般情况下,为了方便计算,根节点会被存储在下标为 1 的位置。
通过上述可以看到,针对一般树来说,使用数组的方式存储树会浪费比较多的存储空间。但是针对下文会提到的满二叉树或者完全二叉树来说,数组存储的方式是最节省内存的一种方式。因为数组存储时,不需要再存储额外的左右子节点的指针。
3. 二叉树的遍历
二叉树的遍历就是将二叉树中的所有节点遍历打印出来。经典的方法有三种,前序遍历、中序遍历和后序遍历,还可以按层遍历(个人理解的按层遍历其实就是按照图的广度优先遍历方法来进行遍历)。
前、中、后是根据节点被打印的先后来进行区分的:前序就是先打印节点本身,之后再打印它的左子树,最后打印它的右子树;中序就是先打印节点的左子树,再打印节点本身,最后打印右子树,即把节点放中间的位置输出;后序就是先打印节点的左子树,再打印节点的右子树,最后打印节点本身。如下图所示
按层遍历类似于图的广度优先遍历,先打印第一层的节点,之后再依次打印第二层的节点,以此类推。
3.1. 代码实现
实际上,二叉树的前、中、后序遍历是一个递归的过程。比如,前序遍历,其实就是先打印根节点,然后递归遍历左子树,最后递归遍历右子树。递归遍历左右子树其实就跟遍历根节点的方法一样。下面先写出这三者遍历的递推公式:
前序遍历的递推公式:
preOrder(r) = print r ---> preOrder(r->left) ---> preOrder(r->right)
中序遍历的递推公式:
inOrder(r) = inOrder(r--->left) ---> print r ---> inOrder(r->right)
后序遍历的递推公式:
postOrder(r) = postOrder(r->left) ---> postOrder(r->right) --->print r
之后将递推公式转化为代码如下所示:
/**
* 前序遍历
*/
public void preOrder(Node tree) {
if (tree == null) {
return;
}
System.out.print(tree.data + " ");
preOrder(tree.left);
preOrder(tree.right);
}
/**
* 中序遍历
*/
public void inOrder(Node tree) {
if (tree == null) {
return;
}
inOrder(tree.left);
System.out.print(tree.data + " ");
inOrder(tree.right);
}
/**
* 后序遍历
*/
public void postOrder(Node tree) {
if (tree == null) {
return;
}
postOrder(tree.left);
postOrder(tree.right);
System.out.print(tree.data + " ");
}
★递归代码的关键,在于写出递推公式。而递推公式的关键在于,A 问题可以被拆解成 B、C 两个问题。假设要解决 A 问题,那么假设 B、C 问题已经解决了。那么在 B、C 已经解决的提前下,看如何利用 B、C 来解决 A 。千万不要模拟计算机一层一层想下去,否则你就会发现你自己都不知道在哪了。
”
下面是按层遍历的代码,按层遍历需要用到队列的入队和出队等操作。先将根节点放入到队列中,然后循环从队列中取节点(出队),再将该节点的左右子节点入队。出队的顺序就是层次遍历的结果。
/**
* 层次遍历
*/
public void BFSOrder(Node tree) {
if (tree == null) {
return;
}
Queue<Node> queue = new LinkedList<>();
Node temp = null;
queue.offer(tree);
while (!queue.isEmpty()) {
temp = queue.poll();
System.out.print(temp.data + " ");
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
}
★完整的代码可查看 github 仓库 https://github.com/DawnGuoDev/algos ,这个仓库将主要包含常用数据结构及其基本操作的手写实现(Java),也会包含常用算法思想经典例题的实现(Java)。在程序锅找到工作之前,这个仓库将会保持更新状态,在此之间学到的关于数据结构和算法的知识或者实现也都会往里面 commit,所以赶紧来 star 哦。
”
3.2. 时间复杂度
遍历过程中的次数就是访问所有节点的所需的次数,而每个节点最多被访问两次,因此遍历的时间复杂度是跟节点的个数 n 成正比的,即遍历的时间复杂度是 O(n)。
4. 特殊的二叉树
4.1. 满二叉树
满二叉树是一种特殊的二叉树,而且还是完全二叉树的一种特殊情况。如上图编号 2 的那棵树所示,叶子节点全在底层,除了叶子节点之外,每个节点都有左右两个子节点。
4.2. 完全二叉树
完全二叉树也是一种特殊的二叉树。如上图编号 3 的那棵树所示,叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都达到最大。
完全二叉树的特征使得它可以使用数组就可以很好地存储数据。完全二叉树要求最后一层的叶子节点靠左排列也是因为如此。
4.2.1. 完全二叉树的存储
-
链式存储
就是上面提到的那种方式。
-
数组存储
完全二叉树使用数组存储时,如下图所示。我们发现使用数组来存储完全二叉树是一种很节省内存的方式。这也是完全二叉树被作为一种特殊树的原因,也是完全二叉树要求最后一层的子节点必须都靠左的原因。
在讲解堆或者堆排序的时候,堆其实也是一种完全二叉树,最常用的存储方式就是数组。
4.3. 其他特殊的二叉树
其他特殊的二叉树还有二叉查找树、平衡二叉查找树等。因为这两种特殊的树涵盖的知识比较多,所以会将其分开进行单独讲解。
5. 巨人的肩膀
-
极客时间专栏,王争老师的《数据结构与算法之美》
6. 附 Github
整个系列的代码可查看 github 仓库 https://github.com/DawnGuoDev/algos ,这个仓库将主要包含常用数据结构及其基本操作的手写实现(Java),也会包含常用算法思想经典例题的实现(Java)。在接下来一年内,这个仓库将会保持更新状态,在此之间学到的关于数据结构和算法的知识或者实现也都会往里面 commit,所以赶紧来 star 哦。
不甘于「本该如此」,「多选参数 」值得关注
本文分享自微信公众号 - 多选参数(zhouxintalk)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
5分钟!用Java实现目标检测 | PyTorch
云栖号资讯:【点击查看更多行业资讯】在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来! 编者按:作为一个Java开发者,你是否曾为在PyTorch上部署模型而苦恼?这篇来自AWS软件工程师的投稿,结合实例,详细介绍了DJL这个为Java开发者设计的深度学习库:5分钟,你就能在PyTorch上,用Java实现目标检测。 5分钟,用Java实现目标检测 PyTorch在深度学习领域中的应用日趋广泛,得益于它独到的设计。无论是数据的并行处理还是动态计算图,一切都为Python做出了很多简化。很多论文都选择使用PyTorch去实现也证明了它在训练方面的效率以及易用性。 在PyTorch领域,尽管部署一个模型有很多选择,可为Java开发人员准备的选项却屈指可数。 在过去,用户可以用PyTorch C++ 写JNI (Java Native Interface) 来实现这个过程。最近,PyTorch 1.4 也发布了试验性的Java 前端。 可是这两种解决方案都没有办法能让Java开发者很好的使用:用户需要从易于使用和易于维护中二选一。 针对于这个问题,亚马逊云服务 (AWS)开源了 ...
- 下一篇
Flutter Dojo的设计之道
认识Flutter是在18年,移动端开发日趋成熟的情况下,很多开发者都在寻求跨平台开发的终极法门,在经过了webview、RN的痛苦之后,Flutter的出现,给跨平台开发带来了一线曙光。自此,便开始了Flutter的学习之路,布道师之路,修仙之路。 筑基 Flutter的学习曲线很奇怪,像坐过山车一样,初学很简单,上手几天,很快就能写一些基本的界面,但是很快就遇到了瓶颈,因为官方的Widget越来越多,越来越复杂,学了忘,忘了学,有些人突破了,成为了一代先驱,有些人则被搞的一团雾水,大骂一声,垃圾Flutter,毁我青春。 相信大部分上手的开发者,都会抱怨两个问题,一是Widget太多,二是嵌套太多。嵌套太多的问题,没什么好解释的,大部分有这种抱怨的人,都是因为不知道如何正确的使用茫茫多的Widget而恼羞成怒的。 对于UI界面来说,树形结构是表现UI最好的方式,当然可以通过很多其它的方式来减少嵌套,但simple is fast,Android xml布局中,嵌套近十层的布局比比皆是,这对于写UI来说,并不会造成什么困扰。 但是Widget太多,确实是一个比较麻烦的问题,这里的学习...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS7设置SWAP分区,小内存服务器的救世主
- Hadoop3单机部署,实现最简伪集群
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Red5直播服务器,属于Java语言的直播服务器
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- CentOS8安装Docker,最新的服务器搭配容器使用
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- Linux系统CentOS6、CentOS7手动修改IP地址
- Windows10,CentOS7,CentOS8安装Nodejs环境
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作