学习回忆录之二叉树的七种遍历方式

/ 默认分类 / 0 条评论 / 1284浏览

数据结构

二叉树的七种遍历方式

方法1:层级遍历

层级遍历是二叉树遍历的一种常用方式,可以使用队列先进先出的特性将二叉树的每一层节点存入,然后一层层弹出获取下一层数据 这里的要求是需要按照不同的层次进行打印,也就是说需要区分出不同的层级队列.下面是我写的两种方式:

两种方式运行结构基本一样


//使用临时层级队列,区分队列的层级关系
public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        ArrayDeque<TreeNode> mainQueue = new ArrayDeque<TreeNode>();
        if(root == null){
            return result;
        }
        mainQueue.push(root);
        ArrayList<Integer> rootStep = new ArrayList<>();
        rootStep.add(root.val);
        result.add(rootStep);
        ArrayList<Integer> childStep = new ArrayList<>();
        ArrayDeque<TreeNode> queueTemp = new ArrayDeque<TreeNode>();
        while (!mainQueue.isEmpty()){
            TreeNode currentNode = mainQueue.pop();
            if(currentNode.left != null){
                queueTemp.add(currentNode.left);
                childStep.add(currentNode.left.val);
            }
            if(currentNode.right != null){
                queueTemp.add(currentNode.right);
                childStep.add(currentNode.right.val);
            }
            //遍历当前层级的queue的最后一个元素之后,将当前queue换位最新的
            if(mainQueue.isEmpty() && childStep.size() > 0){
                mainQueue = queueTemp;
                result.add(childStep);
                childStep = new ArrayList<>();
                queueTemp = new ArrayDeque<TreeNode>();
            }
        }
        return result;
    }


//通过循环上一次层级队列的个数次,区分队列的层级关系
    public static List<List<Integer>> levelOrder1(TreeNode root) {
        if(root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        ArrayDeque<TreeNode> mainQueue = new ArrayDeque<TreeNode>();
        mainQueue.add(root);
        while(!mainQueue.isEmpty()){
            int count = mainQueue.size();
            List<Integer> list = new ArrayList<Integer>();
            while(count > 0){
                TreeNode currentNode = mainQueue.pop();
                list.add(currentNode.val);
                if(currentNode.left != null) {
                    mainQueue.add(currentNode.left);
                }
                if(currentNode.right != null) {
                    mainQueue.add(currentNode.right);
                }
                count--;
            }
            result.add(list);
        }
        return result;
    } 


/**
public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
 */

当然,如果不需要区分树的层次,那么可以直接使用队列输出即可,也就是这样:

    private static void cengjibianli(TreeNode root) {
        if(root == null){
            return;
        }
        ArrayDeque<TreeNode> queue = new ArrayDeque();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode pop = queue.pop();
            System.out.println(pop.val);
            if(pop.left != null){
                queue.add(pop.left);
            }
            if(pop.right != null){
                queue.add(pop.right);
            }
        }
    }

递归的前中后序遍历

首先递归就是将一件完整的事情进行分析,发现这件事都是在做同一件相同的事情,只是阶段不同,下面想来简单写一个经典的递归遍历 文件夹文件的程序,其实都是同一件事,首先看这个文件是否为文件夹,如果是就获取文件夹下的所有文件然后遍历这些,如果是文件就输出文件名.

    public static void main(String[] args) {
        getFile(new File("D:\\soft2\\qqmusic"));
    }

    public static void getFile(File file){
        File[] files = file.listFiles();
        for (File file1 : files) {
            //如果是目录就继续遍历如果不是就输出文件名
            if(file1.isDirectory()){
                getFile(file1);
            }else{
                System.out.println(file1.getName());
            }
        }
    }

二叉树的递归遍历方式很容易理解,就是按照一个节点的遍历方式来写就好了.

ps:关于二叉树遍历的几种方式的定义这里不再过多介绍,之前我有说过,其实就是根节点遍历的三种时机.

方法2:递归前序遍历

    public static void diguiqianxubianli(TreeNode root){
        if (root != null){
            System.out.println(root.val);
            diguiqianxubianli(root.left);
            diguiqianxubianli(root.right);
        }
    }

方法3:递归中序遍历

    public static void diguiqianxubianli(TreeNode root){
        if (root != null){
            diguiqianxubianli(root.left);
            System.out.println(root.val);
            diguiqianxubianli(root.right);
        }
    }

方法4:递归后序遍历

    public static void diguiqianxubianli(TreeNode root){
        if (root != null){
            diguiqianxubianli(root.left);
            diguiqianxubianli(root.right);
            System.out.println(root.val);
        }
    }

二叉树非递归遍历

假设有下面这样的二叉树

方法5:非递归前序遍历

    private static void qianxubianli(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        if(root ==null){
            return;
        }
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            System.out.println(pop.val);
            if(pop.right != null){
                stack.push(pop.right);
            }
            if(pop.left != null){
                stack.push(pop.left);
            }
        }
    }

这里需要注意的是,对于当前节点,首先入栈的应该是右孩子,然后是左孩子,因为栈属于LIFO.具体的原理看了我画的出栈入栈的过程图你应该就明白了.

方法6:非递归中序遍历

假设有下面这样的二叉树

    private static void zhongxubianli(TreeNode root) {

        Stack<TreeNode> stack = new Stack<>();
        if(root == null){
            return;
        }
        TreeNode currentNode = root;
        while (currentNode !=null || !stack.isEmpty()){
            if(currentNode != null){
                stack.push(currentNode);
                currentNode = currentNode.left;
            }else{
                TreeNode pop = stack.pop();
                System.out.println(pop.val);
                currentNode = pop.right;
            }
        }
    }

同样的,我画了这样的入栈出栈图

方法7:非递归后续遍历

使用两个栈结构,stack1每次出栈都将出栈的数据放入stack2,并且在每次stack1出栈时都将当前元素的左右节点元素放入stack2,这里 是先左后右,因为之后需要出栈,再入栈,再出栈,这样就可以保证最后的出栈顺序是先左后右

还是上面的二叉树

    private static void houxubianli(TreeNode root) {
            List<Integer> list=new ArrayList<Integer>();
            Stack<TreeNode> stack1=new Stack<TreeNode>();
            Stack<TreeNode> stack2=new Stack<TreeNode>();
            if (root!=null) {
                stack1.push(root);
                while(!stack1.empty()) {
                    root=stack1.pop();
                    stack2.push(root);
                    if (root.left!=null) {
                        stack1.push(root.left);
                    }
                    if (root.right!=null) {
                        stack1.push(root.right);
                    }
                }
                while(!stack2.empty()) {
                    list.add(stack2.pop().val);
                }
            }
        System.out.println(list);
    }

这里我也画了入栈出栈的过程图,如果大家不是十分理解这里的过程,可以按照代码,自己画出这样的入栈出栈图,这样在写代码的时候会 很清晰.

01

02

03

04

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2021/10/30 13:04