什么是有序遍历算法? 该序遍历的三个流行的方式来遍历一个二叉树数据结构之一,其他两个分别是序和后序。在按顺序遍历算法期间,首先探索左子树,然后探索根,最后探索右子树上的节点。
您从root≤开始遍历,然后转到左侧节点,然后再次转到左侧节点,直到到达叶节点。此时,您将打印节点的值或将其标记为已访问并移至右侧的子树。继续相同的算法,直到访问了二叉树的所有节点。
该序遍历也被称为左节点右或左根右遍历或LNR遍历算法。
与preOrder算法相似,它也是深度优先算法,因为它在探索同级之前先探索二叉树的深度。由于它是基本的二叉树算法之一,因此在编程采访中非常流行。
这些遍历算法也是学习更高级的二叉树算法的基础,因此每个程序员都应该学习,理解和知道如何实现有序遍历和其他遍历算法。顺便说一句,如果您正准备进行编码面试,那么我强烈建议您阅读Andrei Neagoie的“编码面试大师:数据结构+算法”课程,它确实是瑰宝,您将学到很多东西。
用Java或任何编程语言实现inOrder遍历算法的最简单方法是使用递归。由于二叉树是递归的数据结构,因此递归是解决基于树的问题的自然选择。的inOrder()在二叉树类实现的方法中的逻辑使用递归遍历二叉树。
从Interview的角度来看,InOrder遍历非常重要,因为它也以排序的顺序打印二叉搜索树的节点,但前提是给定的树是二叉搜索树。
如果您还记得的话,在BST中,左子树中的节点的值低于根,而右子树中的节点的值高于根。InOrder遍历字面意思是IN顺序,我的意思是,节点是按顺序或排序顺序打印的。
顺便说一句,尽管这三种算法(预排序,有序排序和后排序)是流行的二叉树遍历算法,但它们并不是唯一的算法。您还可以使用其他广度优先的方式遍历二叉树,例如级别顺序遍历。
实现二叉树有序遍历的递归算法 InOrder遍历的递归算法非常简单。您只需要按照要访问树的顺序调用BinaryTree类的inOrder()方法即可。最重要的是包括基本情况,这是任何递归算法的关键。
例如,在此问题中,基本情况是您到达叶节点并且没有更多要探索的节点,此时递归开始逐渐减弱。以下是使用InOrder遍历遍历二叉树的确切步骤:
private void inOrder(TreeNode node) { if (node == null) { return; } inOrder(node.left); System.out.printf("%s ", node.data); inOrder(node.right); }
与最后一个示例中的preOrder()方法类似,还有另一种inOrder()方法将inOrder遍历公开给公众,并调用此私有方法来实际执行InOrder遍历。
这是编写需要输入的递归方法的标准方法,它使客户端可以更轻松地调用该方法。
public void inOrder() { inOrder(root); }
您可以看到我们从root开始,然后使用递归调用该inOrder() 方法node.left,这意味着我们将在左侧子node == null树上向下移动,直到命中,这意味着最后一个节点是叶节点。
此时,该inOrder()方法将返回并执行下一行,该行将打印node.data。之后,再次inOrder()使用node.right进行递归调用,这将再次启动相同的过程。
Java中二叉树的有序遍历 这是我们对Java中的顺序遍历算法的完整解决方案。该程序使用递归算法通过InOrder遍历打印二叉树所有节点的值。
正如我之前告诉您的,在此过程中,将首先打印左子树的有序遍历值,然后是根子树和右子树。
import java.util.Stack; /* * Java Program to traverse a binary search tree * using inorder traversal without recursion * and print all nodes in sorted order * In InOrder traversal first left node is visited, followed by root * and right node. * * input: * 40 * /\ * 20 50 * / \ \ * 10 30 60 * / / \ * 5 67 78 * * output: 5 10 20 30 40 50 60 67 78 */ public class Main { public static void main(String[] args) throws Exception { // construct the binary tree given in question BinaryTree bt = BinaryTree.create(); // traversing binary tree using InOrder traversal using recursion System.out .println("printing nodes of binary tree on InOrder using recursion"); bt.inOrder(); } } class BinaryTree { static class TreeNode { String data; TreeNode left, right; TreeNode(String value) { this.data = value; left = right = null; } } // root of binary tree TreeNode root; /** * traverse the binary tree on InOrder traversal algorithm */ public void inOrder() { inOrder(root); } private void inOrder(TreeNode node) { if (node == null) { return; } inOrder(node.left); System.out.printf("%s ", node.data); inOrder(node.right); } /** * Java method to create binary tree with test data * * @return a sample binary tree for testing */ public static BinaryTree create() { BinaryTree tree = new BinaryTree(); TreeNode root = new TreeNode("40"); tree.root = root; tree.root.left = new TreeNode("20"); tree.root.left.left = new TreeNode("10"); tree.root.left.left.left = new TreeNode("5"); tree.root.left.right = new TreeNode("30"); tree.root.right = new TreeNode("50"); tree.root.right.right = new TreeNode("60"); tree.root.left.right.left = new TreeNode("67"); tree.root.left.right.right = new TreeNode("78"); return tree; } }
输出 printing nodes of the binary tree on InOrder using recursion 5 10 20 30 67 78 40 50 60
printing nodes of the binary tree on InOrder using recursion
5 10 20 30 67 78 40 50 60
这就是如何使用递归在Java中实现二叉树的inOrder遍历的全部内容。您可以看到该代码与preOrder遍历非常相似,唯一的区别在于我们递归调用该方法的顺序。在这种情况下,我们inOrder(node.left)先调用然后打印节点的值。
值得记住的是,顺序遍历是一种深度优先算法,如果给定的二叉树是二叉搜索树,则按排序顺序打印树节点。
原文链接:http://codingdict.com