上篇博客介绍了构建一棵二叉树,但是并没有介绍如何遍历二叉树,一下,我们只介绍3三种遍历二叉树的形式,
分别是,前序遍历,中序遍历,后序遍历,因为我也是学习阶段,难免会有解释不清,或者理解有误的,欢迎指正
----------------------------------我是分割线------------------------------------
我们先定义一棵普通的二叉树,如下图
我们先说前序遍历吧!
前序遍历:通过递归进行遍历,如果二叉树为空,则操作返回,如果非空,否则从根结点开始,然后遍历左子树完左子树,在遍历右子树
前序遍历的结果是: ABDGHEICFJK 为什么会遍历出这种结果,请看上面对前序遍历的描述,先遍历左边,然后在遍历右边
JAVA代码如下:
//前序遍历 public static void preTraversal(Node node){ if(null!=node){ System.out.println(node.getData()); preTraversal(node.getLeft()); preTraversal(node.getRight()); return; } }
然后是中序遍历!
中序遍历:通过递归进行遍历,如果二叉树为空,则操作返回,如果非空,否则从根结点开始,中序遍历根结点的左子树,然后访问根结点,最后中序遍历右子树
前序遍历的结果是: GDHBEIACJFK 为什么会遍历出这种结果,请看上面对中序遍历的描述,先遍历左边,然后访问根结点,然后在遍历右边
JAVA代码如下:
//中序遍历 public static void inOrder(Node node){ if(null!=node){ inOrder(node.getLeft()); System.out.println(node.getData()); inOrder(node.getRight()); return; } }
最后是后序遍历!
后序遍历:通过递归进行遍历,如果二叉树为空,则操作返回,如果非空,否则从左到右,先叶子后结点的方式遍历访问左右子树,最后访问根结点
前序遍历的结果是: GHDIEBJKFCA 为什么会遍历出这种结果,请看上面对中序遍历的描述,从左到右,先叶子,后结点
JAVA代码如下:
//后序遍历 public static void postOrder(Node node){ if(null!=node){ postOrder(node.getLeft()); postOrder(node.getRight()); System.out.println(node.getData()); return; } }
以上就是二叉树的其中三种遍历方式,其中的差异性就在于递归调用的时候,对某个结点进行操作,
例如前序遍历,每次递归调用,都是先打印结点的data信息,然后是访问左叶子结点信息,又是打印结点信息,直到没有左叶子的时候,返回上层结点,然后调用右叶子,如此递归,就会出现前序遍历的结果
中序跟后序跟前序原理差不多,不同的在于什么时候打印结点信息而已,就给各位看官自己看了
到这,文章就结束了!
以上,均为本人个人理解,比较简单的理解,或许跟各位看官理解的有出入,欢迎指正交流
欢迎转载,请注明出处跟作者,谢谢!
