专注Java教育14年 全国咨询/投诉热线:400-8080-105
动力节点LOGO图
始于2009,口口相传的Java黄埔军校
首页 学习攻略 Java学习 Java基础学习:java递归算法

Java基础学习:java递归算法

更新时间:2020-03-19 13:16:57 来源:动力节点 浏览1889次


  与数组和链表不同,二叉树有几种遍历方式。遍历算法大致分为深度优先和广度优先遍历算法,这取决于算法实际如何工作。顾名思义,深度优先在访问同级别兄弟之前先向二叉树纵深访问,而广度优先是先访问同一级别中的所有节点然后再进入下一级别,因此它也被称为级别顺序遍历。PreOrder和InOrder树遍历算法都是深度优先的,预序和中序算法之间的唯一区别是访问二叉树的根,左节点和右节点的顺序。


  InOrder遍历算法首先访问左节点,然后是root节点,最后是右节点。这与首先访问根的预序遍历不同。InOrder遍历的一个重要特性是,如果给定的二叉树是二叉搜索树,它将按排序顺序打印节点。


  请记住,如果左子树中的所有节点都低于root并且右子树中的所有节点都大于root,则二叉树称为二叉搜索树。


  在示例中,使用二叉搜索树来演示InOrder树遍历以排序顺序打印二叉树的节点,并分享了这个问题的递归和迭代解决方案。从面试的角度来看,这非常重要。即使递归解决方案更容易,占用更少的代码行,并且更具可读性,您也应该知道如何在没有Java递归的情况下遍历二叉树,以便在编程面试中做得更好。


  Java中InOrder遍历二叉树-递归

  

  由于二叉树是递归数据结构,因此递归是解决基于树的问题的最佳方法。以下是二叉树InOrder遍历的步骤:


  访问左节点


  访问root


  访问右节点


  要实现此算法,您可以使用InOrder遍历编写一个方法来遍历二叉树的所有节点,方法如下:


  在inOrder(TreeNode节点)中编写方法


  检查node==null,如果是,则返回,这是我们的基本情况。


  调用inOrder(node.left)以递归方式访问左子树


  打印节点的值


  调用inOrder(node.right)以递归方式遍历右子树。


  这将按照InOrder遍历打印二叉树的所有节点。如果二叉树是二叉搜索树,则树的所有节点将按排序顺序打印。这是一种在Java中实现InOrder算法的方法:


Java基础学习:java递归算法


  该方法是私有方法,因为它是通过另一个公共方法inorder()公开的,后者不需要来自客户端的参数。这是一个facade模式的例子,它使客户端的方法更简单。递归算法很容易理解,深入到左子树,直到找到叶节点。一旦找到,递归堆栈就开始展开,打印节点数据并开始探索右子树。


  Java中InOrder遍历二叉树-迭代


  您可以使用堆栈将递归的顺序算法转换为迭代的顺序算法。。没有递归的解决方案虽然不容易阅读,但也不是很难理解。我们从根和进程开始,直到当前节点或Stack不为空。我们开始从左子树推节点,直到到达叶节点。此时,我们pop()最后一个元素,打印它的值,并通过指定current=current.right开始探索右子树。这将一直持续到堆栈变空为止,此时,二叉树的所有元素都被访问,树遍历完成。


Java基础学习:java递归算法


  因为我们的二叉树是一个二叉搜索树,所以可以看到它们是按排序顺序打印的。


  

    以上就是动力节点Java培训机构小编介绍的“Java基础学习:java递归算法”的内容,希望对大家有帮助,如有疑问,请在线咨询,有专业老师随时为你服务。


提交申请后,顾问老师会电话与您沟通安排学习

免费课程推荐 >>
技术文档推荐 >>