Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式)

这篇具有很好参考价值的文章主要介绍了Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🔥博客主页: 【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍
  

Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式),Java 数据结构与算法篇,数据结构,深度优先,算法,java

Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式),Java 数据结构与算法篇,数据结构,深度优先,算法,java

文章目录

        1.0 二叉树的说明

        1.1 二叉树的实现

        2.0 二叉树的优先遍历说明

        3.0 用递归方式实现二叉树遍历

        3.1 用递归方式实现遍历 - 前序遍历

        3.2 用递归方式实现遍历 - 中序遍历

        3.3 用递归方式实现遍历 - 后序遍历

        4.0 用非递归方式实现二叉树遍历

        4.1 用非递归方式实现遍历 - 前序遍历

        4.2 用非递归方式实现遍历 - 中序遍历

        4.3 用非递归方式实现遍历 - 后序遍历

        5.0 深度遍历的完整代码


        1.0 二叉树的说明

        二叉树是一种树形数据结构,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树可以为空,或者包含一个根节点和两个指向左子树和右子树的指针。

        1.1 二叉树的实现

二叉树可以是空的,也可以是具有以下特点的非空树:

         - 每个节点最多有两个子节点,分别称为左子节点和右子节点

         - 左子树和右子树都是二叉树

代码实现如下:

public class MyBinaryTree {

    //指向左子树
    private MyBinaryTree left;
    //当前节点的值
    private int val;
    //指向右子树
    private MyBinaryTree right;

    //构造方法一:带一个值的参数
    public MyBinaryTree(int val) {
        this.val = val;
    }

    //构造方法二:带三个参数
    public MyBinaryTree(MyBinaryTree left, int val, MyBinaryTree right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }

}

        实现两个构造方法是为了创建二叉树的时候会比较方便一些。

二叉树的创建如下:

MyBinaryTree myBinaryTree = new MyBinaryTree(new MyBinaryTree(new MyBinaryTree(4),2,null),
                                                        1,
                                             new MyBinaryTree(new MyBinaryTree(5),3,new MyBinaryTree(6)));

该二叉树的图片:

Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式),Java 数据结构与算法篇,数据结构,深度优先,算法,java

        2.0 二叉树的优先遍历说明

        二叉树的优先遍历是指按照一定顺序访问二叉树中的所有节点。常见的三种优先遍历方式包括:前序遍历、中序遍历和后序遍历。可以使用递归实现非递归实现这三种遍历方式。

               

        3.0 用递归方式实现二叉树遍历

        递归实现前序遍历、中序遍历、后续遍历。用递归实现这三种遍历方式的区别就是对于数据什么时候处理,如打印。

                - 前序遍历(Preorder Traversal):首先访问根节点,然后递归地遍历左子树,最后递归地遍历右子树。在前序遍历中,节点的访问顺序是“根-左-右”。

                - 中序遍历(Inorder Traversal):首先递归地遍历左子树,然后访问根节点,最后递归地遍历右子树。在中序遍历中,节点的访问顺序是“左-根-右”。

                - 后序遍历(Postorder Traversal):首先递归地遍历左子树,然后递归地遍历右子树,最后访问根节点。在后序遍历中,节点的访问顺序是“左-右-根”。

        3.1 用递归方式实现遍历 - 前序遍历

        具体思路为:在递出之前需要对当前节点的值访问,然后再接着向左子树递出,一直下去,每一次都需要先对当前节点的值访问,直到 node == null 时,左子树结束递出。当右子树此时也为  node == null 时,从叶子节点开始回归,回归到上一个节点的右子树。

代码实现如下:

假设该二叉树的图:

Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式),Java 数据结构与算法篇,数据结构,深度优先,算法,java

