文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java二叉树的遍历方式有哪些

2023-06-25 13:02

关注

本篇内容主要讲解“Java二叉树的遍历方式有哪些”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Java二叉树的遍历方式有哪些”吧!

二叉树的四种遍历方式:

四种遍历方式分别为:先序遍历、中序遍历、后序遍历、层序遍历。

Java二叉树的遍历方式有哪些

遍历之前,我们首先介绍一下,如何创建一个二叉树,在这里用的是先建左树在建右树的方法,

首先要声明结点TreeNode类,代码如下:

public class TreeNode {    public int data;    public TreeNode leftChild;    public TreeNode rightChild;    public TreeNode(int data){        this.data = data;    }}

再来创建一颗二叉树:

    public static TreeNode createBinaryTree(LinkedList<Integer> list){        TreeNode node = null;        if(list == null || list.isEmpty()){            return null;        }        Integer data = list.removeFirst();        if(data!=null){            node = new TreeNode(data);            node.leftChild = createBinaryTree(list);            node.rightChild = createBinaryTree(list);        }        return node;    }

接下来按照上面列的顺序一一讲解,

首先来看前序遍历,所谓的前序遍历就是先访问根节点,再访问左节点,最后访问右节点,

Java二叉树的遍历方式有哪些

如上图所示,前序遍历结果为:

ABDFECGHI

实现代码如下:

    public static void preOrderTraveral(TreeNode node){        if(node == null){            return;        }        System.out.print(node.data+" ");        preOrderTraveral(node.leftChild);        preOrderTraveral(node.rightChild);    }

再者就是中序遍历,所谓的中序遍历就是先访问左节点,再访问根节点,最后访问右节点,

Java二叉树的遍历方式有哪些

如上图所示,中序遍历结果为:

DBEFAGHCI

实现代码如下:

    public static void inOrderTraveral(TreeNode node){        if(node == null){            return;        }        inOrderTraveral(node.leftChild);        System.out.print(node.data+" ");        inOrderTraveral(node.rightChild);    }

最后就是后序遍历,所谓的后序遍历就是先访问左节点,再访问右节点,最后访问根节点。

Java二叉树的遍历方式有哪些

如上图所示,后序遍历结果为:

DEFBHGICA

实现代码如下:

    public static void postOrderTraveral(TreeNode node){        if(node == null){            return;        }        postOrderTraveral(node.leftChild);        postOrderTraveral(node.rightChild);        System.out.print(node.data+" ");    }

讲完上面三种递归的方法,下面再给大家讲讲非递归是如何实现前中后序遍历的

还是一样,先看非递归前序遍历

首先申请一个新的栈,记为stack;

声明一个结点treeNode,让其指向node结点;

如果treeNode的不为空,将treeNode的值打印,并将treeNode入栈,然后让treeNode指向treeNode的右结点,

重复步骤3,直到treenode为空;

然后出栈,让treeNode指向treeNode的右孩子

重复步骤3,直到stack为空.

实现代码如下:

public static void preOrderTraveralWithStack(TreeNode node){        Stack<TreeNode> stack = new Stack<TreeNode>();        TreeNode treeNode = node;        while(treeNode!=null || !stack.isEmpty()){            //迭代访问节点的左孩子,并入栈            while(treeNode != null){                System.out.print(treeNode.data+" ");                stack.push(treeNode);                treeNode = treeNode.leftChild;            }            //如果节点没有左孩子,则弹出栈顶节点,访问节点右孩子            if(!stack.isEmpty()){                treeNode = stack.pop();                treeNode = treeNode.rightChild;            }        }    }

中序遍历非递归,在此不过多叙述具体步骤了,

具体过程:

申请一个新栈,记为stack,申请一个变量cur,初始时令treeNode为头节点;

先把treeNode节点压入栈中,对以treeNode节点为头的整棵子树来说,依次把整棵树的左子树压入栈中,即不断令treeNode=treeNode.leftChild,然后重复步骤2;

不断重复步骤2,直到发现cur为空,此时从stack中弹出一个节点记为treeNode,打印node的值,并让treeNode= treeNode.right,然后继续重复步骤2;

当stack为空并且cur为空时结束。

public static void inOrderTraveralWithStack(TreeNode node){        Stack<TreeNode> stack = new Stack<TreeNode>();        TreeNode treeNode = node;        while(treeNode!=null || !stack.isEmpty()){            while(treeNode != null){                stack.push(treeNode);                treeNode = treeNode.leftChild;            }            if(!stack.isEmpty()){                treeNode = stack.pop();                System.out.print(treeNode.data+" ");                treeNode = treeNode.rightChild;            }        }    }

后序遍历非递归实现,后序遍历这里较前两者实现复杂一点,我们需要一个标记位来记忆我们此时节点上一个节点,具体看代码注释

public static void postOrderTraveralWithStack(TreeNode node){        Stack<TreeNode> stack = new Stack<TreeNode>();        TreeNode treeNode = node;        TreeNode lastVisit = null;   //标记每次遍历最后一次访问的节点        while(treeNode!=null || !stack.isEmpty()){//节点不为空,结点入栈,并且指向下一个左孩子            while(treeNode!=null){                stack.push(treeNode);                treeNode = treeNode.leftChild;            }            //栈不为空            if(!stack.isEmpty()){                //出栈                treeNode = stack.pop();                                if(treeNode.rightChild == null || treeNode.rightChild == lastVisit) {                    System.out.print(treeNode.data + " ");                    lastVisit = treeNode;                    treeNode  = null;                }else{                    stack.push(treeNode);                    treeNode = treeNode.rightChild;                }            }        }    }

最后再给大家介绍一下层序遍历

具体步骤如下:

首先申请一个新的队列,记为queue;

将头结点head压入queue中;

每次从queue中出队,记为node,然后打印node值,如果node左孩子不为空,则将左孩子入队;如果node的右孩子不为空,则将右孩子入队;

重复步骤3,直到queue为空。

实现代码如下:

public static void levelOrder(TreeNode root){        LinkedList<TreeNode> queue = new LinkedList<>();        queue.add(root);        while(!queue.isEmpty()){            root = queue.pop();            System.out.print(root.data+" ");            if(root.leftChild!=null) queue.add(root.leftChild);            if(root.rightChild!=null) queue.add(root.rightChild);        }    }

到此,相信大家对“Java二叉树的遍历方式有哪些”有了更深的了解,不妨来实际操作一番吧!这里是编程网网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