# 二叉树遍历总结（先序||中序||后序||按层遍历||之字遍历&&递归||非递归）

### 先序遍历

##### 递归
```    public static void printBTPerRecursion(TreeNode root){
if (root!=null){
System.out.print(root.value+" ");
printBTPerRecursion(root.left);
printBTPerRecursion(root.right);
}
}```
##### 非递归
``` public static void printBTPerUnrecursion(TreeNode node){
while (node!=null||!stack.isEmpty()){
if (node!=null){
System.out.print(node.value+" ");
stack.push(node);
node = node.left;
}
else {
node = stack.pop();
node = node.right;
}
}
}```

### 中序遍历

##### 递归
```public static void printBTMidRecursion(TreeNode root){
if (root!=null){
printBTMidRecursion(root.left);
System.out.print(root.value+" ");
printBTMidRecursion(root.right);
}
}```
##### 非递归
``` public static void printBTMidUnrecursion(TreeNode node){
while (node!=null||!stack.isEmpty()){
if (node!=null){
stack.push(node);
node = node.left;
}else {
TreeNode node1 = stack.pop();
System.out.print(node1.value+" ");
node = node1.right;
}
}
}```

### 后序遍历

##### 递归
```    public static void printBTBackRecursion(TreeNode root){
if (root!=null){
printBTBackRecursion(root.left);
printBTBackRecursion(root.right);
System.out.print(root.value+" ");
}
}```
##### 非递归（）
```//非递归后序遍历 参考自https://blog.csdn.net/zhuqiuhui/article/details/51319165
public static void printBTBackUnrecursion(TreeNode node){
if (node==null)return;
TreeNode curNode;
TreeNode lastVisitNode;
curNode = node;
lastVisitNode = null;
//先找到最左节点
while (curNode!=null){
stack.push(curNode);
curNode = curNode.left;
}
while (!stack.empty()){
curNode = stack.pop();
//如果此结点右节点不为空且没有被访问过，那么将它再次入栈，并顺着它的右节点再次入栈左节点
if (curNode.right!=null&&curNode.right!=lastVisitNode){
stack.push(curNode);
curNode = curNode.right;
while (curNode!=null){
stack.push(curNode);
curNode = curNode.left;
}
}else {
System.out.print(curNode.value+" ");
lastVisitNode = curNode;
}
}
}```

### 按层遍历（使用队列实现）

##### 递归
```public static void printLayerRecursion(TreeNode root) throws InterruptedException {
System.out.print(root.value+" ");
TreeNode treeNode = queue.poll();
if (treeNode!=null)
printLayerRecursion(treeNode);
}```
##### 非递归
``` public static void printLayerUnrecursion(TreeNode node){
if (node==null)return;
while (!queue.isEmpty()){
TreeNode node1 = queue.poll();
System.out.print(node1.value+" ");
}
}```

### 之字遍历

##### 非递归（需要两个栈，两个栈交替装入每一层的结点，一个栈先装左节点再装右节点，另一个栈先装右节点再装左节点）
```public static void printBTlikeZHI(TreeNode node){
if (node==null)return;
stack.push(node);
int current = 0;
int next = 1;
while (!stack.empty()||!otherStack.isEmpty()){
TreeNode node1 = (TreeNode) stacks[current].pop();
System.out.print(node1.value+" ");
if (current==0){
if (node1.left!=null)stacks[next].push(node1.left);
if(node1.right!=null)stacks[next].push(node1.right);

}else {
if (node1.right!=null)stacks[next].push(node1.right);
if (node1.left!=null)stacks[next].push(node1.left);

}
if (stacks[current].empty()){
current = 1-current;
next = 1-next;
}
}
}```

0 条评论

• ### 计数排序

计数排序和原来说过的几个排序算法有一个特别大的不同之处：它是一个不基于比较的排序算法。不管是快排，归并，还是堆排，它们都难以突破NlogN的运行时间下限，而计数...

• ### JDK源码——Arrays.sort()的实现

可见，Arrays并没有自己来实现排序，而是委托给了DualPivotQuicksort类。进入上边的sort方法

• ### 浅谈java线程池（基于jdk1.8）

多线程让程序世界丰富多彩，也让其错综复杂。对于线程的创建和销毁成了一笔不小的开销，为了减少这些开销，出现了线程池。线程池对线程进行管理，对于需要使用多线程的我们...

• ### 【编程经验】表达式和语句及选择结构

在C中，表达式代表值，而语句代表给计算机的指令。 表达式 表达式由运算符和操作数组成。最简单的表达式只是一个不带运算符的常量或者变量，例如12或者num。...

• ### 5.1 if语句

C语言有两种选择语句，if语句和switch语句，if语句是用来实现两个分支的选择结构。

• ### python基础知识——控制语句

其中，raw_input()用于获取控制台的输入，由于raw_input()返回的是字符串，则在比较的时候必须使用int()转换，若是不想转换，可以直接使...

• ### python基础知识——控制语句

控制语句主要有条件语句和循环语句。 一、条件语句 1、if语句 格式 if 表达式： 语句1 else: 语句2 如下面的例子： ...

• ### Python学习-if条件语句

Python条件语句是通过一条或多条语句的执行结果（True或者False）来决定执行的代码块。

• ### 卫语句

动机：条件表达式通常有2种表现形式。第一：所有分支都属于正常行为。第二：条件表达式提供的答案中只有一种是正常行为，其他都是不常见的情况。