数据结构|二叉树的三种遍历方式，你掌握了几种？

目录

1、遍历方式

2、前序遍历

3、中序遍历

1、遍历方式

学习二叉树的结构，最简单的方式就是遍历二叉树。遍历二叉树就是通过某条线路对二叉树的各个结点进行一次访问，访问的方法有三种分为前序遍历、中序遍历、后续遍历，层序遍历它们的遍历顺序如下所示：

• 前序遍历:根节点=》根节点的左子树=》根节点的右子树
• 中序遍历:根节点的左节点=》根节点=》根节点的右子树
• 后续遍历:根节点的左节点=》根节点的右节点=》根节点

在二叉树的遍历中，遍历的开始是从头节点开始的遍历的结束也是从头节点结束的。

---

有一个二叉树，它有六个节点ABCDEF其值为123456。对应的结构为：

• A为根节点时，A的左子树是D，A的右子树是E，A的值为1。
• B为根节点时，B的左子树是D，B的右子树是E，B的值为2。
• C为根节点时，C的左子树是null，C的右子树是F，C的值为3。
• D为根节点时，D的左子树是null，F的右子树是null，的值为4。
• E为根节点时，E的左子树是null，F的右子树是null，的值为5。
• F为根节点时，F的左子树是null，F的右子树是null，的值为6。

本期博文所演练的遍历方式，均以上图中的二叉树进行展示。

---

2、前序遍历

前序遍历，我们在上方已经了解到了它的遍历顺序为：根节点=》根节点的左子树=》根节点的右子树。因此前序遍历上述的定义好的二叉树的顺序应为：ABDECF得到的值也应该为124536。具体实现方式看下方讲解：

第一步，获取根节点A。判断A节点是否有左子树。有则往下一个左子树遍历。没有则遍历右子树，右子树也没有则返回父节点。如果无父节点则程序结束！

此步骤往A的左子树进行遍历，首先获取A节点，发现A存在左子树，则往下遍历A的左子树节点。此时遍历到节点为:A、元素为:1。

---

第二步，来到B节点，获取B节点。判断B节点是否有左子树。有则往下一个左子树遍历。没有则遍历右子树，右子树也没有则返回父节点。如果无父节点则程序结束！

此步骤往B的左子树进行遍历，发现B存在左子树，则往下遍历B的左子树节点。此时遍历到的节点为AB、元素为:12。

 

---

第三步，来到D节点，获取D节点。然后判断D节点是否有左子树有则往下一个节点遍历。没有则遍历右子树，右子树也没有则返回父节点。

此时发现D没有左子树，遍历D的右子树发现右子树也没有，返回到B节点，并且往B节点的右子树进行遍历。 此时遍历到的节点为:ABD、元素为:124。

---

第四步，来到E节点，获取E节点。判断E是否有左子树。有则往下一个节点遍历。没有则遍历右子树，右子树也没有则返回父节点。

此时，发现E节点没有左右子树，则返回到B节点，B节点再返回到A节点，A节点再遍历到C节点，此时遍历到的节点为:ABDE、元素为:1245。

---

第五步，来到C节点，获取C节点。判断C是否有左子树。有则往下一个节点遍历。没有则遍历右子树，右子树也没有则返回父节点。

此时发现，C节点没有左子树，则访问C节点右子树F节点获取F节点的根节点。往F的左子树进行遍历，此时获取到的节点为:ABDEC，元素为:12453。

---

最后一步，来到F节点，获取F节点。F节点没有左右子树，返回F节点的父节点C节点，C节点再返回到C的父节点A节点。最后发现A没有父节点，程序结束。此时获取到的节点为:ABDECF，元素为:124536。

---

以上就是对前序遍历步骤的一个详细讲解，下面我们来看代码的实现： 

//MyBinaryTree.java文件下
public class MyBinaryTree {//静态内部类BinaryTreestatic class BinaryTree {public int val;public BinaryTree left;public BinaryTree right;public BinaryTree(int val) {this.val = val;}}//根节点public BinaryTree root;//创建一个二叉树public void initBinaryTree() {BinaryTree A = new BinaryTree(1);BinaryTree B = new BinaryTree(2);BinaryTree C = new BinaryTree(3);BinaryTree D = new BinaryTree(4);BinaryTree E = new BinaryTree(5);BinaryTree F = new BinaryTree(6);A.left = B;A.right = C;B.left = D;B.right = E;C.right = F;root = A;}//前序遍历二叉树public void preOrder(BinaryTree tree) {if( tree == null) {return;}//节点的元素System.out.print(tree.val+" ");//节点的左子树preOrder(tree.left);//节点的右子树preOrder(tree.right);}
}//Test.java文件下
public class Test {public static void main(String[] args) {MyBinaryTree myBinaryTree = new MyBinaryTree();myBinaryTree.initBinaryTree();myBinaryTree.preOrder(myBinaryTree.root);}
}

