专栏首页Vegout二叉树遍历总结(先序||中序||后序||按层遍历||之字遍历&&递归||非递归)

二叉树遍历总结(先序||中序||后序||按层遍历||之字遍历&&递归||非递归)

先序遍历:8 6 5 7 10 9 11 后序遍历:5 7 6 9 11 10 8 中序遍历:5 6 7 8 9 10 11 按层遍历:8 6 10 5 7 9 11 之字遍历:8 10 6 5 7 9 11

先序遍历

递归
    public static void printBTPerRecursion(TreeNode root){
        if (root!=null){
            System.out.print(root.value+" ");
            printBTPerRecursion(root.left);
            printBTPerRecursion(root.right);
        }
    }
非递归
 public static void printBTPerUnrecursion(TreeNode node){
        while (node!=null||!stack.isEmpty()){
            if (node!=null){
                System.out.print(node.value+" ");
                stack.push(node);
                node = node.left;
            }
            else {
                node = stack.pop();
                node = node.right;
            }
        }
    }

中序遍历

递归
public static void printBTMidRecursion(TreeNode root){
        if (root!=null){
            printBTMidRecursion(root.left);
            System.out.print(root.value+" ");
            printBTMidRecursion(root.right);
        }
    }
非递归
 public static void printBTMidUnrecursion(TreeNode node){
        while (node!=null||!stack.isEmpty()){
            if (node!=null){
                stack.push(node);
                node = node.left;
            }else {
                TreeNode node1 = stack.pop();
                System.out.print(node1.value+" ");
                node = node1.right;
            }
        }
    }

后序遍历

递归
    public static void printBTBackRecursion(TreeNode root){
        if (root!=null){
            printBTBackRecursion(root.left);
            printBTBackRecursion(root.right);
            System.out.print(root.value+" ");
        }
    }
非递归()
//非递归后序遍历 参考自https://blog.csdn.net/zhuqiuhui/article/details/51319165
    public static void printBTBackUnrecursion(TreeNode node){
        if (node==null)return;
        TreeNode curNode;
        TreeNode lastVisitNode;
        curNode = node;
        lastVisitNode = null;
        //先找到最左节点
        while (curNode!=null){
            stack.push(curNode);
            curNode = curNode.left;
        }
        while (!stack.empty()){
            curNode = stack.pop();
            //如果此结点右节点不为空且没有被访问过,那么将它再次入栈,并顺着它的右节点再次入栈左节点
            if (curNode.right!=null&&curNode.right!=lastVisitNode){
                stack.push(curNode);
                curNode = curNode.right;
                while (curNode!=null){
                    stack.push(curNode);
                    curNode = curNode.left;
                }
            }else {
                System.out.print(curNode.value+" ");
                lastVisitNode = curNode;
            }
        }
    }

按层遍历(使用队列实现)

递归
public static void printLayerRecursion(TreeNode root) throws InterruptedException {
        System.out.print(root.value+" ");
        if (root.left!=null)queue.add(root.left);
        if (root.right!=null)queue.add(root.right);
        TreeNode treeNode = queue.poll();
        if (treeNode!=null)
        printLayerRecursion(treeNode);
    }
非递归
 public static void printLayerUnrecursion(TreeNode node){
        if (node==null)return;
        queue.add(node);
        while (!queue.isEmpty()){
            TreeNode node1 = queue.poll();
            System.out.print(node1.value+" ");
            if (node1.left!=null)queue.add(node1.left);
            if (node1.right!= null)queue.add(node1.right);
        }
    }

之字遍历

非递归(需要两个栈,两个栈交替装入每一层的结点,一个栈先装左节点再装右节点,另一个栈先装右节点再装左节点)
public static void printBTlikeZHI(TreeNode node){
        if (node==null)return;
        stack.push(node);
        int current = 0;
        int next = 1;
        while (!stack.empty()||!otherStack.isEmpty()){
            TreeNode node1 = (TreeNode) stacks[current].pop();
            System.out.print(node1.value+" ");
            if (current==0){
                if (node1.left!=null)stacks[next].push(node1.left);
                if(node1.right!=null)stacks[next].push(node1.right);

            }else {
                if (node1.right!=null)stacks[next].push(node1.right);
                if (node1.left!=null)stacks[next].push(node1.left);

            }
            if (stacks[current].empty()){
                current = 1-current;
                next = 1-next;
            }
        }
    }

本文分享自微信公众号 - Vegout(t10244201),作者:naget

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 计数排序

    计数排序和原来说过的几个排序算法有一个特别大的不同之处:它是一个不基于比较的排序算法。不管是快排,归并,还是堆排,它们都难以突破NlogN的运行时间下限,而计数...

    naget
  • JDK源码——Arrays.sort()的实现

    可见,Arrays并没有自己来实现排序,而是委托给了DualPivotQuicksort类。进入上边的sort方法

    naget
  • 浅谈java线程池(基于jdk1.8)

    多线程让程序世界丰富多彩,也让其错综复杂。对于线程的创建和销毁成了一笔不小的开销,为了减少这些开销,出现了线程池。线程池对线程进行管理,对于需要使用多线程的我们...

    naget
  • 3.1 选择结构和if语句

    闫小林
  • 【编程经验】表达式和语句及选择结构

    在C中,表达式代表值,而语句代表给计算机的指令。 表达式 表达式由运算符和操作数组成。最简单的表达式只是一个不带运算符的常量或者变量,例如12或者num。...

    编程范 源代码公司
  • 5.1 if语句

    C语言有两种选择语句,if语句和switch语句,if语句是用来实现两个分支的选择结构。

    闫小林
  • python基础知识——控制语句

    其中,raw_input()用于获取控制台的输入,由于raw_input()返回的是字符串,则在比较的时候必须使用int()转换,若是不想转换,可以直接使...

    zhaozhiyong
  • python基础知识——控制语句

    控制语句主要有条件语句和循环语句。 一、条件语句 1、if语句 格式 if 表达式: 语句1 else: 语句2 如下面的例子: ...

    zhaozhiyong
  • Python学习-if条件语句

    Python条件语句是通过一条或多条语句的执行结果(True或者False)来决定执行的代码块。

    用户2398817
  • 卫语句

    动机:条件表达式通常有2种表现形式。第一:所有分支都属于正常行为。第二:条件表达式提供的答案中只有一种是正常行为,其他都是不常见的情况。

    李郑

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动