本文实现了二叉树的深度遍历算法，分为递归与非递归
递归的实现非常简单，基本上没啥难度
非递归的实现需要根据遍历的顺序，将递归转换成循环
代码中的二叉树如下
---
### 递归
递归的实现很简单，此处不做过多赘述
```
package cn.lillcol.agst.test;
/**
* 定义 结点数据结构
*/
public class Node {
// 数据域
String data = "null";
// 左孩子
Node leftChild;
// 右孩子
Node rightChild;
// 是否被访问
boolean isVisit = false;
public void setIsVisit(boolean isVisit) {
this.isVisit = isVisit;
}
public boolean getisVisit() {
return this.isVisit;
}
public Node(String data) {
this.data = data;
}
public void setData(String data) {
this.data = data;
}
public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}
public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
@Override
public String toString() {
return this.data;
}
}
```
---
```
package cn.lillcol.agst.test;
/**
* 二叉树遍历案例递归版本
*
* @author lillcol
* @date 2020-01-16 23：56：51
*/
public class BTreeTestRecursion {
public static void main(String[] args) {
BTreeTestRecursion bTreeTestRecursion = new BTreeTestRecursion();
Node bTree = bTreeTestRecursion.createBTree();
System.out.print("前序遍历：");
bTreeTestRecursion.preOrderTraverse(bTree);
System.out.print("\n中序遍历：");
bTreeTestRecursion.inOrderTraverse(bTree);
System.out.print("\n后序遍历：");
bTreeTestRecursion.postOrderTraverse(bTree);
}
/**
* 生成一棵树
*
* @return
*/
public Node createBTree() {
Node A = new Node("A");
Node B = new Node("B");
Node C = new Node("C");
Node D = new Node("D");
Node E = new Node("E");
Node F = new Node("F");
Node G = new Node("G");
Node H = new Node("H");
Node I = new Node("I");
A.setLeftChild(B);
A.setRightChild(C);
B.setLeftChild(D);
C.setLeftChild(E);
C.setRightChild(F);
D.setLeftChild(G);
D.setRightChild(H);
E.setRightChild(I);
return A;
}
/**
* 前序遍历递归版本
*
* @param t
*/
public void preOrderTraverse(Node t) {
if (t == null) return;
System.out.print(t.data + "->");
preOrderTraverse(t.leftChild);
preOrderTraverse(t.rightChild);
}
/**
* 中序遍历 递归版本
*
* @param t
*/
public void inOrderTraverse(Node t) {
if (t == null) return;
inOrderTraverse(t.leftChild);
System.out.print(t.data + "->");
inOrderTraverse(t.rightChild);
}
/**
* 后续遍历 递归版本
*
* @param t
*/
public void postOrderTraverse(Node t) {
if (t == null) return;
postOrderTraverse(t.leftChild);
postOrderTraverse(t.rightChild);
System.out.print(t.data + "->");
}
}
```
---
### 非递归
非递归的实现比起递归相对复杂些。
核心是利用栈的特性，记录访问过的结点或输出的结点
非递归的实现中，先序遍历、中序遍历是比较简单的，只要按照便利的顺序结合代码的注释基本就可以理解了。
比较难的后续遍历，在实现的过程中发现，如果要按照访问顺序来进行实现，很复杂。
有些实现方式是通过增加一个标志位标记该借点是否访问过，但是却有问题：比如需要考虑很多子树的情况，判断情况特别多，只要少一个情况就会出错。
后面查看资料还有一个实现的方式相对简单很多，实现如下：
后序遍历可以看作逆先序遍历，此处有两个关键：
1. 结果是先序遍历的逆序
2. 此处的先序遍历不是从左到右的先序遍历，是从右到做的先序遍历，具体如下图
下面对比观察一下结果：
```
package cn.lillcol.agst.test;
import java.util.Stack;
/***
* 二叉树层次遍历的非递归实现版本
* @author lillcol 20200308
*/
public class BTreeTestNotRecursion {
public static void main(String[] args) throws InterruptedException {
BTreeTestNotRecursion bTreeTestNotRecursion = new BTreeTestNotRecursion();
Node bTree = bTreeTestNotRecursion.createBTree();
bTreeTestNotRecursion.inOrderTraverse(bTree);
bTreeTestNotRecursion.preOrderTraverse(bTree);
bTreeTestNotRecursion.postOrderTraverse(bTree);
}
/**
* 前序遍历 非递归版本
*
* @param t
*/
public void preOrderTraverse(Node t) {
if (t == null) return;
Stack
