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节点的左子节点是2rootNode.setRight(nodes[2]);//1节点的右子节点是3nodes[1].setLeft(nodes[3]);//2节点的左子节点是4nodes[1].setRight(nodes[4]);//2节点的右子节点是5nodes[3].setRight(nodes[7]);//4节点的右子节点是8nodes[4].setRight(nodes[8]);//5节点的右子节点是9nodes[2].setLeft(nodes[5]);//3节点的左子节点是6nodes[2].setRight(nodes[6]);//3节点的右子节点是7nodes[5].setLeft(nodes[9]);//6节点的左子节点是10nodes[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节点的左子节点是2rootNode.setRight(nodes[2]);//1节点的右子节点是3nodes[1].setLeft(nodes[3]);//2节点的左子节点是4nodes[1].setRight(nodes[4]);//2节点的右子节点是5nodes[3].setRight(nodes[7]);//4节点的右子节点是8nodes[4].setRight(nodes[8]);//5节点的右子节点是9nodes[2].setLeft(nodes[5]);//3节点的左子节点是6nodes[2].setRight(nodes[6]);//3节点的右子节点是7nodes[5].setLeft(nodes[9]);//6节点的左子节点是10nodes[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节点的左子节点是2rootNode.setRight(nodes[2]);//1节点的右子节点是3nodes[1].setLeft(nodes[3]);//2节点的左子节点是4nodes[1].setRight(nodes[4]);//2节点的右子节点是5nodes[3].setRight(nodes[7]);//4节点的右子节点是8nodes[4].setRight(nodes[8]);//5节点的右子节点是9nodes[2].setLeft(nodes[5]);//3节点的左子节点是6nodes[2].setRight(nodes[6]);//3节点的右子节点是7nodes[5].setLeft(nodes[9]);//6节点的左子节点是10nodes[5].setRight(nodes[10]);//6节点的右子节点是11}
//后序遍历
private void postOrder() {
if (rootNode != null) { System.out.println("二叉树的后序遍历~~"); rootNode.postOrder();} else { System.out.println("这是一棵空树");}}
}
程序运行后果如下所示：
图片
程序输入的后果跟咱们下面剖析图1的后序遍历输入程序也是截然不同的。
小结：如何判断它是前序遍历还是中序遍历或者后续遍历，其实很简略，是有法则的，咱们可认为配角是父节点，如果是优先输入父节点，那便是前序遍历；如果优先输入左子树，再输入父节点，那便是中序遍历；如果是最初才输入父节点，那便是后续遍历。