前序、中序、后序的含义
前序遍历： 先输出父节点，再遍历左子树，最后遍历右子树
中序遍历 ： 先遍历左子树，再输出父节点，最后遍历右子树
后序遍历 ： 先遍历左子树，再遍历右子树，最后输出父节点
如何区分呢？
看输出父节点的顺序 ，就可以确定是 前序、中序、后序
实例
我们先来分析下 将 下面的几个数 放到 二分搜索树中会是怎样的存放 。
注意我们这里用的是二分搜索树来演示二叉树的这个遍历，才会有中序遍历的那个排序的特征。
5 / \ 3 6 / \ \ 2 4 8
前序遍历： 5 、3、2、4、6、8
中序遍历： 2、3、4、5、6、8
后序遍历 ： 2、4、3、8、6、5
其实 ， 前序遍历比较常用。
观察中序遍历，可以看到是排序的 ，这个也很好理解。 毕竟是 左侧的都是小于父节点的，右侧都是大于父节点的。
后序遍历的适用场景，举个例子 为二分搜索树释放内存
前序遍历、中序遍历、后续遍历本质上一种深度遍历
Code （递归）
前序遍历
/** * * * @Title: preOrder * * @Description: 二分搜索树的前序遍历 * * * @return: void */ public void preOrder() { preOrder(root); } /** * * * @Title: preOrder * * @Description: 前序遍历以node为根的二分搜索树, 递归算法 * * @param node * * @return: void */ private void preOrder(Node node) { if (node == null) // 终止条件 return; System.out.print(node.e + "--"); // 先输出父节点 preOrder(node.left); // 再遍历左子树 preOrder(node.right); // 最后遍历又子树 }
中序遍历
/** * * * @Title: inOrder * * @Description: 二分搜索树的中序遍历 * * * @return: void */ public void inOrder() { inOrder(root); } /** * * * @Title: inOrder * * @Description: 中序遍历以node为根的二分搜索树, 递归算法 * * @param node * * @return: void */ private void inOrder(Node node) { if (node == null) // 终止条件 return; inOrder(node.left); System.out.println(node.e); inOrder(node.right); }
后序遍历
/** * * * @Title: postOrder * * @Description: 二分搜索树的后序遍历 * * * @return: void */ public void postOrder() { postOrder(root); } /** * * * @Title: postOrder * * @Description: 后序遍历以node为根的二分搜索树, 递归算法 * * @param node * * @return: void */ private void postOrder(Node node) { if (node == null) // 终止条件 return; postOrder(node.left); postOrder(node.right); System.out.println(node.e); }
测试
public static void main(String[] args) { BinarySearchTree<Integer> bst = new BinarySearchTree<>(); int[] nums = { 5, 3, 6, 8, 4, 2 }; for (int num : nums) { bst.add(num); } bst.preOrder(); System.out.println("============================"); bst.inOrder(); System.out.println("============================"); bst.postOrder(); }
Code (非递归)
不用递归也可以实现，我们要借助Stack来实现这个。 推荐使用递归的方式，代码更简洁。
这里把不用递归的代码也贴一下，供参考
/** * * * @Title: preOrderNR * * @Description: 二分搜索树的前序遍历 非递归的方式 栈是LIFO ,前序遍历（先处理左子树，后处理右子树） * ，需要先把右节点入栈，这样才能确保后处理 * * @return: void */ public void preOrderNR() { Stack<Node> stack = new Stack<>(); stack.push(root); // 把root入栈 while (!stack.isEmpty()) { Node currentNode = stack.pop(); System.out.println(currentNode.e); if (currentNode.right != null) { stack.push(currentNode.right); } if (currentNode.left != null) { stack.push(currentNode.left); } } }
