PS：本文为转载文章，原文可读性会更好，文末有原文链接。序遍历1,3后序遍历1,二叉树遍历1,1前序遍历从本文Java版的数据结构和算法（三），我们了解了二叉树的常用术语和二叉树的概念tree，这里说说对于二叉树的遍历，我们可以使用前序遍历、中序遍历和后序遍历三种方式来遍历二叉树；先说前序遍历，前序遍历的输出顺序是：父节点->左子树->右子树，注意：叶子节点也可以看成是一棵子树。好吧，让我们列出前序遍历的步骤：(1)创建一棵二叉树。(2)先输出当前节点（初始化时为根节点）。(3)如果左子树不为空，则递归继续前序遍历。(4)如果右子树不为空，则递归继续前序遍历。可能有读者会说，我看了前序遍历的步骤还是一头雾水。图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-node的左子树6，将6-node作为10-node和11-node的父节点，直接输出6-node。(9)遍历6个节点的左子树10，发现10个节点直接从叶子节点输出。(10)至此，已经遍历了6个节点的左子树，再遍历6个节点的右子树11，发现节点11为叶子节点，直接输出。(11)至此，已经遍历了节点3的左子树，再遍历节点3的右子树7，发现节点7为叶子节点，直接输出。最后按前序遍历图1中二叉树的顺序：1248593610117；到这里，你应该知道二叉树的前序遍历规则了吧？那么，我们现在使用代码创建图1中的二叉树并执行前序遍历。(1)节点类Node:publicclassNode{privateintvalue;私有节点离开；私有节点权；publicNode(intvalue){super();this.value=value;}publicvoidsetLeft(Nodeleft){this.left=left;}publicvoidsetRight(Noderight){this.right=right;}@OverridepublicStringtoString(){return"Node[value="+value+"]";}publicvoidpreOrder(){//输出当前节点（如果当前节点有子节点，则为父节点，否则是叶子节点)System.out.println(this);//递归前序遍历左子树if(left!=null){left.preOrder();}//递归前序遍历右子树if(right!=null){right.preOrder();}}}(2)测试类BinaryTreeTest:publicclassBinaryTreeTest{privateNoderootNode;publicstaticvoidmain(String[]args){BinaryTreeTesttest=newBinaryTreeTest();test.createBinaryTree();test.preOrder();}privatevoidcreateBinaryTree(){Node[]nodes=newNode[11];for(inti=1;i<=nodes.length;i++){nodes[i-1]=newNode(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}privatevoidpreOrder(){if(rootNode!=null){System.out.println("二叉树的前序遍历~~");rootNode.preOrder();}else{System.out.println("Thisisanemptytree");}}}程序运行结果如下：图像程序的输出与输出顺序完全一致上图1中的前序遍历。1,2中序遍历的输出顺序为：左子树->父节点->右子树，下面列出中序遍历的步骤：(1)创建一棵二叉树。(2)如果当前节点的左子节点不为空，则递归中序遍历。(3)输出当前节点。(4)如果当前节点的右子节点不为空，则递归中序遍历。首先，中序遍历的优先级是遍历左子树吧？好吧，下面举个例子。下面用中序遍历来谈谈图1的思路；(1)一开始找到根节点1，找到根节点right的左右子树，先递归向下左子树进行中序遍历，即遍历左子树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中二叉树的顺序：4825911061137；到这里，我们已经弄清楚了二叉树中序遍历的规则，我们也用代码实现了图1二叉树的创建和中序遍历。(1)节点类Node2：publicclassNode2{privateintvalue;私有Node2离开；私有Node2权限；publicNode2(intvalue){super();this.value=value;}publicvoidsetLeft(Node2left){this.left=left;}publicvoidsetRight(Node2right){this.right=right;}@OverridepublicStringtoString(){return"Node2[value="+value+"]";}publicvoidmidOrder(){//递归对左子树进行前序遍历if(left!=null){left.midOrder();}//输出当前节点System.out.println(this);//递归对右子树进行前序遍历if(right!=null){right.midOrder();}}}(2)测试类BinaryTreeTest2:publicclassBinaryTreeTest2{privateNode2rootNode;publicstaticvoidmain(String[]args){BinaryTreeTest2test=newBinaryTreeTest2();test.createBinaryTree();test.midOrder();}//创建图1中的二叉树privatevoidcreateBinaryTree(){Node2[]nodes=newNode2[11];for(inti=1;i<=nodes.length;i++){nodes[i-1]=newNode2(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}//中序遍历privatevoidmidOrder(){if(rootNode!=null){System.out.println("二叉树的中序遍历~~");rootNode.midOrder();}else{System.out.println("Thisisaemptytree");}}}程序运行结果如下：图像程序的输出与输出序列完全一致上图1中的中序遍历。1,3后序遍历的输出顺序为：左子树->右子树->父节点，下面列出后序遍历的步骤：(1)创建一棵二叉树。(2)如果当前节点的左子节点不为空，则递归后序遍历。(3)如果当前节点的右子节点不为空，则递归后序遍历。(4)输出当前节点。后序遍历先遍历左子树，再遍历右子树，最后遍历父节点。好吧，让我们在下面举个例子。下面用后序遍历来谈谈图1的思路；(1)开始查找Rootnode1发现rootnode1有左右子树，先遍历rootnode1的左子树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个节点都有左右子树，左子树首先遍历3个节点的子树6。(13)发现6个节点也有左右子树，同样先遍历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中二叉树的顺序：8495210116731；到这里，我们也想通了二叉树的后序遍历规则，我们用代码实现了图1中的后序遍历。(1)节点类Node3：publicclassNode3{privateintvalue;私有Node3离开；私有Node3权限；publicNode3(intvalue){super();this.value=value;}publicvoidsetLeft(Node3left){this.left=left;}publicvoidsetRight(Node3right){this.right=right;}@OverridepublicStringtoString(){return"Node3[value="+value+"]";}publicvoidpostOrder(){//递归对左子树进行前序遍历if(left!=null){left.postOrder();}//递归对右子树进行前序遍历if(right!=null){right.postOrder();}//输出当前节点System.out.println(this);}}(3)测试类BinaryTreeTest3:publicclassBinaryTreeTest3{privateNode3rootNode;publicstaticvoidmain(String[]args){BinaryTreeTest3test=newBinaryTreeTest3();test.createBinaryTree();test.postOrder();}//创建图1中的二叉树privatevoidcreateBinaryTree(){Node3[]nodes=newNode3[11];for(inti=1;i<=nodes.length;i++){nodes[i-1]=newNode3(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}//序遍历后privatevoidpostOrder(){if(rootNode!=null){System.out.println("二叉树的后序遍历~~");rootNode.postOrder();}else{System.out.println("ThisItisanemptytree");}}}程序运行结果如下：图片程序的输出和输出完全一样上图1中的后序遍历顺序。总结：如何判断是前序遍历还是中序遍历还是后序遍历，其实很简单，有规律。我们可以把主角看成是父节点。如果先输出父节点，则为前序遍历；如果先输出左子树，再输出父节点，则为中序遍历；如果最后输出了父节点，则为后续遍历。
