数据结构—二叉树的4种遍历方式详解以及Java代码的完整演示

Answer 1

二叉树的遍历（traversing binary tree）是指从根节点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

本文介绍了4种二叉树的遍历方法，分别是前序、中序、后续、层序遍历，并且每种方法均提供了详尽的Java语言的代码演示，在最后还介绍了遍历结果推导的方法。

1 概述

二叉树的遍历（traversing binary tree）是指从根节点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

访问其实是要根据实际的需要来确定具体做什么，比如对每个结点进行相关计算，输出打印等，它算作是一个抽象操作。在这里我们可以简单地假定访问就是输出结点的数据信息。

二叉树的遍历次序不同于线性结构，最多也就是从头至尾、循环、双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择。因此遍历的方式也有很多种，主要的方式有先序遍历、中序遍历、后序遍历、层序遍历。

关于二叉树的知识，如果不是很了解，可以看这篇文章：二叉树的入门以及Java实现案例详解。

本文将以下面的二叉树来作为样例进行遍历：

2 构建二叉树

首先，构建出上图中二叉树，下面是二叉树的简单链式存储结构的实现。二叉树的实现在：二叉树的入门以及Java实现案例详解中有讲解。

/***二叉树的链式存储结构的简单实现*/publicclassLinkedBinaryTree<E>{/***外部保存根节点的引用*/privateBinaryTreeNode<E>root;/***树节点的数量*/privateintsize;/***内部节点对象**@param<E>数据类型*/publicstaticclassBinaryTreeNode<E>{//数据域Edata;//左子节点BinaryTreeNode<E>left;//右子节点BinaryTreeNode<E>right;publicBinaryTreeNode(Edata){this.data=data;}publicBinaryTreeNode(Edata,BinaryTreeNode<E>left,BinaryTreeNode<E>right){this.data=data;this.left=left;this.right=right;}@OverridepublicStringtoString(){returndata.toString();}/*@OverridepublicStringtoString(){return"BinaryTreeNode{"+"data="+data+'}';}*/}/***空构造器*/publicLinkedBinaryTree(){}/***构造器,初始化root节点**@paramroot根节点数据*/publicLinkedBinaryTree(Eroot){checkNullData(root);this.root=newBinaryTreeNode<>(root);size++;}/***添加子节点**@paramparent父节点的引用*@paramdata节点数据*@paramleft是否是左子节点,true是;false否*/publicBinaryTreeNode<E>addChild(BinaryTreeNode<E>parent,Edata,booleanleft){checkNullParent(parent);checkNullData(data);BinaryTreeNode<E>node=newBinaryTreeNode<>(data);if(left){if(parent.left!=null){thrownewIllegalStateException("该父节点已经存在左子节点,添加失败");}parent.left=node;}else{if(parent.right!=null){thrownewIllegalStateException("该父节点已经存在右子节点,添加失败");}parent.right=node;}size++;returnnode;}/***是否是空树**@returntrue是;false否*/publicbooleanisEmpty(){returnsize==0;}/***获取根节点**@return根节点;或者null--表示空树*/publicBinaryTreeNode<E>getRoot(){returnroot;}/***获取左子节点**@paramparent父节点引用*@return左子节点或者null--表示没有左子节点*/publicBinaryTreeNode<E>getLeft(BinaryTreeNode<E>parent){returnparent==null?null:parent.left;}/***获取右子节点**@paramparent父节点引用*@return右子节点或者null--表示没有右子节点*/publicBinaryTreeNode<E>getRight(BinaryTreeNode<E>parent){returnparent==null?null:parent.right;}/***数据判null**@paramdata添加的数据*/privatevoidcheckNullData(Edata){if(data==null){thrownewNullPointerException("数据不允许为null");}}/***检查父节点是否为null**@paramparent父节点引用*/privatevoidcheckNullParent(BinaryTreeNode<E>parent){if(parent==null){thrownewNoSuchElementException("父节点不能为null");}}}2.1 添加节点数据publicclassTreeTest{/***构建二叉树,添加根节点r*/LinkedBinaryTree<String>integerLinkedBinaryTree=newLinkedBinaryTree<>("r");@BeforepublicvoidbuildTree(){/*构建二叉树*/LinkedBinaryTree.BinaryTreeNode<String>r=integerLinkedBinaryTree.getRoot();//添加r根节点的左子结点aLinkedBinaryTree.BinaryTreeNode<String>a=integerLinkedBinaryTree.addChild(r,"a",true);//添加r根节点的右子结点bLinkedBinaryTree.BinaryTreeNode<String>b=integerLinkedBinaryTree.addChild(r,"b",false);//添加a节点的左子结点cLinkedBinaryTree.BinaryTreeNode<String>c=integerLinkedBinaryTree.addChild(a,"c",true);//添加a节点的右子结点dLinkedBinaryTree.BinaryTreeNode<String>d=integerLinkedBinaryTree.addChild(a,"d",false);//添加b节点的左子结点eLinkedBinaryTree.BinaryTreeNode<String>e=integerLinkedBinaryTree.addChild(b,"e",true);//添加b节点的右子结点fLinkedBinaryTree.BinaryTreeNode<String>f=integerLinkedBinaryTree.addChild(b,"f",false);//添加c节点的左子结点gLinkedBinaryTree.BinaryTreeNode<String>g=integerLinkedBinaryTree.addChild(c,"g",true);//添加c节点的右子结点hLinkedBinaryTree.BinaryTreeNode<String>h=integerLinkedBinaryTree.addChild(c,"h",false);//添加d节点的左子结点iLinkedBinaryTree.BinaryTreeNode<String>i=integerLinkedBinaryTree.addChild(d,"i",true);//添加f节点的左子结点jLinkedBinaryTree.BinaryTreeNode<String>j=integerLinkedBinaryTree.addChild(f,"j",true);}}3 先序遍历 preorder traversal3.1 先序遍历的介绍

规则是：若二叉树为空，则空操作返回；否则，从根节点开始，先遍历根，然后是左子树，最后遍历右子树；对于子树，同样从子树根开始，先遍历根，然后是左子树，最后遍历右子树。采用了递归的思想。

先序遍历中，对节点的遍历工作，是在对该节点的儿子节点的遍历之前进行遍历的。这也就是“先序”的得来。

先序遍历也叫前序遍历。

从r根节点开始，其遍历流程如下：

3.2 先序遍历的简单实现

以下代码添加到LinkedBinaryTree类中。

/***保存遍历出来的节点数据*/ThreadLocal<StringBuilder>threadLocal=ThreadLocal.withInitial(StringBuilder::new);/***先序遍历,提供给外部使用的api**@return遍历的数据*/publicStringtoPreorderTraversalString(){//如果是空树,直接返回空if(isEmpty()){returnnull;}//从根节点开始递归preorderTraversal(root);//获取遍历结果Strings1=threadLocal.get().toString();threadLocal.remove();returns1.substring(0,s1.length()-3);}/***先序遍历内部使用的递归遍历方法**@paramroot节点,从根节点开始*/privatevoidpreorderTraversal(BinaryTreeNode<E>root){//添加数节点threadLocal.get().append(root).append("-->");//获取节点的左子节点BinaryTreeNode<E>left=getLeft(root);if(left!=null){//如果左子节点不为null,则继续递归遍历该左子节点preorderTraversal(left);}//获取节点的右子节点BinaryTreeNode<E>right=getRight(root);if(right!=null){//如果右子节点不为null,则继续递归遍历该右子节点preorderTraversal(right);}}3.2.1 测试/***先序遍历*/@TestpublicvoidpreorderTraversal(){Strings=integerLinkedBinaryTree.toPreorderTraversalString();System.out.println(s);}

查看输出：

r-->a-->c-->g-->h-->d-->i-->b-->e-->f-->j

确实图中的遍历顺序一致。

4 中序遍历 inorder traversal4.1 中序遍历的介绍

规则是：若树为空，则空操作返回；否则，从根节点开始，先遍历根结点的左子树，然后是访问根结点，最后遍历右子树；对于子树，同样，先遍历子树根节点的左子树，然后是访问子树根结点，最后遍历右子树。采用了递归的思想。

中序遍历中，对节点的遍历工作，是在对该节点的左儿子节点的遍历之后、右儿子节点的遍历之前进行遍历的。这也就是“中序”的得来。

对图中的树采用中序遍历，从r根节点开始，顺序如下：

4.2 中序遍历的简单实现/***中序遍历,提供给外部使用的api**@return遍历的数据*/publicStringtoInorderTraversalString(){//如果是空树,直接返回空if(isEmpty()){returnnull;}//从根节点开始递归inorderTraversal(root);//获取遍历结果Strings1=threadLocal.get().toString();threadLocal.remove();returns1.substring(0,s1.length()-3);}/***中序遍历内部使用的递归遍历方法**@paramroot节点,从根节点开始*/privatevoidinorderTraversal(BinaryTreeNode<E>root){BinaryTreeNode<E>left=getLeft(root);if(left!=null){//如果左子节点不为null,则继续递归遍历该左子节点inorderTraversal(left);}//添加数据节点threadLocal.get().append(root).append("-->");//获取节点的右子节点BinaryTreeNode<E>right=getRight(root);if(right!=null){//如果右子节点不为null,则继续递归遍历该右子节点inorderTraversal(right);}}4.2.1 测试/***中序遍历*/@TestpublicvoidinorderTraversal(){Strings=integerLinkedBinaryTree.toInorderTraversalString();System.out.println(s);}

查看输出：

g-->c-->h-->a-->i-->d-->r-->e-->b-->j-->f

确实图中的遍历顺序一致。

5 后序遍历 postorder traversal5.1 后序遍历的介绍

规则是：若树为空，则空操作返回；否则，从根节点开始，先遍历根结点的左子树，然后是遍历右子树，最后遍历根结点；对于子树，同样，先遍历子树根节点的左子树，然后是遍历右子树，最后遍历子树根结点。采用了递归的思想。

后序遍历中，对节点的遍历工作，是在对该节点的儿子节点的遍历之后进行遍历的。这也就是“后序”的得来。

对图中的树采用后序遍历，从r根节点开始，顺序如下：

5.2 后序遍历的简单实现/***后序遍历,提供给外部使用的api**@return遍历的数据*/publicStringtoPostorderTraversalString(){//如果是空树,直接返回空if(isEmpty()){returnnull;}//从根节点开始递归postorderTraversal(root);//获取遍历结果Strings1=threadLocal.get().toString();threadLocal.remove();returns1.substring(0,s1.length()-3);}/***后序遍历内部使用的递归遍历方法**@paramroot节点,从根节点开始*/privatevoidpostorderTraversal(BinaryTreeNode<E>root){BinaryTreeNode<E>left=getLeft(root);if(left!=null){//如果左子节点不为null,则继续递归遍历该左子节点postorderTraversal(left);}//获取节点的右子节点BinaryTreeNode<E>right=getRight(root);if(right!=null){//如果右子节点不为null,则继续递归遍历该右子节点postorderTraversal(right);}//添加数据节点threadLocal.get().append(root).append("-->");}5.2.1 测试/***后序遍历*/@TestpublicvoidpostorderTraversal(){Strings=integerLinkedBinaryTree.toPostorderTraversalString();System.out.println(s);}

查看输出：

g-->h-->c-->i-->d-->a-->e-->j-->f-->b-->r

确实图中的遍历顺序一致。

6 层序遍历 level traversal6.1 层序遍历的介绍

规则是：若树为空，则空操作返回；否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。 层序遍历中，对节点的遍历工作，上层节点的遍历先于下层节点的遍历。这也就是“层序”的得来。

对图中的树采用层序遍历，从r根节点开始，顺序如下：

6.2 层序遍历的简单实现/***层序遍历,提供给外部使用的api**@return遍历的数据*/publicStringtoLevelTraversalString(){//如果是空树,直接返回空if(isEmpty()){returnnull;}//从根节点开始遍历,借用队列levelTraversal(root);//获取遍历结果Strings1=threadLocal.get().toString();threadLocal.remove();returns1.substring(0,s1.length()-3);}/***层序遍历内部使用的借用了队列**@paramroot节点,从根节点开始*/privatevoidlevelTraversal(BinaryTreeNode<E>root){Queue<BinaryTreeNode<E>>q=newLinkedList<>();q.add(root);while(!q.isEmpty()){BinaryTreeNode<E>nowNode=q.poll();//添加数据节点threadLocal.get().append(nowNode.data).append("-->");if(nowNode.left!=null){//如果左子节点不为null,则将子节点加入队列q.add(nowNode.left);}if(nowNode.right!=null){//如果右子节点不为null,则将子节点加入队列q.add(nowNode.right);}}}6.2.1 测试/***层序遍历*/@TestpublicvoidlevelTraversal(){Strings=integerLinkedBinaryTree.toLevelTraversalString();System.out.println(s);}

查看输出：

r-->a-->b-->c-->d-->e-->f-->g-->h-->i-->j

确实图中的遍历顺序一致。

7 遍历结果推导

题目：已知一棵二叉树的前序遍历序列为r-->a-->c-->h-->d-->i-->b-->e-->j-->k-->f，中序遍历序列为c-->h-->a-->d-->i-->r-->e-->k-->j-->b-->f，请问这棵二叉树的后序遍历结果是多少？

这样的题目常出现在面试中，这个原理其实并不是很复杂，并且有一定的规律性。下面一起来推导。

7.1 寻找根节点

找到前序遍历的第1个字符：r，可知r是根节点；

再找到中序遍历中的根节点r的位置，r的左边c-->h-->a-->d-->i，这就是最大的左子树Ⅰ，e-->k-->j-->b-->f就是最大的右子树Ⅱ。

7.2 推导左子树

找到前序遍历的第2个字符：a，然后在中序遍历的子树Ⅰ中也能找到节点a，可知a是r根节点的左子节点，也是左子树Ⅰ的根节点，；那么可以推导出来，左子树Ⅰ还具有左子树Ⅲ：c-->h和右子树Ⅳ：d-->i

找到前序遍历的第3、4个字符：c-->h，可知，c作为子树Ⅰ的左子结点，对比中顺序遍历顺序c-->h，可知h是c节点的右子结点；

找到前序遍历的第5、6个字符：d-->i，可知，d作为子树Ⅰ的右子结点，对比中顺序遍历顺序d-->i，可知 i是d节点的右子节点；

到此可以推导出最大的左子树的数据结构如下：

下面推导右子树。

7.3 推导右子树

右子树Ⅱ的前序遍历节点就是排除左子树和根节点剩下的节点：b-->e-->j-->k-->f，中序遍历为e-->k-->j-->b-->f

前序遍历的第一个节点是b，可以b是右子树Ⅱ的根节点；

在中序遍历中b节点的左边是e-->k-->j，右边是f。可以f是节点b的右子结点，并且是叶子节点；这样还剩下最后的左子树Ⅴ；<