二叉树的前、中、后遍历(递归/非递归)

二叉树的遍历

二叉树的前序遍历

访问根结点,先序遍历左子树,先序遍历右子树

遍历基本步骤为先根结点,然后左子树,然后右子树, 需要注意的是这个遍历需要类似于递归,在访问完A以后,需要去访问B,这时,需要把B当做一个根结点,下一次应该去访问D而不是C,只到访问到G即叶子节点以后才会递归的往回访问,所有节点都可以看作为父节点,叶子节点可以看做两个孩子为空的父节点

二叉树的中序遍历

中序遍历左子树,访问根结点,中序遍历右子树

二叉树的后续遍历

后续遍历左子树,后续遍历右子树,访问根结点。

后选遍历为先遍历左子树,若其节点有左子树,则会往下递归找到最后一个左子树开始,然后遍历右子树,如果右子树有子节点,将会按照前面的方法进行遍历。

建立二叉树

    public void buildTree(Node node) {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        System.out.println(str);
        if ("#".equals(str)) {
            node = null;
        } else {
            node.data = str;
            buildTree(node.left = new Node(""));
            buildTree(node.right = new Node(""));
        }

    }

上图应输入:ABDG###EH###C#F## (#代表空节点)

二叉树的前、中、后遍历(递归遍历)

存储结构

class Node {
    public Node left;
    public Node right;
    public String data;

    public Node(String data) {
        this.left = null;
        this.right = null;
        this.data = data;
    }

}

二叉树的前序遍历(递归)

    public void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.data);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

二叉树的中序遍历(递归)

    public void postOrder(Node node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.data);
        }
       

    }

二叉树的后续遍历(递归)

    public void inOrder(Node node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.data);
            inOrder(node.right);
        }
       

    }

二叉树的非递归实现

因为当遍历过根节点之后还要回来,所以必须将其存起来。考虑到后进先出的特点,选用栈存储。数量确定,以顺序栈存储。

前序遍历

    // 需要将访问过的节点都记录下来,最后取出来在访问右子树
    public void preOrder2(Node node) { // 通过栈来实现
        Stack<Node> nodeS = new Stack<>();
        if (node == null) {
            System.out.println("数据错误");
        } else {
            while (!nodeS.isEmpty() || node != null) {
                while (node != null) {
                    System.out.print(node.data); // 访问根结点
                    nodeS.push(node);
                    node = node.left;
                }
                node = nodeS.pop();
                node = node.right;
            }
        }
    }

中序遍历

    public void postOrder2(Node node) {
        Stack<Node> nodeS = new Stack<>();
        if (node == null) {
            System.out.println("数据错误");
        } else {
            while (!nodeS.isEmpty() || node != null) {
                while (node != null) {
                    nodeS.push(node);
                    node = node.left;
                }

                node = nodeS.pop();
                System.out.print(node.data);
                node = node.right;
            }
        }
    }

后序遍历

后序遍历的难点在于:需要判断上次访问的节点是位于左子树,还是右子树。若是位于左子树,则需跳过根节点,先进入右子树,再回头访问根节点;若是位于右子树,则直接访问根节点,这里解决方式是设置一个辅助栈用来标志当前节点的状态。

  // 所以设置一个辅助栈   里面存放对应节点的状态
    public void inOrder2(Node node) {
        Stack<Node> nodeS = new Stack<>(); 
        Stack<Boolean> tagS = new Stack<>();  // 辅助栈
        boolean tag = false;
        while (!nodeS.isEmpty() || node != null) {
            while (node != null) {  
                nodeS.push(node);
                tagS.push(false);   // 初始化,false代表第一次访问
                node = node.left;
            }
            tag = tagS.pop();  // 先将节点对应的标志位出栈
            if (tag) {  // 判断,如果是true 代表第二次访问, 则出栈并且访问
                node = nodeS.pop();
                System.out.print(node.data);
                node = null;
            } else {  // false, 则是第一次访问,需要访问右子树
                tagS.push(true);  // 则把标志位改为true,然后将标志压入栈中(上面标志位出栈了)
                node = nodeS.lastElement();  // 获取到栈顶元素
                node = node.right;  // 右子树
            }
        }
    }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Bingo的深度学习杂货店

Q198 House Robber

You are a professional robber planning to rob houses along a street. Each house ...

2695
来自专栏desperate633

LintCode 单词切分题目分析

给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

662
来自专栏Play & Scala 技术分享

酷炫的一行代码 - Scala就是这么任性!

3567
来自专栏用户2442861的专栏

异或的应用 及剑指offer 面试 40 数组中只出现一次的数字

转载请注明出处:http://blog.csdn.net/ns_code/article/details/27568975

982
来自专栏武培轩的专栏

剑指Offer-二叉树的下一个结点

题目描述 给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。 思路 分析二叉...

2465
来自专栏编程

2017余额不足,Python来充值:迭代和生成器

时光虽然脚步轻轻,但它透过2018却悄然露出了狐狸尾巴,岁月的时钟显示2017已然余额不足。 怎么办呢?继续用Python来充值吧! Python的击出语法里,...

1705
来自专栏彭湖湾的编程世界

【算法】二叉查找树(BST)实现字典API

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

3419
来自专栏IT可乐

Java数据结构和算法(十二)——2-3-4树

  通过前面的介绍,我们知道在二叉树中,每个节点只有一个数据项,最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点,就是多叉树。本篇博客我们将介...

3417
来自专栏程序员叨叨叨

6.1 关系操作符(Comparison Operators)

在上一章中,我们已经介绍了Cg语言的基础数据类型(7种)、内置数据类型,以及数组、结构、接口等类型,本章将在此基础上讨论Cg中的表达式,表达式由操作符(oper...

462
来自专栏尾尾部落

[算法总结] 一文搞懂面试链表题

链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。

631

扫码关注云+社区