共计 6885 个字符，预计需要花费 18 分钟才能阅读完成。
PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
目录
1、二叉树的遍历
1、1 前序遍历
1、2 中序遍历
1、3 后续遍历
1、二叉树的遍历
1、1 前序遍历
从 Java 版的数据结构和算法（三）这篇文章中，咱们学到了二叉树的罕用术语和二叉树的概念，这里咱们说一下二叉树的遍历，咱们能够应用前序遍历、中序遍历和后序遍历这 3 种形式对二叉树进行遍历；咱们先说说前序遍历，前序遍历的输入程序是：父节点 -> 左子树 -> 右子树，留神：叶子节点也能够看作一棵子树。
好，咱们列举一下前序遍历的步骤：
（1）创立一棵二叉树。
（2）先输入以后节点（初始化的时候是根节点）。
（3）如果左子树不为空，则递归持续前序遍历。
（4）如果右子树不为空，则递归持续前序遍历。
有的读者可能会说，看了前序遍历的步骤，我还是懵啊，没关系，咱们举个例子，先画出一棵二叉树，如图 1 所示：
图片
好，咱们用前序遍历说一下图 1 的思路；
（1）首先 1 节点是根节点，咱们该当优先输入 1 节点。
（2）而后遍历 1 节点的左子树 2，发现 2 节点是 4 节点和 5 节点的父节点，所以把 2 节点输入来。
（3）遍历 2 节点的左子树 4，发现 4 节点是 8 节点的父节点，所以把 4 节点输入来。
（4）这时候 4 节点没有左子树，只有右子树，而后去遍历 4 节点的右子树 8，8 节点作为叶子节点间接输入来。
（5）到了这里，2 节点的左子树遍历完了，而后去遍历 2 节点的右子树 5，5 节点作为 9 节点的父节点先输入来。
（6）5 节点没有左子树，间接去遍历右子树 9，发现 9 节点是叶子节点间接输入来。
（7）到了这里根节点 1 的左子树遍历完了，而后去遍历右子树 3，3 节点 6 节点和 7 节点的父节点，所以优先输入 3 节点。
（8）而后又去遍历 3 节点的左子树 6，6 节点作为 10 节点和 11 节点的父节点，间接输入 6 节点。
（9）遍历 6 节点的左子树 10，发现 10 节点是叶子节点间接输入来。
（10）到了这里，6 节点的左子树曾经遍历完了，而后去遍历 6 节点的右子树 11，发现 11 节点是叶子节点间接输入来。
（11）到了这里，3 节点的左子树曾经遍历完了，接着去遍历 3 节点的右子树 7，发现 7 节点是叶子节点间接输入来。
最初用前序遍历图 1 的二叉树程序为：1 2 4 8 5 9 3 6 10 11 7；到了这里，二叉树的前序遍历的规定应该晓得了吧？好了，咱们当初用代码实现一把创立图 1 的二叉树并进行前序遍历。
（1）节点类 Node：
public class Node {
private int value;
private Node left;
private Node right;
public Node(int value) {
super();
this.value = value;}
public void setLeft(Node left) {
this.left = left;}
public void setRight(Node right) {
this.right = right;}
@Override
public String toString() {
return "Node [value=" + value + "]";}
public void preOrder() {
// 输入以后节点（如果以后节点有子节点，那么它就是父节点，否则就是叶子节点）System.out.println(this);
// 递归向左子树进行前序遍历
if (left != null) {left.preOrder();
}
// 递归向右子树进行前序遍历
if (right != null) {right.preOrder();
}}
}
（2）测试类 BinaryTreeTest：
public class BinaryTreeTest {
private Node rootNode;
public static void main(String[] args) {
BinaryTreeTest test = new BinaryTreeTest();
test.createBinaryTree();
test.preOrder();}
private void createBinaryTree() {
Node[] nodes = new Node[11];
for (int i = 1; i <= nodes.length; i++) {nodes[i-1] = new Node(i);
}
rootNode = nodes[0];// 1 节点为根节点
rootNode.setLeft(nodes[1]);// 1 节点的左子节点是 2
rootNode.setRight(nodes[2]);// 1 节点的右子节点是 3
nodes[1].setLeft(nodes[3]);// 2 节点的左子节点是 4
nodes[1].setRight(nodes[4]);// 2 节点的右子节点是 5
nodes[3].setRight(nodes[7]);// 4 节点的右子节点是 8
nodes[4].setRight(nodes[8]);// 5 节点的右子节点是 9
nodes[2].setLeft(nodes[5]);// 3 节点的左子节点是 6
nodes[2].setRight(nodes[6]);// 3 节点的右子节点是 7
nodes[5].setLeft(nodes[9]);// 6 节点的左子节点是 10
nodes[5].setRight(nodes[10]);// 6 节点的右子节点是 11}
private void preOrder() {
if (rootNode != null) {System.out.println("二叉树的前序遍历~~");
rootNode.preOrder();} else {System.out.println("这是一棵空树");
}}
}
程序运行后果如下所示：
图片
程序输入的后果跟咱们下面剖析图 1 的前序遍历输入程序是截然不同的。
1、2 中序遍历
中序遍历的输入程序是：左子树 -> 父节点 -> 右子树，上面咱们列举一下中序遍历的步骤：
（1）创立一棵二叉树。
（2）如果以后节点的左子节点不为空，那么则递归中序遍历。
（3）输入以后节点。
（4）如果以后节点的右子节点不为空，那么则递归中序遍历。
首先中序遍历最优先遍历的是左子树对不对，好，上面也举个例子，咱们用中序遍历同样说一下图 1 的思路；
（1）一开始找到根节点 1，发现根节点右左右子树，先往下递归左子树进行中序遍历，也就是去遍历左子树 2。
（2）发现节点 2 也有左右子树，也先往下递归左子树进行中序遍历，也就是去遍历右子树 4。
（3）发现 4 节点没有左子树，只有右子树，所以这里先输入 4 节点，而后去遍历 4 节点的右子树 8。
（4）发现 8 节点是叶子节点，间接输入 8 节点。
（5）到了这里 2 节点的左子树曾经遍历完了，而后将 2 节点间接输入，这时去遍历 2 节点的右子树 5。
（6）发现 5 节点没有左子树，只有右子树，所以这里就先输入 5 节点，而后 5 节点的右子树 9，发现 9 节点是叶子节点，就间接输入 9 节点。
（7）到了这里，1 节点的曾经遍历完了，而后将 1 节点间接输入，这时候去遍历 1 节点的右子树 3。
（8）发现 3 节点有左右子树，而后先去遍历 3 节点的左子树 6，这时候发现 6 节点也有左右子树。
（9）先去遍历 6 节点的左子树 10，发现 10 节点是叶子节点，间接输入 10 节点。
（10）到了这一步，6 节点的左子树曾经遍历完了，而后将 6 节点间接输入，这时候去遍历 6 节点的右子树 11。
（11）发现 11 节点是叶子节点，间接将 11 节点输入来。
（12）到了这一步，3 节点的左子树曾经遍历完了，而后将 3 节点间接输入来，这时候去遍历 3 节点的右子树 7。
（13）发现 7 节点是叶子节点，间接将 7 节点输入来。
最初用中序遍历图 1 的二叉树程序为：4 8 2 5 9 1 10 6 11 3 7；到了这里，二叉树的中序遍历的规定咱们曾经摸清楚了，咱们也用代码实现一把创立图 1 的二叉树并进行中序遍历。
（1）节点类 Node2：
public class Node2 {
private int value;
private Node2 left;
private Node2 right;
public Node2(int value) {
super();
this.value = value;}
public void setLeft(Node2 left) {
this.left = left;}
public void setRight(Node2 right) {
this.right = right;}
@Override
public String toString() {
return "Node2 [value=" + value + "]";}
public void midOrder() {
// 递归向左子树进行前序遍历
if (left != null) {left.midOrder();
}
// 输入以后节点
System.out.println(this);
// 递归向右子树进行前序遍历
if (right != null) {right.midOrder();
}}
}
（2）测试类 BinaryTreeTest2：
public class BinaryTreeTest2 {
private Node2 rootNode;
public static void main(String[] args) {
BinaryTreeTest2 test = new BinaryTreeTest2();
test.createBinaryTree();
test.midOrder();}
// 创立图 1 的一棵二叉树
private void createBinaryTree() {
Node2[] nodes = new Node2[11];
for (int i = 1; i <= nodes.length; i++) {nodes[i-1] = new Node2(i);
}
rootNode = nodes[0];// 1 节点为根节点
rootNode.setLeft(nodes[1]);// 1 节点的左子节点是 2
rootNode.setRight(nodes[2]);// 1 节点的右子节点是 3
nodes[1].setLeft(nodes[3]);// 2 节点的左子节点是 4
nodes[1].setRight(nodes[4]);// 2 节点的右子节点是 5
nodes[3].setRight(nodes[7]);// 4 节点的右子节点是 8
nodes[4].setRight(nodes[8]);// 5 节点的右子节点是 9
nodes[2].setLeft(nodes[5]);// 3 节点的左子节点是 6
nodes[2].setRight(nodes[6]);// 3 节点的右子节点是 7
nodes[5].setLeft(nodes[9]);// 6 节点的左子节点是 10
nodes[5].setRight(nodes[10]);// 6 节点的右子节点是 11}
// 中序遍历
private void midOrder() {
if (rootNode != null) {System.out.println("二叉树的中序遍历~~");
rootNode.midOrder();} else {System.out.println("这是一棵空树");
}}
}
程序运行后果如下所示：
图片
程序输入的后果跟咱们下面剖析图 1 的中序遍历输入程序也是截然不同的。
1、3 后序遍历
后序遍历的输入程序是：左子树 -> 右子树 -> 父节点，上面咱们列举一下后序遍历的步骤：
（1）创立一棵二叉树。
（2）如果以后节点的左子节点不为空，那么则递归后序遍历。
（3）如果以后节点的右子节点不为空，那么则递归后序遍历。
（4）输入以后节点。
后序遍历最优先遍历的是左子树，其次是右子树，最初是父节点，好，上面也举个例子，咱们用后序遍历同样说一下图 1 的思路；
（1）一开始找到根节点 1，发现根节点 1 有左右 2 棵子树，先优先去遍历根节点 1 的左子树 2。
（2）发现 2 节点也有左右 2 棵子树，也优先去遍历 2 节点的左子树 4。
（3）这时候发现 4 节点没有左子树，有右子树，于是先去遍历 4 节点的右子树 8。
（4）发现 8 节点是叶子节点，间接将 8 节点输入来。
（5）这时候 4 节点的右子树遍历完了，而后将 4 节点间接输入来。
（6）到了这里，2 节点的左子树曾经遍历完了，于是这就去遍历 2 节点的右子树 5。
（7）发现 5 节点没有左子树，只有右子树，于是先去遍历 5 节点的右子树 9。
（8）发现 9 节点是叶子节点，间接将 9 节点输入来。
（9）这时候 5 节点的右子树曾经遍历完了，这就将 5 节点间接输入来。
（10）也这时候 2 节点的右子树曾经遍历完了，也将 2 节点间接输入来。
（11）到了这里，根节点 1 的左子树曾经遍历完了，这就去遍历根节点 1 的右子树 3。
（12）发现 3 节点有左右 2 棵子树，优先遍历 3 节点的左子树 6。
（13）发现 6 节点也有左右 2 棵子树，也优先遍历 6 节点的左子树 10。
（14）发现 10 节点是叶子节点，间接将 10 节点输入来。
（15）这时候 6 节点的左子树遍历完了，于是去遍历 6 节点的右子树 11。
（16）发现 11 节点是叶子节点，间接将 11 节点输入来。
（17）到了这里 6 节点的右子树曾经遍历完了，这就将 6 节点间接输入来。
（18）也到了这里 3 节点的左子树曾经遍历完了，于是去遍历 3 节点的右子树 7。
（19）发现 7 节点是叶子节点，间接将 7 节点输入来。
（20）这时候 3 节点的右子树曾经遍历完了，这就将 3 节点间接输入来。
（21）到了这里根节点 1 的右子树也曾经遍历完了，这就将根节点 1 输入来。
最初用后序遍历图 1 的二叉树程序为：8 4 9 5 2 10 11 6 7 3 1；到了这里，二叉树的后序遍历的规定咱们也搞清楚了，咱们用代码实现一把图 1 的后序遍历。
（1）节点类 Node3：
public class Node3 {
private int value;
private Node3 left;
private Node3 right;
public Node3(int value) {
super();
this.value = value;}
public void setLeft(Node3 left) {
this.left = left;}
public void setRight(Node3 right) {
this.right = right;}
@Override
public String toString() {
return "Node3 [value=" + value + "]";}
public void postOrder() {
// 递归向左子树进行前序遍历
if (left != null) {left.postOrder();
}
// 递归向右子树进行前序遍历
if (right != null) {right.postOrder();
}
// 输入以后节点
System.out.println(this);}
}
（3）测试类 BinaryTreeTest3：
public class BinaryTreeTest3 {
private Node3 rootNode;
public static void main(String[] args) {
BinaryTreeTest3 test = new BinaryTreeTest3();
test.createBinaryTree();
test.postOrder();}
// 创立图 1 的一棵二叉树
private void createBinaryTree() {
Node3[] nodes = new Node3[11];
for (int i = 1; i <= nodes.length; i++) {nodes[i-1] = new Node3(i);
}
rootNode = nodes[0];// 1 节点为根节点
rootNode.setLeft(nodes[1]);// 1 节点的左子节点是 2
rootNode.setRight(nodes[2]);// 1 节点的右子节点是 3
nodes[1].setLeft(nodes[3]);// 2 节点的左子节点是 4
nodes[1].setRight(nodes[4]);// 2 节点的右子节点是 5
nodes[3].setRight(nodes[7]);// 4 节点的右子节点是 8
nodes[4].setRight(nodes[8]);// 5 节点的右子节点是 9
nodes[2].setLeft(nodes[5]);// 3 节点的左子节点是 6
nodes[2].setRight(nodes[6]);// 3 节点的右子节点是 7
nodes[5].setLeft(nodes[9]);// 6 节点的左子节点是 10
nodes[5].setRight(nodes[10]);// 6 节点的右子节点是 11}
// 后序遍历
private void postOrder() {
if (rootNode != null) {System.out.println("二叉树的后序遍历~~");
rootNode.postOrder();} else {System.out.println("这是一棵空树");
}}
}
程序运行后果如下所示：
图片
程序输入的后果跟咱们下面剖析图 1 的后序遍历输入程序也是截然不同的。
小结：如何判断它是前序遍历还是中序遍历或者后续遍历，其实很简略，是有法则的，咱们可认为配角是父节点，如果是优先输入父节点，那便是前序遍历；如果优先输入左子树，再输入父节点，那便是中序遍历；如果是最初才输入父节点，那便是后续遍历。
