Java 中有哪些遍历二叉树的方法，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。树结构多种多样，但是最常用的还是二叉树。二叉 香港云主机树中每个节点最多有两个子节点，这两个节点分别是左子节点和右子节点。注意：不要求都有两个子节点，可以只有左子节点，也可以只有右子节点。每个节点至少有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。这种存储方式比较常用，大部分二叉树代码都是通过这种结构来实现的。我们把根节点存储在下标 i=1 的位置，它的左子节点存储在下标为 2 * i 的位置，右子节点存储在下标为 2*i+1 的位置。以此类推，B 节点、C 节点的左右子节点都按照这种规律进行存储，最终如下图所示。综上，如果节点 X 存储在数组中下标为 i 的位置，那么下标为 2*i 的位置存储的就是它的左子节点，下标为 2*i+1 的位置存储的就是它的右子节点。反过来，i/2 的位置存储的就是它的父节点。一般情况下，为了方便计算，根节点会被存储在下标为 1 的位置。通过上述可以看到，针对一般树来说，使用数组的方式存储树会浪费比较多的存储空间。但是针对下文会提到的满二叉树或者完全二叉树来说，数组存储的方式是最节省内存的一种方式。因为数组存储时，不需要再存储额外的左右子节点的指针。二叉树的遍历就是将二叉树中的所有节点遍历打印出来。经典的方法有三种，前序遍历、中序遍历和后序遍历，还可以按层遍历（个人理解的按层遍历其实就是按照图的广度优先遍历方法来进行遍历）。前、中、后是根据节点被打印的先后来进行区分的：前序就是先打印节点本身，之后再打印它的左子树，最后打印它的右子树；中序就是先打印节点的左子树，再打印节点本身，最后打印右子树，即把节点放中间的位置输出；后序就是先打印节点的左子树，再打印节点的右子树，最后打印节点本身。如下图所示按层遍历类似于图的广度优先遍历，先打印第一层的节点，之后再依次打印第二层的节点，以此类推。实际上，二叉树的前、中、后序遍历是一个递归的过程。比如，前序遍历，其实就是先打印根节点，然后递归遍历左子树，最后递归遍历右子树。递归遍历左右子树其实就跟遍历根节点的方法一样。下面先写出这三者遍历的递推公式：之后将递推公式转化为代码如下所示：递归代码的关键，在于写出递推公式。而递推公式的关键在于，A 问题可以被拆解成 B、C 两个问题。假设要解决 A 问题，那么假设 B、C 问题已经解决了。那么在 B、C 已经解决的提前下，看如何利用 B、C 来解决 A 。千万不要模拟计算机一层一层想下去，否则你就会发现你自己都不知道在哪了。下面是按层遍历的代码，按层遍历需要用到队列的入队和出队等操作。先将根节点放入到队列中，然后循环从队列中取节点（出队），再将该节点的左右子节点入队。出队的顺序就是层次遍历的结果。完整的代码可查看 github 仓库 https://github.com/DawnGuoDev/algos ，这个仓库将主要包含常用数据结构及其基本操作的手写实现（Java），也会包含常用算法思想经典例题的实现（Java）。在程序锅找到工作之前，这个仓库将会保持更新状态，在此之间学到的关于数据结构和算法的知识或者实现也都会往里面 commit，所以赶紧来 star 哦。遍历过程中的次数就是访问所有节点的所需的次数，而每个节点最多被访问两次，因此遍历的时间复杂度是跟节点的个数 n 成正比的，即遍历的时间复杂度是 O(n)。满二叉树是一种特殊的二叉树，而且还是完全二叉树的一种特殊情况。如上图编号 2 的那棵树所示，叶子节点全在底层，除了叶子节点之外，每个节点都有左右两个子节点。完全二叉树也是一种特殊的二叉树。如上图编号 3 的那棵树所示，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都达到最大。完全二叉树的特征使得它可以使用数组就可以很好地存储数据。完全二叉树要求最后一层的叶子节点靠左排列也是因为如此。链式存储就是上面提到的那种方式。数组存储完全二叉树使用数组存储时，如下图所示。我们发现使用数组来存储完全二叉树是一种很节省内存的方式。这也是完全二叉树被作为一种特殊树的原因，也是完全二叉树要求最后一层的子节点必须都靠左的原因。在讲解堆或者堆排序的时候，堆其实也是一种完全二叉树，最常用的存储方式就是数组。看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注开发云行业资讯频道，感谢您对开发云的支持。
这篇文章主要介绍“win10中找不到网络路径怎么办”，在日常操作中，相信很多人在win10中找不到网络路径怎么办问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”win10中找不到网络路径怎么办”的疑惑有所帮助！接下来，请跟着小编一…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
