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

目录
  • 前言
  • 1.递归遍历
  • 2.非迭代遍历
  • 3.二叉树的统一迭代法

前言

二叉树的遍历方法分为前序遍历,中序遍历,后续遍历,层序遍历。

1.递归遍历

对于递归,就不得不说递归三要素:以前序遍历为例

递归入参参数和返回值

因为要打印出前序遍历节点的数值,所以参数里需要传入List在放节点的数值,除了这一点就不需要在处理什么数据了也不需要有返回值,所以递归函数返回类型就是void,代码如下:

public void preorder(TreeNode root, List<Integer> result)

确定终止条件

在递归的过程中,如何算是递归结束了呢,当然是当前遍历的节点是空了,那么本层递归就要要结束了,所以如果当前遍历的这个节点是空,就直接return

if (root == null) return;

单层循环逻辑

前序遍历是中左右的循序,所以在单层递归的逻辑,是要先取中节点的数值,代码如下:

result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }
    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);//先保存中间节点
        preorder(root.left, result); //处理左边节点
        preorder(root.right, result); //处理右边节点
    }
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list); //先处理左边节点
        list.add(root.val);       //保存中间当前的节点
        inorder(root.right, list);//先处理右边节点
    }
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }
    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);  //先处理左边节点
        postorder(root.right, list); //再处理右边节点
        list.add(root.val);          //保存最后
    }
}

2.非迭代遍历

//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        if (root == null) return res;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.right != null) { //先将右孩子入栈,因为它在最后
                stack.push(node.right);
            }
            if (node.left != null) { //左孩子入栈再出栈
                stack.push(node.left);
            }
        }
        return res;
    }
}
//中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            //如果可以,一直往左下探
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop(); //弹出来的肯定是叶子节点或中间节点
                res.add(cur.val); //将这个节点加入list
                cur = cur.right; //查看当前节点是否有右节点,如果右,肯定是中间节点,如果没有,就是叶子节点,继续弹出就可以
            }
        }
        return res;
    }
}
//后序遍历
//再来看后序遍历,先序遍历是中左右,后续遍历是左右中,那么我们只需要调整一下先序遍历的代码顺序,就变成中右左的遍历顺序,然后在反转result数组,输出的结果顺序就是左右中
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);
            if (node.left != null) stack.push(node.left); // 相对于前序遍历,这更改一下入栈顺序 (空节点不入栈)
            if (node.right != null) stack.push(node.right);// 空节点不入栈
        }
        Collections.reverse(res); // 将结果反转之后就是左右中的顺序了
        return res;
    }
}

3.二叉树的统一迭代法

//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点(空节点不入栈)
                if (node.left!=null) st.push(node.left);    // 添加左节点(空节点不入栈)
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。
            } else { // 只有遇到空节点的时候,才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}
//中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点(空节点不入栈)
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。
                if (node.left!=null) st.push(node.left);    // 添加左节点(空节点不入栈)
            } else { // 只有遇到空节点的时候,才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}
//后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 添加右节点(空节点不入栈)
                if (node.left!=null) st.push(node.left);    // 添加左节点(空节点不入栈)
            } else { // 只有遇到空节点的时候,才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

到此这篇关于Java开发深入分析讲解二叉树的递归和非递归遍历方法的文章就介绍到这了,更多相关Java二叉树的递归内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(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二叉树的几种遍历(递归,非递归)实现

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

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

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

  • java二叉树的非递归遍历

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

  • Java 数据结构中二叉树前中后序遍历非递归的具体实现详解

    目录 一.前序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现 二.中序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现 三.后序遍历 1.题目描述 2.输入输出示例 3.解题思路 4.代码实现 一.前序遍历 1.题目描述 给你二叉树的根节点 root ,返回它节点值的 前序 遍历. 2.输入输出示例 示例 1: 输入:root = [1,null,2,3] 输出:[1,2,3] 示例2: 输入:root = [] 输出:[] 示例 3: 输入:root = [1

  • 通俗易懂讲解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 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(

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

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

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

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

  • 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.

随机推荐