江苏龙网

  1. 主页 > 生活百科 > >

二叉树的遍历-递归和非递归

递归


二叉树的遍历-递归和非递归

文章插图
盗图
前言
最近准备面试 ,复习了一下数据结构 中的二叉树,整理了二叉树的前序、中序、后序、深度和广度遍历以及递归和非递归实现方法，如有好的方案大家可以一起讨论 。
前序遍历
先遍历根节点，然后再遍历左子树，最后再遍历右子树
JAVA 示例：
/** * 前序遍历 */public void previousTraverse() { if (Objects.nonNull(root)) { doPreviousTraverse(root); }}private void doPreviousTraverse(Node root) { //先遍历根节点 System.out.println(root.getData()); if (Objects.nonNull(root.getLeft())) { doPreviousTraverse(root.getLeft()); } if (Objects.nonNull(root.getRight())) { doPreviousTraverse(root.getRight()); }}【二叉树的遍历-递归和非递归】中序遍历
思路：先遍历左子树，然后遍历根节点，最后遍历右子树java 示例
/** * 中序遍历 */public void middleTraverse() { if (Objects.nonNull(root)) { doMiddleTraverse(root); }}private void doMiddleTraverse(Node root) { //先遍历左节点 if (Objects.nonNull(root.getLeft())) { doMiddleTraverse(root.getLeft()); } //遍历根节点 System.out.println(root.getData()); //遍历右节点 if (Objects.nonNull(root.getRight())) { doMiddleTraverse(root.getRight()); }}后序遍历
思路：先遍历左子树，然后遍历右子树，再遍历根节点java示例
/** * 后序遍历 */public void afterTraverse() { if (Objects.nonNull(root)) { doAfterTraverse(root); }}private void doAfterTraverse(Node root) { //先遍历左节点 if (Objects.nonNull(root.getLeft())) { doAfterTraverse(root.getLeft()); } // 遍历右节点 if (Objects.nonNull(root.getRight())) { doAfterTraverse(root.getRight()); } //遍历根节点 System.out.println(root.getData());}广度遍历
思路：使用队列来辅助实现，首先把根节点放到队列里，然后弹出 根节点 打印根节 点的値，判断左子节点是否为空，不为空放入队列，判断右节点是否为空，不为空 放入队列，一次重复上述步骤，找到队列里没有数据结束，打印出来的序列则为该 树的广度遍历 。java 示例：
/** * 广度遍历 */public void broadCastTraverse() { if (Objects.nonNull(root)) { //定义一个存放节点的队列 LinkedList<Node> nodes = new LinkedList<>(); nodes.addLast(root); while (!nodes.isEmpty()) { Node node = nodes.removeFirst(); System.out.println(node.getData()); if (Objects.nonNull(node.getLeft())) { nodes.addLast(node.getLeft()); } if (Objects.nonNull(node.getRight())) { nodes.addLast(node.getRight()); } } }}深度遍历 即先序遍历 若不采用递归方式则序借助栈的后进先出
先将根节点事先放到栈中然后执行下面的步骤: 1.从栈顶弹出节点 2.打印节点的値 3.判断该节点的右子节点是否为空，若不为空则将右子节点放入栈中 4.判断该节点的左子节点是否为空，若不为空则将左子节点放入栈中 重复上述步骤，直到栈为空java 示例
/** * 深度遍历 即先序遍历 若不采用递归方式则序借助栈的后进先出 * 先将根节点事先放到栈中然后执行下面的步骤: * 1.从栈顶弹出节点 * 2.打印节点的値 * 3.判断该节点的右子节点是否为空，若不为空则将右子节点放入栈中 * 4.判断该节点的左子节点是否为空，若不为空则将左子节点放入栈中 * 重复上述步骤，直到栈为空 */public void deepTraverse() { if (Objects.nonNull(root)) { Stack<Node> nodes = new Stack<>(); nodes.push(root); while (!nodes.isEmpty()) { Node node = nodes.pop(); System.out.println(node.getData()); if (Objects.nonNull(node.getRight())) { nodes.push(node.getRight()); } if (Objects.nonNull(node.getLeft())) { nodes.push(node.getLeft()); } } }}中序遍历 非递归遍历 借用栈来实现
思路：1.首先将根节点 入栈2.依次将左节点入栈直到左节点为空3.弹出栈顶打印判断是否有右节点，若有则入栈 java 示例
/** * Non-recursive traversal * * 中序遍历 非递归遍历 借用栈来实现 * 思路： * 1.首先将根节点 入栈 * 2.依次将左节点入栈直到左节点为空 * 3.弹出栈顶打印判断是否有右节点，若有则入栈 */public void nonRecursiveTraverse() { if (Objects.nonNull(root)) { Node node = root; Stack<Node> nodes = new Stack<>(); while (Objects.nonNull(node) || !nodes.isEmpty()) { if (Objects.nonNull(node)) { //将根节点入栈 nodes.push(node); node = node.getLeft(); } else { Node someLeft = nodes.pop(); System.out.println(someLeft.getData()); if (Objects.nonNull(someLeft.getRight())) { node = someLeft.getRight(); } } } }}完整源码位置
https://github.com/241600489/homeworks/tree/master/src/main/java/zym/sort/tree/binary
后记
看完之后如果觉得有用麻烦点个赞加个关注哦


推荐阅读


上一篇：熬中药锅为什么裂 熬药锅碎了是不是不吉利

下一篇：Chrome 调试工具的一些高阶功能