那么前序遍历打印的顺序为:124356

    //使用递归实现前序遍历
    public void preTraversalRecursion(MyBinaryTree node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        preTraversalRecursion(node.left);
        preTraversalRecursion(node.right);
    }

        

        3.2 用递归方式实现遍历 - 中序遍历

        具体思路为:向左子树递出,一直下去,直到 node == null 时,左子树结束递出。再来对当前节点的值进行访问,接着继续向着右子树递出,当右子树此时也为 node == null 时,从叶子节点开始回归,回归到上一个节点的右子树前先对当前节点的值进行访问。

代码实现如下:

假设该二叉树的图:

Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式),Java 数据结构与算法篇,数据结构,深度优先,算法,java

中序遍历打印的顺序为:421563

    //使用递归实现中序遍历
    public void middleTraversalRecursion(MyBinaryTree node) {

        if (node == null) {
            return;
        }

        middleTraversalRecursion(node.left);
        System.out.print(node.val + " ");
        middleTraversalRecursion(node.right);

    }

        相对于前序遍历,中序遍历就是将对节点的值的访问进行换了一下位置。先进行左子树递归,再来访问值,最后再右子树递归。

        3.3 用递归方式实现遍历 - 后序遍历

        具体思路为:向左子树递出,一直下去,直到 node == null 时,左子树结束递出。再接着继续向着右子树递出,再来对当前节点的值进行访问,当右子树此时也为 node == null 时,从叶子节点开始回归,回归到对当前节点的值进行访问。

代码实现如下:

假设该二叉树的图:

Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式),Java 数据结构与算法篇,数据结构,深度优先,算法,java

后续遍历打印顺序为:425631

    //使用递归实现后续遍历
    public void postTraversalRecursion(MyBinaryTree node) {
        if (node == null) {
            return;
        }
        postTraversalRecursion(node.left);
        postTraversalRecursion(node.right);
        System.out.print(node.val + " ");
    }

        4.0 用非递归方式实现二叉树遍历

        非递归实现前序遍历、中序遍历、后续遍历。用非递归实现这三种遍历方式的区别是访问的顺序不同,而前中后序它们所走的路线是一致的

假设该树的图片:

Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式),Java 数据结构与算法篇,数据结构,深度优先,算法,java

        具体思路为:先定义一个当前节点 curr 一开始指向根节点,还需要有一个栈的数据结构来存储数据。从根节点开始往后先左子树一直遍历下去 curr = curr.left ,每次都需要存储当前节点到栈中,直到 curr == null 时,说明了左子树已经遍历完毕了。此时需要栈弹出节点,来寻找 “来时的路”,弹出来的节点就是离当前节点最近的节点,在原路返回的时候,还要判断当前节点是否还有右子树,将弹出栈的节点的右子树赋值给 curr = tp.right 。如果右子树不为 null ,就会继续对当前节点的左子树遍历,且把当前节点压入栈中,方便记住 “来时的路”,;如果右子树不为 null ,继续把栈中的节点弹出,直到栈中没有了节点且 curr == null 时,因此整个二叉树就遍历结束了。

        4.1 用非递归方式实现遍历 - 前序遍历

        对于前序遍历来说,就是在来到下一个节点之前对当前节点的值先访问了。

代码如下:

    //非递归实现前序遍历
    public void preTraversal(MyBinaryTree node) {
        MyBinaryTree curr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                System.out.print(curr.val + " ");
                stack.push(curr);
                curr = curr.left;
            }else {
                MyBinaryTree tp = stack.pop();
                curr = tp.right;
            }
        }
        System.out.println();

    }

        4.2 用非递归方式实现遍历 - 中序遍历

        对于中序遍历来说,在栈弹出节点后,对弹出的节点进行访问。

