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

yizhihongxing

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

简介

二叉树是一种常见的数据结构,其遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历。Java中可以使用递归和非递归的方式进行遍历。在该攻略中,我们将详细介绍Java二叉树的四种遍历方式,包括递归和非递归实现,帮助读者提高对Java数据结构的理解。

前序遍历

在前序遍历中,我们先访问二叉树的根节点,然后分别访问左子树和右子树。在Java中,我们可以使用递归和非递归的方式实现前序遍历。

递归实现

public void preOrderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    System.out.println(root.val);
    preOrderTraversal(root.left);
    preOrderTraversal(root.right);
}

非递归实现

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

中序遍历

在中序遍历中,我们先访问二叉树的左子树,然后访问根节点,最后再访问右子树。同样地,在Java中我们也可以使用递归和非递归的方式实现中序遍历。

递归实现

public void inOrderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    inOrderTraversal(root.left);
    System.out.println(root.val);
    inOrderTraversal(root.right);
}

非递归实现

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

后序遍历

在后序遍历中,我们先访问二叉树的左子树,然后访问右子树,最后再访问根节点。同样地,在Java中我们也可以使用递归和非递归的方式实现后序遍历。

递归实现

public void postOrderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    postOrderTraversal(root.left);
    postOrderTraversal(root.right);
    System.out.println(root.val);
}

非递归实现

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

层序遍历

在层序遍历中,我们按照从上到下、从左到右的顺序访问二叉树的每个节点。同样地,在Java中我们也可以使用队列的非递归方式实现层序遍历。

非递归实现

public void levelOrderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int levelSize = queue.size();
        for(int i=0;i<levelSize;i++){
            TreeNode curr = queue.poll();
            System.out.println(curr.val);
            if(curr.left!=null){
                queue.offer(curr.left);
            }
            if(curr.right!=null){
                queue.offer(curr.right);
            }
        }
    } 
}

示例说明

以下为一个简单的二叉树:

       1
     /   \
    2     3
   / \
  4   5

前序遍历

递归:1 2 4 5 3

非递归:1 2 4 5 3

中序遍历

递归:4 2 5 1 3

非递归:4 2 5 1 3

后序遍历

递归:4 5 2 3 1

非递归:4 5 2 3 1

层序遍历

1 2 3 4 5

以上是Java二叉树的四种遍历方式及其实现。希望能够帮助读者更好地掌握Java的数据结构,提高代码能力。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java二叉树的四种遍历(递归与非递归) - Python技术站

(0)
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • windows下gitbash安装教程(小白教程)

    下面是详细的“Windows下GitBash安装教程(小白教程)”。 步骤一:下载Git安装包 首先,从Git官网下载Git安装包。请根据您当前使用的操作系统版本选择对应的安装包,使用以下链接下载: Git for Windows 官方下载页面 示例:如果您的电脑是 Windows 10 操作系统,则应选择“64位Git for Windows 2.32.0…

    other 2023年6月27日
    00
  • 苹果iOS 13.3/iPadOS 13.3开发者预览版Beta2推送 iOS13.3 beta2更新内容汇总

    苹果iOS 13.3/iPadOS 13.3开发者预览版Beta2推送 iOS13.3 beta2更新内容汇总 简介 本次推送的是苹果iOS 13.3/iPadOS 13.3开发者预览版Beta2,是一次针对开发者的测试版本。本文将对iOS13.3 beta2的更新内容和使用方法进行详细的介绍。 更新内容 修复了iCloud Backup的问题 在iOS 1…

    other 2023年6月26日
    00
  • 使用python无账号无限制获取企查查信息的实例代码

    下面是“使用python无账号无限制获取企查查信息的实例代码”的完整攻略。 1. 准备工作 首先,我们需要安装必要的库来进行数据抓取。在此过程中,我们需要使用到以下库:- requests- lxml 可以使用以下命令安装这些库: pip install requests pip install lxml 2. 信息获取 经过调研,我们发现企查查的数据是通过…

    other 2023年6月27日
    00
  • golang 实现tcp server端和client端,并计算RTT时间操作

    这里是关于实现golang TCP服务器端和客户端,并计算RTT时间操作的完整攻略。下面我们一步步来实现。 初始设置 首先,为了实现TCP服务器端和客户端,可以使用Go语言标准库中的net包,这个包提供了各种用于网络通信的功能,我们需要引入这个包,如下: import ( "net" ) 接下来,我们需要定义一些常量、变量等,在本例中我们…

    other 2023年6月27日
    00
  • 浅谈python模块的导入操作

    浅谈python模块的导入操作 在Python中,模块是一种组织代码的方式,可将代码拆分为多个文件,方便复用和维护。Python标准库中以及第三方库中都提供了大量具有各种功能的模块。在使用Python时,我们通常需要使用一些已经存在的模块。而要使用这些模块,我们需要进行导入操作,本文将为大家简要介绍Python中常用的模块导入操作。 导入模块 在Python…

    其他 2023年3月28日
    00
  • vue测试环境打包与生产环境打包文件数量不一致解决方案

    一、问题描述 在使用 Vue.js 进行开发时,一些同学可能遇到过这样的情况:在测试环境下打包出来的文件数量与在生产环境下打包出来的文件数量不一致,并且测试环境下打包出来的文件数量更多。 二、原因分析 造成这个问题的原因比较复杂,主要有以下几点: 1.测试环境下可能会有一些调试和性能分析的代码,比如 source map、开发环境的调试工具等等。 2.在测试…

    other 2023年6月27日
    00
  • Java设计模式之责任链模式的示例详解

    Java设计模式之责任链模式的示例详解 什么是责任链模式 责任链模式是一种行为型设计模式,设计思路是将一个请求同一个处理的对象组成一条链,当请求在链上不断传递并处理直到被处理完毕。责任链模式可以避免请求的直接发起者和接受者之间的耦合关系,同时使得请求可以被多个对象依次进行处理。 如何实现责任链模式 责任链模式包含两个重要的角色:抽象处理者和具体处理者。抽象处…

    other 2023年6月27日
    00
  • js实现加载更多功能实例

    下面是我对于“js实现加载更多功能实例”的攻略: 一、实现思路 实现加载更多功能主要需要以下几个步骤: 在html页面中定义一个数据展示区域,并设定一个按钮用于触发加载更多功能; 使用ajax请求获取更多数据, 并使用JavaScript将其添加到页面; 监听按钮的点击事件,在事件触发时执行加载更多操作; 对于大量数据的情况,可以使用分页加载的方式,每次请求…

    other 2023年6月25日
    00
合作推广
合作推广
分享本页
返回顶部