java二叉树的遍历方式详解

目录
  • 一、前序遍历(递归和非递归)
  • 二、中序遍历(递归和非递归)
  • 三、后序遍历(递归和非递归)
  • 四、层序遍历
  • 总结

一、前序遍历(递归和非递归)

前序遍历就是先遍历根再遍历左之后是右 根左右

递归实现:

 public List<Integer> preorderTraversal(TreeNode root) {
       List <Integer>  list=new ArrayList<>();
       pre(root,list);
       return list;
    }
    public void pre(TreeNode root,List list){
        if(root==null){
            return ;
        }
        list.add(root.val);
        pre(root.left,list);
        pre(root.right,list);
    }

迭代实现:

利用栈来实现 先将树的右子树放入栈中,再放入左子树

 public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null) return list;
        Stack<TreeNode>  stack=new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node=stack.pop();
            list.add(node.val);
           if(node.right!=null) stack.push(node.right);
            if(node.left!=null) stack.push(node.left);
        }
        return list;
    }

二、中序遍历(递归和非递归)

中序遍历就是先遍历左再遍历根,最后遍历右 左根右

递归实现:

 public List<Integer> inorderTraversal(TreeNode root) {
         List <Integer> list=new ArrayList<>();
         inorder(root,list);
         return list;
    }
    public void inorder(TreeNode root,List list){
        if(root==null){
            return ;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }

迭代实现

利用栈来实现,二叉树的中序遍历,由于中序遍历是左根右,先定义节点找到最左节点入栈,之后出栈,判断该节点是否有右孩子

 public List<Integer> inorderTraversal(TreeNode root) {
        //迭代实现
        List<Integer> list =new LinkedList<>();
        Stack <TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            //先找到左节点
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode node=stack.pop();
            list.add(node.val);
            if(node.right!=null){
              cur=node.right;
            }
        }
        return list;
    }

三、后序遍历(递归和非递归)

后序遍历就是左右根

递归实现:

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
            postorder(root,list);
            return list;
    }
    public void postorder(TreeNode root,List list){
        if(root==null){
            return ;
        }
        postorder(root.left,list);
        postorder(root.right,list);
        list.add(root.val);
    }

非递归实现:

用两个栈来实现二叉树的后序遍历

第一个栈先放入根节点,之后弹出放入第二个节点,之后第一个栈放入左右孩子,之后再弹出放入第二个栈,即可实现

 public List<Integer> postorderTraversal(TreeNode root) {
        //利用双栈实现后序遍历
        Stack <TreeNode> s1=new Stack<>();
        Stack <TreeNode> s2=new Stack<>();
        List<Integer> list=new LinkedList<>();
          if(root==null) return list;
        s1.push(root);
        while(!s1.isEmpty()){
            TreeNode node=s1.pop();
            s2.push(node);
            if(node.left!=null) s1.push(node.left);
            if(node.right!=null) s1.push(node.right);
        }
        while(!s2.isEmpty()){
            TreeNode cur=s2.pop();
            list.add(cur.val);
        }
        return list;
    }

四、层序遍历

用队列实现层序遍历

public List<List<Integer>> levelOrder(TreeNode root) {
        //用队列实现层序遍历
        //第一层节点先进队列,出的节点带下一层的节点
        List <List<Integer>> list=new ArrayList<>();
         if(root==null) return list;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> list1=new ArrayList<>();
            int size=queue.size();
            while(size!=0){
                TreeNode cur=queue.poll();
                list1.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;
            }
            list.add(list1);
        }
        return list;
    }

总结

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

(0)

