1.前序遍历概述
前序遍历(VLR) 是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。
若二叉树为空则结束返回,否则:
(1)访问根结点。
(2)前序遍历左子树。
(3)前序遍历右子树 。
需要注意的是:遍历左右子树时仍然采用前序遍历方法。
2.二叉树
3.遍历过程
前序遍历首先访问根节点
前序遍历节点输出1
然后访问左子树2,遍历输出左子树当前节点
前序遍历节点输出1 2
然后左子树任然按照前序遍历的方法首先访问左子树4,左子树首先输出4,发现4为叶子节点,没有左子树和右子树,回到上一步指向左子树2
前序遍历节点输出1 2 4
左子树2根据前序遍历已经访问了根节点和左子树,接下来访问左子树2的右节点5(注意这里递归到4这个叶子节点后,会返回到2开始继续前序遍历,所以其实指针的指向顺序是4->2->5)
前序遍历节点输出1 2 4 5
1.当前5为叶子节点没有左子树和右子树,所以指针回到2节点
2.发现2节点已经输出,2的左子树和右子树也遍历完成,所以根据递归继续返回,指针从2回到1
3.发现1节点和左子树都已经遍历,根据前序遍历的规则,最后遍历右子树,指针向右子树移动指向3节点
前序遍历节点输出1 2 4 5 3
之后分别遍历节点3的左节点和右节点
前序遍历节点输出1 2 4 5 3 6 7
4.代码实现
@Testpublic void testBinaryTree(){int[] array = {1,2,3,4,5,6,7};//1 2 4 5 3 6 7 前序 4 2 5 1 6 3 7 中序 4 5 2 6 7 3 1 后序//创建一个ArrBinaryTreebinaryTree binaryTree = new binaryTree(array);binaryTree.preNode(0);System.out.println();binaryTree.infixNode(0);System.out.println();binaryTree.PostNode(0);}/*** 树的前序中序后序遍历*/static class binaryTree{private int[] arr;public binaryTree(int[] arr) {this.arr = arr;}public int[] getArr() {return arr;}public void setArr(int[] arr) {this.arr = arr;}/**** 前序遍历* 1.输出root节点* 2.输出左子节点* 3.输出右子节点*/public void preNode(int index){if (arr.length==0||arr==null){System.out.println("数组为空,无法遍历");}// 输出当前节点System.out.print(arr[index]+" ");// 输出当前左子节点if (index*2+1<arr.length){preNode(index*2+1);}// 输出当前右子节点if (index*2+1<arr.length){preNode(index*2+2);}}/**** 中序遍历* 1.输出左子节点* 2.输出root节点* 3.输出右子节点*/public void infixNode(int index){if (arr.length==0||arr==null){System.out.println("数组为空,无法遍历");}// 输出当前左子节点if (index*2+1<arr.length){infixNode(index*2+1);}// 输出当前节点System.out.print(arr[index]+" ");// 输出当前右子节点if (index*2+1<arr.length){infixNode(index*2+2);}}/**** 后序遍历* 1.输出左子节点* 2.输出root节点* 3.输出右子节点*/public void PostNode(int index){if (arr.length==0||arr==null){System.out.println("数组为空,无法遍历");}// 输出当前左子节点if (index*2+1<arr.length){PostNode(index*2+1);}// 输出当前右子节点if (index*2+1<arr.length){PostNode(index*2+2);}// 输出当前节点System.out.print(arr[index]+" ");}}
输出前序中序后序遍历
如果觉得《二叉树的前序中序后序遍历java代码实现》对你有帮助,请点赞、收藏,并留下你的观点哦!