二叉树广度遍历java,深度优先遍历相当于二叉树
如何解决写爬虫IP受阻的问题？立即使用。
这两天在做二叉树相关的算法题，做一些学习笔记。(连二叉树都没有？我真的不熟练，平时也不用写二叉树相关的算法或者数据结构。因为自己做饭，所以要更加努力学习！)
定义
先看看维基百科的解释：在计算机科学中，二叉树(英文：Binary tree)是每个节点最多有两个分支的树结构(即不存在分支大于2的节点)。通常，分支被称为“左子树”或“右子树”。二叉树的分支有左右顺序，不能随意颠倒。
由于二叉树定义的特点，它具有高度的局部可重复性，所以在首先对二叉树进行深度遍历时，通常采用递归的方式实现。这样实现的代码非常简洁，美观，易于理解。
深度优先遍历
一般来说，我们的深度优先遍历二叉树有三种最常见的顺序遍历：前序、中序和后序。
遍历的顺序是：访问根节点——遍历左子树——遍历右子树。
中间顺序的遍历顺序是：遍历左子树-访问根节点-遍历右子树。
下面的遍历顺序是：遍历左子树-遍历右子树-访问根节点。
注意，这里的左右是整个子树，不是一个节点。因为我们需要遍历整个树，所以每次遍历都是按照这个顺序执行的，直到叶子节点。
例如，假设有以下二叉树：
通过前序遍历得到的序列是A-B-C-D-E
遍历中间顺序得到的序列是B-A-D-C-E
后序遍历得到的序列是B-D-E-C-A
先说前序遍历方面的思维方式(不建议去人肉递归，至少我的大脑承受不了三层。):
递归的第一级：
先访问根节点，所以输出根节点A，然后遍历左子树(L1)，再遍历右子树(R1)；
二级递归：
对于L1，先访问根节点，所以输出此时的根节点B，然后发现B的左右子树为空，结束递归；
对于R1，先访问根节点，所以输出此时的根节点C，然后遍历左子树(L2)，再遍历右子树(R2)；
第三层递归：
对于L2，先访问根节点，所以输出此时的根节点D，然后发现D的左右子树为空，结束递归；
对于R2，先访问根节点，所以输出此时的根节点E，然后发现E的左右子树都是空的，结束递归；
前中后序特征
根据前中后的定义，其实我们很容易发现以下几个特点：
顺序中的第一个必须是根节点，顺序中的最后一个必须是根节点。
每种排序的左子树和右子树的分布是有规律的。
每个子树都遵循上述两条规则的树。
这些特征是定义中秩序的表现。
各种推导
下面是二叉树遍历的一些基本算法：
给定一棵二叉树，求其前/中/后序遍历的序列；
根据前序和中序导出后序(或整个二叉树)；
根据后序和中序导出前序(或整个二叉树)；
如前所述，二叉树的遍历通常是通过递归完成的。对于递归，有一些模板可以直接应用：
public void recurve(int level，int param) {
//终止符
if (level MAX_LEVEL) {
//处理结果
返回；
}
//处理当前逻辑
过程(级别，参数)；
//深入查看
recurve(level 1，new param)；
//恢复当前状态
}这是超哥(覃超)这两天在极客时间的算法训练营里讲的一个实用技巧(这个模板特别适合新手)。按照上面的三个步骤(如果有局部变量需要释放或者额外处理，做第四步)以更有条理的方式编写递归代码。
这里以前面订单和中间订单推导后面订单为例：
首先初始化两个序列：
int[]pressequence={ 1，2，3，4，5，6，7，8，9 }；
int[] inSequence={2，3，1，6，7，8，5，9，4 }；通过上面提到的特征，我们已经可以找到最小重复子问题，每次递归。
根据前导码的第一个结点值，匹配前导码中节点值所在的索引I，这样我们就可以得到索引I中分别对应左右两个子树的两部分，然后分别遍历这左右两个子树，再输出当前前导码的第一个节点值，也就是根节点。
按照自顶向下的编程方法，我们可以先编写下面的初始递归调用：
list integer result=new ArrayList()；
preandtopost(0，0，preSequence.length，preSequence，inSequence，result)；第一个参数指示前导序列的第一个元素的索引；
第二个参数指示中间顺序序列的第一个元素索引；
第三个参数表示序列的长度；
第四个参数表示前导序列；
第五个参数表示后续序列；
第六个参数用于保存结果；
我们先考虑终止条件是什么，也就是递归什么时候结束，当我们的根节点为空的时候就结束，也就是序列长度为零的时候。
if(长度==0) {
返回；
}然后考虑处理逻辑，也就是找到索引I:
int I=0；
while (inSequence[inIndex i]！=preSequence[preIndex]) {
我；
}然后开始向下递归：
preandtopost(pre index 1，inIndex，I，preSequence，inSequence，result)；
preandtopost(pre index I 1，inIndex i 1，length - i - 1，preSequence，inSequence，result)；
result . add(pre sequence[pre index])；因为推导顺序，所以顺序如上，添加根节点的操作在最后。怎么得到前三个参数？我们可以通过第一次遍历得到它们。
前序序列中第一个节点1的索引在中序序列中是2。此时此刻
左子树中序序列的起始索引是全序列的第一个索引，长度为2；
左子树的前序序列的初始索引是总序列的第二个索引，长度为2；
右子树的中序序列的起始索引是总序列的第三个索引，其长度为length-3；
右子树的前序序列的起始索引为总序列的第三个索引，长度为length-3；
完整的代码如下：
/**
*根据前面序列和中间序列推导后面序列。
*
* @param preIndex前导索引
* @param inIndex中间顺序索引
* @param length序列长度
* @ param preSequence前导序列
* @param inSequence中间序列
* @param结果结果序列
*/
private void preAndInToPost(int preIndex，int inIndex，int length，int[] preSequence，int[] inSequence，ListInteger result) {
if(长度==0) {
返回；
}
int I=0；
while (inSequence[inIndex i]！=preSequence[preIndex]) {
我；
}
preandtopost(pre index 1，inIndex，I，preSequence，inSequence，result)；
preandtopost(pre index I 1，inIndex i 1，length - i - 1，preSequence，inSequence，result)；
result . add(pre sequence[pre index])；
}推荐教程：以上《java教程》是java中二叉树深度优先遍历的详细内容。更多请关注我们的其他相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。