美文网首页
数据结构笔记

数据结构笔记

作者: R7_Perfect | 来源:发表于2019-08-15 09:06 被阅读0次

二叉树遍历

数据结构

    private static class TreeNode {
        int val;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

深度优先&广度优先

深度优先:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历中序遍历后序遍历。深度优先遍历非递归的通用做法是采用栈
广度优先:从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。广度优先遍历使用方法为层次遍历,非递归的通用做法是采用队列

先序遍历

先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树。按照这个规则,可以很容易的写出先序遍历的递归方法。

 /**
     * 先序遍历二叉树,递归
     * @param root
     */
    public static void preOrderTraverse(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrderTraverse(root.left);
        preOrderTraverse(root.right);
    }

对于非递归方法,可以描述为:由根节点开始,不断将二叉树的节点压入栈中,然后由栈中取出栈顶节点,并且将该节点的右、左(顺序不可颠倒)子节点压入栈中,循环此过程直至栈为空。 该方法的java代码如下:

/**
     * 先序遍历二叉树,非递归
     * @param root
     */
    public static void preOrderTraverseNoRecursion(TreeNode root){
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode currentNode = stack.pop();
            System.out.print(currentNode.val + " ");
            if (currentNode.right != null){
                stack.push(currentNode.right);
            }
            if (currentNode.left != null){
                stack.push(currentNode.left);
            }
        }
        System.out.print("\n");
    }

中序遍历

中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树。按照这个规则,可以很容易的写出中序遍历的递归方法。

 /**
     * 中序遍历二叉树,递归
     * @param root
     */
    public static void inOrderTraverse(TreeNode root){
        if(root == null){
            return;
        }
        inOrderTraverse(root.left);
        System.out.print(root.val + " ");
        inOrderTraverse(root.right);
    }

后序遍历

后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后再访问根。按照这个规则,可以很容易的写出后序遍历的递归方法。

 /**
     * 后序遍历二叉树,递归
     * @param root
     */
    public static void postOrderTraverse(TreeNode root){
        if(root == null){
            return;
        }
        postOrderTraverse(root.left);
        postOrderTraverse(root.right);
        System.out.print(root.val + " ");
    }

层次遍历

层次遍历指的是将二叉树按层输出。借助队列可以很容易的实现层次优先遍历。算法描述为:由根节点开始,不断将二叉树的节点送至队列中,然后由队列中取出队列头节点,并且将该节点的左、右子节点分别送至队列中,循环此过程直至队列为空。java代码如下:

 /**
     * 普通层次遍历
     * @param root
     */
    public static void levelTraverse(TreeNode root){
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        while (!queue.isEmpty()){
            TreeNode currentNode = queue.poll();
            System.out.print(currentNode.val + " ");
            if (currentNode.left != null){
                queue.add(currentNode.left);
            }
            if (currentNode.right != null){
                queue.add(currentNode.right);
            }
        }
        System.out.println();
    }

//层次遍历进阶
//除了一般的层次遍历,这里再介绍一种面试中常考的层次遍历——按二叉树的层次结构分行输出元素。要实//现这种需求,只需要两个指针记录当前行和下一行最右的节点即可。java代码如下:
 /**
     * 按行打印二叉树
     * 算法描述:
     * 1. 初始化:将根节点传入队列,last、nlast指针均指向根节点,
     *    其中,last指针指向当前行最右侧的元素,nlast指针指向下一行最右侧的元素
     * 2. 循环判断队列是否为空,如果不为空,则:
     *    2.1: 获取队列头元素p(将其在队列内删除)并打印
     *    2.2: 将该节点的左右子树分别压入队列,并更新nlast指针
     *    2.3: 判断last指针与p是否相等,如果相等,则换行,并且更新last = nlast
     * @param root
     * @return
     */
    public static void printTreeByRow(TreeNode root){
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        
        TreeNode last = root;
        TreeNode nLast = null;
        
        while (!queue.isEmpty()){
            TreeNode p = queue.poll();
            System.out.print(p.val + " ");

            if (p.left != null){
                queue.add(p.left);
                nLast = p.left;
            }
            if (p.right != null){
                queue.add(p.right);
                nLast = p.right;
            }
            // 当last == p时代表该换行了
            if(last == p){
                last = nLast;
                System.out.print("\n");
            }
        }
    }

相关文章

  • 数据结构回顾学习-基础知识

    数据结构回顾学习笔记 这次数据结构回顾笔记,是我对数据结构回顾学习的笔记。回顾过程是参考易百教程网站上数据结构教程...

  • Redis深度历险笔记

    Redis深度历险笔记 基础与应用 Redis基础数据结构 5种基础数据结构:string、list、hash(字...

  • Observer 观察者模式

    设计原则学习笔记 设计模式学习笔记 作用 使数据结构的变换可以从数据结构主动通知到观察者处。同时方便观察者和被观...

  • alg4th-1.3

    algorithm 4th笔记(1.3) 封装数据结构 Bag,Stack,Queue 三种数据结构各有各的特点,...

  • 小甲鱼数据结构&算法教程学习笔记01

    小甲鱼数据结构&算法教程学习笔记01 一、绪论 程序设计=数据结构+算法 数据结构:数据元素之间的一种或多种特定关...

  • 00.数据结构、算法、时间复杂度

    文章为极客时间《数据结构与算法之美》的学习笔记。要点:辩证思考,多想为什么,多练。 什么是数据结构? 数据结构就是...

  • Redis入门--数据结构

    学习笔记 Redis的数据结构的编码 常说的Redis五种基本数据结构string、list、hash、set、z...

  • 数据结构(二):栈和队列

    本系列为数据结构学习笔记,如有错误请指正~ 数据结构(一):数组和链表 一、理论知识 栈和队列都是线性数据结构,属...

  • 数据结构(三):散列表

    本系列为数据结构学习笔记,如有错误请指正~数据结构(一):数组和链表数据结构(二):栈和队列 一、基本概念 散列表...

  • 2019-04-30

    数据结构记录笔记 第一章:数据结构概论 1.1数据结构的概念 数据是信息的载体,是描述客观事物的数、字符,以及所有...

网友评论

      本文标题:数据结构笔记

      本文链接:https://www.haomeiwen.com/subject/dxlajctx.html