相关推荐

  • java实现二叉树遍历的三种方式

    本文实例为大家分享了java实现二叉树遍历的具体代码,供大家参考,具体内容如下 二叉树如下: 遍历结果如下: 以下是实现代码: package binTree; import java.util.Stack; /** * @author bin.zhang * @version 2017年8月29日 上午10:22:01 */ public class BinTreeTraversal { public static void main(String[] args) { System.out.p

  • java实现按层遍历二叉树

    本文实例为大家分享了java实现按层遍历二叉树,按层遍历二叉树可以通过队列来实现.其主要思路如下: 1.先将根节点放入队列中 2.每次都从队列中取出一个结点打印该结点的值 3.若这个结点有子结点,则将它的子结点放入队列尾,知道队列为空. 实现代码如下: import java.util.LinkedList; import java.util.Queue; public class LayerTranverse { //按层遍历二叉树 public static void main(String

  • java如何创建普通二叉树

    java创建二叉树 这段时间一直在复习数据结构的知识. 从最基础的开始,实现一个普通的二叉树.但发现也不那么简单.因为之前学数据结构时是用C语言写的. 指针用来对结构体的值操作比较好理解.但java没有指针. 而Node节点在方法中传递的是地址. 如果直接对形参进行new操作是错误的.无法改变实参的值的.这一点坑了我很久,然后一顿查资料. 时隔很久,终于填上这个坑了 下面是以递归创建的二叉树.还有一些常见的遍历和树的高度与树的最大宽度. 一个方法不能修改一个基本数据类型的参数 一个方法可以修改一

  • java编程题之从上往下打印出二叉树

    本文实例为大家分享了java从上往下打印出二叉树的具体代码,供大家参考,具体内容如下 github:剑指offer编程全部试题 import java.util.ArrayList; import java.util.Stack; /** * * 剑指offer编程题(JAVA实现)--第22题:从上往下打印出二叉树 * * 题目描述 * 从上往下打印出二叉树的每个节点,同层节点从左至右打印. * */ public class Test22 { ArrayList<Integer> arra

  • Java实现二叉树的建立、计算高度与递归输出操作示例

    本文实例讲述了Java实现二叉树的建立.计算高度与递归输出操作.分享给大家供大家参考,具体如下: 1. 建立 递归输出 计算高度 前中后三种非递归输出 public class Tree_Link { private int save = 0; private int now = 0; Scanner sc = new Scanner(System.in); /* * 构造函数 */ Tree_Link(){ } /* * 链表建立 */ public Tree Link_Build(Tree

  • java二叉树的非递归遍历

    二叉树的递归遍历比较简单,这里就不聊了.今天主要聊聊二叉树的非递归遍历,主要借助于"栈"后进先出的特性来保存节点的顺序,先序遍历和中序遍历相对来说比较简单,重点理解后序遍历. 1. 先看看节点类型: //二叉树的节点类型 private class Node{ int data; //节点值 Node leftChild; //左孩子 Node rightChild; //右孩子 public Node(int data) { this.data=data; } } 2.先序遍历. 非

  • JAVA二叉树的基本操作

    目录 记录二叉树的基本操作DEMO 1.创建一个二叉树类 2.然后创建二叉树的节点 记录二叉树的基本操作DEMO 1.创建一个二叉树类 这里约束了泛型只能为实现了Comparable这个接口的类型. /** * @author JackHui * @version BinaryTree.java, 2020年03月05日 12:45 */ public class BinaryTree<T extends Comparable> { //树根 BinaryTreeNode root; publ

  • java二叉树面试题详解

    目录 二叉树的深度 二叉搜索树的第k大节点 从上到下打印二叉树 二叉树的镜像 对称的二叉树 树的子结构 重建二叉树 二叉树的下一个节点 二叉搜索树的后序遍历路径 二叉树中和为某一值的路径 二叉搜索树与双向链表 总结 二叉树的深度 题目:输入一颗二叉树的根节点,求该树的的深度.输入一颗二叉树的根节点,求该树的深度.从根节点到叶节点依次经过的节点(含根.叶节点)形成的一条路径,最长路径的长度为树的深度. 如果一棵树只有一个节点,那么它的深度是1.如果根节点只有左子树,那深度是其左子树的深度+1,同样

  • java 对称二叉树的判断

    1. 题目描述 请实现一个函数,用来判断一颗二叉树是不是对称的.注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的. 2. 解题思路 可以按照类似层次遍历,来判断是否是堆成二叉树: 首先根节点以及其左右子树,左子树的左子树和右子树的右子树相同,以及左子树的右子树和右子树的左子树相同即可,然后采用递归一直判断下去. 3. 代码 public class isSymmetrical { public static void main(String[] args) { // 新建一棵二叉搜索

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

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

  • Java多线程通信实现方式详解

    这篇文章主要介绍了Java多线程通信实现方式详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 线程通信的方式: 1.共享变量 线程间通信可以通过发送信号,发送信号的一个简单方式是在共享对象的变量里设置信号值.线程A在一个同步块里设置boolean型成员变量hasDataToProcess为true,线程B也在同步代码块里读取hasDataToProcess这个成员变量.这个简单的例子使用了一个持有信号的对象,并提供了set和get方法. pu

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

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

  • Java中map遍历方式的选择问题详解

    1. 阐述 对于Java中Map的遍历方式,很多文章都推荐使用entrySet,认为其比keySet的效率高很多.理由是:entrySet方法一次拿到所有key和value的集合:而keySet拿到的只是key的集合,针对每个key,都要去Map中额外查找一次value,从而降低了总体效率.那么实际情况如何呢? 为了解遍历性能的真实差距,包括在遍历key+value.遍历key.遍历value等不同场景下的差异,我试着进行了一些对比测试. 2. 对比测试 一开始只进行了简单的测试,但结果却表明k

  • Java中遍历ConcurrentHashMap的四种方式详解

    这篇文章主要介绍了Java中遍历ConcurrentHashMap的四种方式详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 方式一:在for-each循环中使用entries来遍历 System.out.println("方式一:在for-each循环中使用entries来遍历");for (Map.Entry<String, String> entry: map.entrySet()) { System.out.pr

  • classloader类加载器_基于java类的加载方式详解

    基础概念 Classloader 类加载器,用来加载 Java 类到 Java 虚拟机中.与普通程序不同的是.Java程序(class文件)并不是本地的可执行程序.当运行Java程序时,首先运行JVM(Java虚拟机),然后再把Java class加载到JVM里头运行,负责加载Java class的这部分就叫做Class Loader. JVM本身包含了一个ClassLoader称为Bootstrap ClassLoader,和JVM一样,BootstrapClassLoader是用本地代码实现

  • Java数据库连接_jdbc-odbc桥连接方式(详解)

    jdbc-odbc桥连接方式操作数据库SU(Course) 步骤: 1.配置数据源 控制面板下搜索管理工具->ODBC数据源(32位)->添加->选择sql server(填写名称mytest,服务器local或者.)->下一步->更改默认的数据库为SU->下一步->测试数据源至成功 用户数据源会多一条mytest,至此配置数据源成功. 2.在程序中连接数据源 打开eclipse,编写程序. public class Demo_1 { public static

  • java打jar包的几种方式详解

    一.制作只含有字节码文件的jar包 我们先来看只含有字节码文件,即只含有class文件的jar包怎么制作,这是最简单的形式 1.最简单的jar包--直接输出hello 最终生成的jar包结构 META-INF Hello.class 方法步骤 (1)用记事本写一个Hello.java的文件 class Hello{     public static void main(String[] agrs){         System.out.println("hello");     }

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

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

  • Java实现AOP代理的三种方式详解

    目录 1.JDK实现 2.CGLIB实现 3.boot注解实现[注意只对bean有效] 业务场景:首先你有了一个非常好的前辈无时无刻的在“教育”你.有这么一天,它叫你将它写好的一个方法进行改进测试,这时出现了功能迭代的情况.然后前辈好好“教育”你的说,不行改我的代码!改就腿打折!悲催的你有两条路可走,拿出你10年跆拳道的功夫去火拼一波然后拍拍屁股潇洒走人,要么就是悲催的开始百度...这时你会发现,我擦怎么把AOP代理这种事给忘了?[其实在我们工作中很少去手写它,但是它又是很常见的在使用(控制台日

随机推荐