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

目录
  • 一、先序遍历与后序遍历
  • 二、中序遍历
  • 三、层序遍历

一、先序遍历与后序遍历

先序遍历根节点,再遍历左子树,再遍历右子树。

后序遍历先遍历左子树,再遍历右子树,再遍历根节点。

先序遍历递归实现:

public static void preOrderByRecursion(TreeNode root) {
    // 打印节点值
    System.out.println(root.value);
    preOrder(root.left);
    preOrder(root.right);
}

先序遍历的非递归实现:

非递归实现需要借助栈这样一个数据结构,实际上递归实现也是依靠栈,只不过是隐式的。

  1. 先将根节点压入栈中。
  2. 弹出栈中的节点,将弹出节点的右子节点压入栈中,再将弹出节点的左子树压入栈中。
  3. 重复步骤2,直到栈为空。
public static void preOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.empty()) {
        TreeNode node = stack.pop();
        // 打印节点值
        System.out.print(node.value + " ");
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

后序遍历递归实现:先序遍历反过来,就不赘述了。

public static void postOrderByRecursion(TreeNode root) {
    postOrderByRecursion(root.left);
    postOrderByRecursion(root.right);
    System.out.println(root.value);
}

后序遍历非递归实现:后序遍历就是先序遍历反过来,所以需要两个栈,多出来的栈用来反向输出。

public static void postOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> s1 = new Stack<>();
    Stack<TreeNode> s2 = new Stack<>();
    s1.push(root);
    while (!s1.empty()) {
        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.empty()) {
        System.out.println(s2.pop().value);
    }
}

二、中序遍历

中序遍历先遍历左子树,再遍历根节点,再遍历右子树。

递归遍历:

public static void inOrderByRecursion(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrderByRecursion(root.left);
    // 打印节点值
    System.out.println(root.value);
    inOrderByRecursion(root.right);
}

非递归遍历:

  1. 将二叉树的左侧“边”从上到下依次压入栈中。
  2. 从栈中弹出节点
  3. 对以弹出节点的右子节点为根节点的子树,重复步骤1。
  4. 重复2、3步骤,直到栈为空。
public static void inOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;

    while (cur != null) {
        stack.push(cur);
        cur = cur.left;
    }

    while (!stack.empty()) {
        TreeNode node = stack.pop();
        System.out.println(node.value);
        cur = node.right;
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
    }
}

三、层序遍历

层序遍历顾名思义就是一层一层,从左到右的遍历二叉树。需要用到队列这一数据结构。

  1. 将根节点推入队列。
  2. 从队列中取出一个节点。
  3. 先将取出节点的左子节点推入队列,再将取出节点的右子节点推入队列。
  4. 重复2、3步骤直到队列中无节点可取。
public static void floorOrder(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.value);
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

到此这篇关于Java二叉树的四种遍历(递归与非递归)的文章就介绍到这了,更多相关Java二叉树的四种遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java二叉树的非递归遍历

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

  • JAVA二叉树的几种遍历(递归,非递归)实现

    首先二叉树是树形结构的一种特殊类型,它符合树形结构的所有特点.本篇博客会针对二叉树来介绍一些树的基本概念,二叉树的基本操作(存储,返回树的深度,节点个数,每一层的节点个数),二叉树的四种遍历(层次,先序,中序,后序) 一.基本概念 二叉树有5种基本形态: 注:二叉树有序树,就是说一个节点的左右节点是有大小之分的,我们通常设定为左孩子一定大于右孩子,下面的实现都是基于这个规则的.二叉树分为三种:满二叉树,完全二叉树,不完全二叉树 二叉树的四种遍历:层次,先序,中序,后序首先是非递归实现上图的满二叉

  • 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 void preorder_Traversal(TreeNode root) { if(root==null)return; //访问节点的逻辑代码块 System.out.print(root.val+" &q

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

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

  • Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】

    本文实例讲述了Java实现的二叉树常用操作.分享给大家供大家参考,具体如下: import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; //二叉树的建树,前中后 递归非递归遍历 层序遍历 //Node节点 class Node { int element; Node left; Node right; public Node() { } public Node(int element) { this.

  • java二叉树的几种遍历递归与非递归实现代码

    前序(先序)遍历 中序遍历 后续遍历 层序遍历 如图二叉树: 二叉树结点结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x){ val=x; } @Override public String toString(){ return "val: "+val; } } 访问函数 public void visit(TreeNode node){ System.out.print(

  • 通俗易懂讲解C语言与Java中二叉树的三种非递归遍历方式

    详解二叉树的三种非递归遍历方式(附C.java源码) 前言 二叉树的递归遍历方式很简单,三种递归遍历方式的区别,只是printf放的位置不一样而已,这里就不多讲了.把前序遍历代码贴在这里: //结点 struct Node { int val; struct Node* left, * right; }; //前序遍历 void pre(Node* root) { if (root == null) return; printf("%d ",root->val); pre(roo

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

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

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

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

  • Java完全二叉树的创建与四种遍历方法分析

    本文实例讲述了Java完全二叉树的创建与四种遍历方法.分享给大家供大家参考,具体如下: 有如下的一颗完全二叉树: 先序遍历结果应该为:1  2  4  5  3  6  7 中序遍历结果应该为:4  2  5  1  6  3  7 后序遍历结果应该为:4  5  2  6  7  3  1 层序遍历结果应该为:1  2  3  4  5  6  7 二叉树的先序遍历.中序遍历.后序遍历其实都是一样的,都是执行递归操作. 我这记录一下层次遍历吧:层次遍历需要用到队列,先入队在出队,每次出队的元素

  • C语言数据结构二叉树先序、中序、后序及层次四种遍历

    目录 一.图示展示 (1)先序遍历 (2)中序遍历 (3)后序遍历 (4)层次遍历 (5)口诀 二.代码展示 一.图示展示 (1)先序遍历 先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果 先序遍历结果为:A B D H I E J C F K G 动画演示: 记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解 (2)中序遍历 中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最

  • Java中四种遍历List的方法总结(推荐)

    实例如下: package com.ietree.basic.collection.loop; import java.util.ArrayList; import java.util.Iterator; import java.util.List; /** * List遍历 * * @author Dylan */ public class ListLoop { public static void main(String[] args) { // 初始化一个长度为10的ArrayList L

  • Java开发深入分析讲解二叉树的递归和非递归遍历方法

    目录 前言 1.递归遍历 2.非迭代遍历 3.二叉树的统一迭代法 前言 二叉树的遍历方法分为前序遍历,中序遍历,后续遍历,层序遍历. 1.递归遍历 对于递归,就不得不说递归三要素:以前序遍历为例 递归入参参数和返回值 因为要打印出前序遍历节点的数值,所以参数里需要传入List在放节点的数值,除了这一点就不需要在处理什么数据了也不需要有返回值,所以递归函数返回类型就是void,代码如下: public void preorder(TreeNode root, List<Integer> resu

  • C语言二叉树的三种遍历方式的实现及原理

    二叉树遍历分为三种:前序.中序.后序,其中序遍历最为重要.为啥叫这个名字?是根据根节点的顺序命名的. 比如上图正常的一个满节点,A:根节点.B:左节点.C:右节点,前序顺序是ABC(根节点排最先,然后同级先左后右):中序顺序是BAC(先左后根最后右):后序顺序是BCA(先左后右最后根). 比如上图二叉树遍历结果 前序遍历:ABCDEFGHK 中序遍历:BDCAEHGKF 后序遍历:DCBHKGFEA 分析中序遍历如下图,中序比较重要(java很多树排序是基于中序,后面讲解分析) 下面介绍一下,二

随机推荐