代码如下:

    //非递归实现中序遍历
    public void middleTraversal(MyBinaryTree node) {
        MyBinaryTree curr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();
        while ( curr != null || !stack.isEmpty()) {

            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }else  {
                MyBinaryTree tp = stack.pop();
                System.out.print(tp.val + " ");
                curr = tp.right;
            }
        }
        System.out.println();

    }

        4.3 用非递归方式实现遍历 - 后序遍历

        相比前面两种前中后序遍历,后序遍历会多了一个判断,由于先访问完当前节点的左子树和右子树后,才能对当前节点的值进行访问,所以不能访问完左子树后,立马将当前节点弹出栈,还需要保留该节点,先对该节点的右节点进行访问完毕之后,再来访问该节点的值,最后就可以弹出栈了。需要先判断,当前节点的右子树为 null 时,可以弹出当前节点或者已经对当前节点的右节点访问完毕之后,也可以将当前节点弹出。

        那么如何来判断是否访问完毕当前节点的右子树了?

        可以用一个变量来标记,只需要判断最近弹出栈的节点是否为当前节点的右子树节点即可。

代码如下:

    //非递归实现后序遍历
    public void postTraversal(MyBinaryTree node) {
        MyBinaryTree crr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();
        MyBinaryTree pop = null;//最后一次弹栈元素
        while ( crr != null || !stack.isEmpty()) {
            if (crr != null) {
                stack.push(crr);
                crr = crr.left;
            }else {
                MyBinaryTree tp = stack.peek();
                if ( tp.right == null || tp.right == pop ) {
                    pop = stack.pop();
                    System.out.print(pop.val + " ");
                }else {
                    crr = tp.right;
                }

            }
        }
    }

        5.0 深度遍历的完整代码

import java.util.LinkedList;

public class MyBinaryTree {

    //指向左子树
    private MyBinaryTree left;
    //当前节点的值
    private int val;
    //指向右子树
    private MyBinaryTree right;

    //构造方法一:带一个值的参数
    public MyBinaryTree(int val) {
        this.val = val;
    }

    //构造方法二:带三个参数
    public MyBinaryTree(MyBinaryTree left, int val, MyBinaryTree right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }


    //使用递归实现前序遍历
    public void preTraversalRecursion(MyBinaryTree node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        preTraversalRecursion(node.left);
        preTraversalRecursion(node.right);
    }

    //使用递归实现中序遍历
    public void middleTraversalRecursion(MyBinaryTree node) {

        if (node == null) {
            return;
        }

        middleTraversalRecursion(node.left);
        System.out.print(node.val + " ");
        middleTraversalRecursion(node.right);

    }

    //使用递归实现后续遍历
    public void postTraversalRecursion(MyBinaryTree node) {
        if (node == null) {
            return;
        }
        postTraversalRecursion(node.left);
        postTraversalRecursion(node.right);
        System.out.print(node.val + " ");
    }


    //非递归实现前序遍历
    public void preTraversal(MyBinaryTree node) {
        MyBinaryTree curr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                System.out.print(curr.val + " ");
                stack.push(curr);
                curr = curr.left;
            }else {
                MyBinaryTree tp = stack.pop();
                curr = tp.right;
            }
        }
        System.out.println();

    }

    //非递归实现中序遍历
    public void middleTraversal(MyBinaryTree node) {
        MyBinaryTree curr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();
        while ( curr != null || !stack.isEmpty()) {

            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }else  {
                MyBinaryTree tp = stack.pop();
                System.out.print(tp.val + " ");
                curr = tp.right;
            }
        }
        System.out.println();

    }


    //非递归实现后序遍历
    public void postTraversal(MyBinaryTree node) {
        MyBinaryTree crr = node;
        LinkedList<MyBinaryTree> stack = new LinkedList<>();
        MyBinaryTree pop = null;//最后一次弹栈元素
        while ( crr != null || !stack.isEmpty()) {
            if (crr != null) {
                stack.push(crr);
                crr = crr.left;
            }else {
                MyBinaryTree tp = stack.peek();
                if ( tp.right == null || tp.right == pop ) {
                    pop = stack.pop();
                    System.out.print(pop.val + " ");
                }else {
                    crr = tp.right;
                }

            }
        }
    }

}

Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式),Java 数据结构与算法篇,数据结构,深度优先,算法,java文章来源地址https://www.toymoban.com/news/detail-752532.html

到了这里,关于Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包