二叉树前序遍历（递归+非递归）Java

一、结构

在这里插入图片描述

二、遍历二叉树

这块内容是二叉树最核心的部分。不但要掌握七种遍历的写法，前、中、后序的递归、非递归写法+层次遍历，还有学会（1）用前、中、后序遍历数组创建二叉树；（2）用一维数组存储二叉树。

1.前序遍历（递归）

前序遍历访问节点的顺序是根节点-左儿子-右儿子。

代码

public void preOrderRecur(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.data + " -> ");
        preOrderRecur(root.left);
        preOrderRecur(root.right);
    }

图解

初始。
在这里插入图片描述
第一步：
（1）执行preOrderRecur（Node root）方法，访问节点A，打印“A”。

第二步：
（1）执行preOrderRecur（root.left）方法，访问节点B，不为空，打印“B”。

第三步：
（1）递归调用preOrderRecur（B.left）方法，访问节点D，不为空，打印“D”。
在这里插入图片描述
第四步：
（1）递归调用preOrderRecur（D.left）方法，D.left为空，返回；
（2）递归调用preOrderRecur（D.right）方法，访问节点H，打印“H”。

第五步：
（1）递归调用preOrderRecur（H.left）方法，此时H.left为空，返回；
（2）递归调用preOrderRecur（H.right）方法，此时H.right为空，返回；
（3）返回到上一级递归方法，即到打印“D”的方法中，这个方法也执行完毕，继续返回到打印“B”的方法中；
（4）递归调用preOrderRecur（B.right）方法，访问节点E，打印“E”。
在这里插入图片描述
第六步：
（1）递归调用preOrderRecur（E.right）方法，访问节点I，打印“I”。

第七步：
（1）递归调用preOrderRecur（I.left）方法，此时I.left为空，返回；
（2）递归调用preOrderRecur（I.right）方法，此时I.right为空，返回；
（3）返回上一级递归方法，即打印“E”的方法中，递归调用preOrderRecur（E.right）方法，访问节点J，打印“J”。
在这里插入图片描述
第八步：
（1）J的左右子树都为空，返回到打印“E”的方法中，该方法执行完毕；
（2）返回到打印“B”的方法中，该方法也执行完毕，接着向上返回到打印“A”的方法中；
（3）递归调用preOrderRecur（A.right）方法，访问节点C，打印“C”。
在这里插入图片描述
第九步：

第十步：

打印顺序为：ABDHEIJCFG

2.前序遍历（非递归）

代码

public void preOrder() {
        if (root == null)
            return;
        Node current;
        //把LinkedList当栈使用
        LinkedList<Node> s = new LinkedList<Node>();
        s.addFirst(root);
        while (!s.isEmpty()) {
            current = s.removeFirst();
            System.out.print(current.data + " -> ");
            if (current.right != null)
                s.addFirst(current.right);
            if (current.left != null)
                s.addFirst(current.left);
        }
    }