运行后输出：  

我们可以运行后的结果与上述演练的最终结果是一致的。通过程序我们也不难看出二叉树的遍历是一种递归思想，它的终止条件就是节点本身不为空。另外细心的朋友可以发现前序遍历得到的首结果就是这个二叉树的头节点，因为头节点是第一个被遍历的。 

---

3、中序遍历

中序遍历的顺序为：根节点的左节点=》根节点=》根节点的右节点。因此，中序遍历本期二叉树得到的根节点顺序为：DBEACF、根节点元素为：425136。

第一步，遍历A的左节点。如果A节点有左节点往A的左节点遍历，不存在则获取A节点，并往A节点的右节点遍历，如果右节点也为空则返回父节点。此时，遍历到了B节点。以下的每个节点也是同此步骤进行的。

---

第二步，遍历来到B节点。判断B节点的左节点不为空。遍历来到D节点，判断D节点的左子树为空，获取D节点，访问D的右子树为空返回父节点B，获取B节点的根节点。此时遍历到的节点为：DB，元素为：42。

---

第三步，遍历来到E节点。E节点的左子树为空，获取E节点，右子树也是空返回父节点B，B节点返回父节点A，获取A节点的根节点。此时遍历到的节点为：DBEA，元素为：4251。

---

第四步，遍历来到C节点。C节点的左子树为空，获取C节点，判断C节点的右子树不为空。遍历到F节点，此时遍历到的节点为：DBEAC，元素为：42513。

---

第五步，遍历来到F节点。F节点的左子树为空，获取F节点，F节点的右子树也为空返回父节点C，C节点返回父节点A，A节点没有父节点，程序结束。此时遍历到的节点为：DBEACF，元素为：425136。程序结束。

---

中序遍历，我们只需将上述代码中的preOrder方法中的访问节点的根节点位置稍微改动一下，其余代码不变。 

    
//中序遍历二叉树
public void inOrder(BinaryTree tree) {if( tree == null) {return;}//节点的左子树preOrder(tree.left);//节点的元素System.out.print(tree.val+" ");//节点的右子树preOrder(tree.right);}

 运行后输出:

通过上述结果，我们可以看到输出的结果与上方展示的结果是一致。细心的朋友可以发现，当我们中序遍历后头节点的左侧都是左子树，头节点的右侧都是右子树。在上方代码中1的左侧为425，1的右侧为36，正好与我们的二叉树一致。因此，当我们知道了一个二叉树的头节点是谁后可以通过中序遍历推出这个二叉树的左、右则的树。 

---

4、后序遍历

后序遍历的步骤为：根节点的左节点=》根节点的右节点=》根节点，在本篇示例二叉树中对应的遍历节点顺序为：DEBFCA，节点元素为452631。

在上文中，前序遍历与后序遍历我给大家展示了流程图以及实现步骤，其实后序遍历也是一样的按照左节点、右节点、根节点的遍历顺序去遍历，在此博主就不多讲解了，大家可以自己尝试去画图。

后序遍历二叉树的代码，我们也是将preOrder方法中的根节点位置互换一下即可：

//后序遍历二叉树    
public void postOrder(BinaryTree tree) {if( tree == null) {return;}//节点的左子树preOrder(tree.left);//节点的右子树preOrder(tree.right);//节点的元素System.out.print(tree.val+" ");}

运行后输出：

通过运行结果可以看到与上方遍历得到的结果是一致的。通过观察，我们也可以知道。知道了一个二叉树的后序遍历，就能得到头节点，因为后序遍历的最后一个数据就是我们的头节点。

---

当我们知道一个二叉树的前序遍历或后续遍历结果与中序遍历结果时，就能轻易的推出这个二叉树的全貌。

如一个二叉树的前序遍历结果为：ABDECF，中序遍历结果为：DBEACF。则这个二叉树的头节点为：A，左侧子树为：DBE、右侧子树为CF。因此可以推出这个二叉树的全貌为：

当然，知道一个二叉树的中序遍历与后序遍历也能很轻松的推出这个二叉树，但知道前序遍历和后序遍历却不能推出这个二叉树，因为通过这两个遍历方式我们不能得到左侧、右侧的子树是什么。

---

本期博客到这里就结束了，大家下来了可以自己去画图理解不懂之处或者私信博主、评论留言都可以。感谢你的阅读，我们下期再见！