Java二叉树的四种遍历方式详解

二叉树的四种遍历方式:

  • 二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问依次且仅被访问一次。

四种遍历方式分别为:先序遍历、中序遍历、后序遍历、层序遍历。

遍历之前,我们首先介绍一下,如何创建一个二叉树,在这里用的是先建左树在建右树的方法,

首先要声明结点TreeNode类,代码如下:

public class TreeNode {
    public int data;
    public TreeNode leftChild;
    public TreeNode rightChild;
    public TreeNode(int data){
        this.data = data;
    }
}

再来创建一颗二叉树:

/**
     * 构建二叉树
     * @param list   输入序列
     * @return
     */
    public static TreeNode createBinaryTree(LinkedList<Integer> list){
        TreeNode node = null;
        if(list == null || list.isEmpty()){
            return null;
        }
        Integer data = list.removeFirst();
        if(data!=null){
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(list);
            node.rightChild = createBinaryTree(list);
        }
        return node;
    }

接下来按照上面列的顺序一一讲解,

首先来看前序遍历,所谓的前序遍历就是先访问根节点,再访问左节点,最后访问右节点,

如上图所示,前序遍历结果为:

ABDFECGHI

实现代码如下:

/**
     * 二叉树前序遍历   根-> 左-> 右
     * @param node    二叉树节点
     */
    public static void preOrderTraveral(TreeNode node){
        if(node == null){
            return;
        }
        System.out.print(node.data+" ");
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);
    }

再者就是中序遍历,所谓的中序遍历就是先访问左节点,再访问根节点,最后访问右节点,

如上图所示,中序遍历结果为:

DBEFAGHCI

实现代码如下:

/**
     * 二叉树中序遍历   左-> 根-> 右
     * @param node   二叉树节点
     */
    public static void inOrderTraveral(TreeNode node){
        if(node == null){
            return;
        }
        inOrderTraveral(node.leftChild);
        System.out.print(node.data+" ");
        inOrderTraveral(node.rightChild);
    }

最后就是后序遍历,所谓的后序遍历就是先访问左节点,再访问右节点,最后访问根节点。

如上图所示,后序遍历结果为:

DEFBHGICA

实现代码如下:

/**
     * 二叉树后序遍历   左-> 右-> 根
     * @param node    二叉树节点
     */
    public static void postOrderTraveral(TreeNode node){
        if(node == null){
            return;
        }
        postOrderTraveral(node.leftChild);
        postOrderTraveral(node.rightChild);
        System.out.print(node.data+" ");
    }

讲完上面三种递归的方法,下面再给大家讲讲非递归是如何实现前中后序遍历的

还是一样,先看非递归前序遍历

1.首先申请一个新的栈,记为stack;

2.声明一个结点treeNode,让其指向node结点;

3.如果treeNode的不为空,将treeNode的值打印,并将treeNode入栈,然后让treeNode指向treeNode的右结点,

4.重复步骤3,直到treenode为空;

5.然后出栈,让treeNode指向treeNode的右孩子

6.重复步骤3,直到stack为空.

实现代码如下:

public static void preOrderTraveralWithStack(TreeNode node){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = node;
        while(treeNode!=null || !stack.isEmpty()){
            //迭代访问节点的左孩子,并入栈
            while(treeNode != null){
                System.out.print(treeNode.data+" ");
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            //如果节点没有左孩子,则弹出栈顶节点,访问节点右孩子
            if(!stack.isEmpty()){
                treeNode = stack.pop();
                treeNode = treeNode.rightChild;
            }
        }
    }

中序遍历非递归,在此不过多叙述具体步骤了,

具体过程:

1.申请一个新栈,记为stack,申请一个变量cur,初始时令treeNode为头节点;

2.先把treeNode节点压入栈中,对以treeNode节点为头的整棵子树来说,依次把整棵树的左子树压入栈中,即不断令treeNode=treeNode.leftChild,然后重复步骤2;

3.不断重复步骤2,直到发现cur为空,此时从stack中弹出一个节点记为treeNode,打印node的值,并让treeNode= treeNode.right,然后继续重复步骤2;

4.当stack为空并且cur为空时结束。

public static void inOrderTraveralWithStack(TreeNode node){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = node;
        while(treeNode!=null || !stack.isEmpty()){
            while(treeNode != null){
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            if(!stack.isEmpty()){
                treeNode = stack.pop();
                System.out.print(treeNode.data+" ");
                treeNode = treeNode.rightChild;
            }
        }
    }

后序遍历非递归实现,后序遍历这里较前两者实现复杂一点,我们需要一个标记位来记忆我们此时节点上一个节点,具体看代码注释

public static void postOrderTraveralWithStack(TreeNode node){
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode treeNode = node;
        TreeNode lastVisit = null;   //标记每次遍历最后一次访问的节点
        while(treeNode!=null || !stack.isEmpty()){//节点不为空,结点入栈,并且指向下一个左孩子
            while(treeNode!=null){
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }
            //栈不为空
            if(!stack.isEmpty()){
                //出栈
                treeNode = stack.pop();
                /**
                 * 这块就是判断treeNode是否有右孩子,
                 * 如果没有输出treeNode.data,让lastVisit指向treeNode,并让treeNode为空
                 * 如果有右孩子,将当前节点继续入栈,treeNode指向它的右孩子,继续重复循环
                 */
                if(treeNode.rightChild == null || treeNode.rightChild == lastVisit) {
                    System.out.print(treeNode.data + " ");
                    lastVisit = treeNode;
                    treeNode  = null;
                }else{
                    stack.push(treeNode);
                    treeNode = treeNode.rightChild;
                }
            }
        }
    }

最后再给大家介绍一下层序遍历

具体步骤如下:

1.首先申请一个新的队列,记为queue;

2.将头结点head压入queue中;

3.每次从queue中出队,记为node,然后打印node值,如果node左孩子不为空,则将左孩子入队;如果node的右孩子不为空,则将右孩子入队;

4.重复步骤3,直到queue为空。

实现代码如下:

public static void levelOrder(TreeNode root){
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            root = queue.pop();
            System.out.print(root.data+" ");
            if(root.leftChild!=null) queue.add(root.leftChild);
            if(root.rightChild!=null) queue.add(root.rightChild);
        }
    }

总结

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • java栈实现二叉树的非递归遍历的示例代码

    一般来说遍历二叉树用到递归,但是用Stack进行遍历也是一个不错的方法. 二叉树设置 class Node{ public int val; public Node left; public Node right; public Node(int v) { val=v; left=null; right=null; } } public class Main { public static void main(String[] args) { Node head =new Node(0); No

  • java二叉树的遍历方式详解

    目录 一.前序遍历(递归和非递归) 二.中序遍历(递归和非递归) 三.后序遍历(递归和非递归) 四.层序遍历 总结 一.前序遍历(递归和非递归) 前序遍历就是先遍历根再遍历左之后是右 根左右 递归实现: public List<Integer> preorderTraversal(TreeNode root) { List <Integer> list=new ArrayList<>(); pre(root,list); return list; } public vo

  • Java二叉树的四种遍历(递归与非递归)

    目录 一.先序遍历与后序遍历 二.中序遍历 三.层序遍历 一.先序遍历与后序遍历 先序遍历根节点,再遍历左子树,再遍历右子树. 后序遍历先遍历左子树,再遍历右子树,再遍历根节点. 先序遍历递归实现: public static void preOrderByRecursion(TreeNode root) { // 打印节点值 System.out.println(root.value); preOrder(root.left); preOrder(root.right); } 先序遍历的非递归

  • Java 二叉树遍历的常用方法

    采用前序遍历.中序遍历.后续遍历实现时,即便采用不同的实现方式(递归方式.非递归),它们的算法结构是有很大的相似性.因而针对前三种的遍历我们会总结出对应通用的解决框架,便于在解决二叉树问题时进行使用. 递归方式 递归方式遍历二叉树时,无论是 前序遍历.中序遍历 还是 后续遍历 的方式,它们最大的区别就是对节点数据的访问位置不同.除此之外其结构完全一致,因而我们总结出如下的框架结构: void traverse(TreeNode root) { //终止条件 if(root == null) re

  • Java中关于二叉树层序遍历深入了解

    前言 大家好,我是bigsai,在数据结构与算法中,二叉树无论是考研.笔试都是非常高频的考点内容,在二叉树中,二叉树的遍历又是非常重要的知识点,今天给大家讲讲二叉树的层序遍历. 这部分很多人可能会但是需要注重一下细节. 前面介绍了二叉排序树的构造和基本方法的实现,遍历也是比较重要的一环,并且二叉树的层序遍历也是bfs的最简单情况,这里我就将二叉树的层序遍历以及常考问题给大家分享一下. 在了解二叉树的遍历之前,需要具备数据结构与算法有队列.递归.栈.二叉树,这些内容咱们前面都有讲过,有这方面知识欠

  • java非递归实现之二叉树的前中后序遍历详解

    二叉树的前中后序遍历 核心思想:用栈来实现对节点的存储.一边遍历,一边将节点入栈,在需要时将节点从栈中取出来并遍历该节点的左子树或者右子树,重复上述过程,当栈为空时,遍历完成. 前序遍历 //非递归 //根 左 右 class Solution { public List<Integer> preorderTraversal(TreeNode root) { //用数组来存储前序遍历结果 List<Integer> list = new ArrayList<>(); i

  • Java二叉树的四种遍历方式详解

    二叉树的四种遍历方式: 二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问依次且仅被访问一次. 四种遍历方式分别为:先序遍历.中序遍历.后序遍历.层序遍历. 遍历之前,我们首先介绍一下,如何创建一个二叉树,在这里用的是先建左树在建右树的方法, 首先要声明结点TreeNode类,代码如下: public class TreeNode { public int data; public TreeNode leftC

  • Java动态代理四种实现方式详解

    代理模式也是一种非常常见的设计模式.了解Spring框架的都知道,Spring AOP 使用的就是动态代理模式.今天就来系统的重温一遍代理模式. 在现实生活中代理是随处可见的,当事人因某些隐私不方便出面,或者当事人不具备某些相关的专业技能,而需要一个职业人员来完成一些专业的操作, 也可能由于当事人没有时间处理事务,而聘用代理人出面.而在软件设计中,使用代理模式的地方也很多,由于安全原因,屏蔽客户端直接访问真实对象, 或者为了提升系统性能,使用代理模式实现延迟加载,还有就是AOP,对委托类的功能进

  • Java二叉树的四种遍历(递归和非递归)

    二叉树的遍历可以分为前序.中序.后序.层次遍历. 前中后是指何时访问中间节点,即前序遍历,遍历节点的顺序为:中->左->右: 中序遍历,遍历节点的顺序为:左->中->右: 后序遍历,遍历节点的顺序为:左->右->中. 前序遍历 递归实现 public void preorder_Traversal(TreeNode root) { if(root==null)return; //访问节点的逻辑代码块 System.out.print(root.val+" &q

  • Android开发之基本控件和四种布局方式详解

    Android中的控件的使用方式和iOS中控件的使用方式基本相同,都是事件驱动.给控件添加事件也有接口回调和委托代理的方式.今天这篇博客就总结一下Android中常用的基本控件以及布局方式.说到布局方式Android和iOS还是区别挺大的,在iOS中有Frame绝对布局和AutoLayout相对布局.而在Android中的布局方式就比较丰富了,今天博客中会介绍四种常用的布局方式.先总结一下控件,然后再搞一搞基本方式,开发环境还是用的Mac下的Android Studio.开始今天的正题, 虽然A

  • buildAdmin开源项目引入四种图标方式详解

    目录 正文 引入Element-Plus图标库 引入Iconfont图标库 引入FontAwesome图标库 引入本地svg图标 正文 在项目开发中,我们经常使用可能都是UI组件库里的图标,当然由于业务需要,可能当前图标库没有我们需要的图标这时候就需要引入其它图标库的图标,比如iconfont.FontAweSome.本地图标库.在了解引入这些图标库之前,我们先学习一下各种图标库的引入使用: Element-Plus:由于elemen官方已经把图标封装成了组件,所以当我们引入图标的时候,需要全局

  • Spring Data Jpa的四种查询方式详解

    这篇文章主要介绍了Spring Data Jpa的四种查询方式详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一.调用接口的方式 1.基本介绍 通过调用接口里的方法查询,需要我们自定义的接口继承Spring Data Jpa规定的接口 public interface UserDao extends JpaRepository<User, Integer>, JpaSpecificationExecutor<User> 使用这

  • Java spring的三种注入方式详解流程

    目录 设置Spring的作用域 自动注入 @Primary Qualifier @ComponentScan不同的配置对性能的影响 懒加载 三种注入方式 字段注入(IDEA 会提示不推荐) 字段注入的bean类外部不可见 循环依赖问题 构造器注入(官方推荐) set方法注入 设置Spring的作用域 或者使用枚举值设置 单例和多里使用场景 自动注入 @Primary 一个接口有多个实现被spring管理吗,在依赖注入式,spring会不知道注入哪个实现类就会抛出NoUniqueBeanDefin

  • Spring bean 四种注入方式详解

    目录 一.Set方式注入 pojo层: 1.xml 文件 test测试 二.构造函数方式注入 pojo层 2.xml文件 test测试 三.注解注入 pojo层 3.xml文件 test测试 四.JavaConfig 方式注入 pojo层 JavaConfig 类 xml文件 扫描包 测试: 五.Service层注入详解 service serviceImpl xml配置文件 总结 一.Set方式注入 pojo层: /** * @Author: crush * @Date: 2021-06-17

  • Python编程实现二叉树及七种遍历方法详解

    本文实例讲述了Python实现二叉树及遍历方法.分享给大家供大家参考,具体如下: 介绍: 树是数据结构中非常重要的一种,主要的用途是用来提高查找效率,对于要重复查找的情况效果更佳,如二叉排序树.FP-树.另外可以用来提高编码效率,如哈弗曼树. 代码: 用Python实现树的构造和几种遍历算法,虽然不难,不过还是把代码作了一下整理总结.实现功能: ① 树的构造 ② 递归实现先序遍历.中序遍历.后序遍历 ③ 堆栈实现先序遍历.中序遍历.后序遍历 ④ 队列实现层次遍历 #coding=utf-8 cl

随机推荐