Java中的有序遍历算法

什么是有序遍历算法？ 该序遍历的三个流行的方式来遍历一个二叉树数据结构之一，其他两个分别是序和后序。在按顺序遍历算法期间，首先探索左子树，然后探索根，最后探索右子树上的节点。

您从root≤开始遍历，然后转到左侧节点，然后再次转到左侧节点，直到到达叶节点。此时，您将打印节点的值或将其标记为已访问并移至右侧的子树。继续相同的算法，直到访问了二叉树的所有节点。

该序遍历也被称为左节点右或左根右遍历或LNR遍历算法。

与preOrder算法相似，它也是深度优先算法，因为它在探索同级之前先探索二叉树的深度。由于它是基本的二叉树算法之一，因此在编程采访中非常流行。

这些遍历算法也是学习更高级的二叉树算法的基础，因此每个程序员都应该学习，理解和知道如何实现有序遍历和其他遍历算法。顺便说一句，如果您正准备进行编码面试，那么我强烈建议您阅读Andrei Neagoie的“编码面试大师：数据结构+算法”课程，它确实是瑰宝，您将学到很多东西。

用Java或任何编程语言实现inOrder遍历算法的最简单方法是使用递归。由于二叉树是递归的数据结构，因此递归是解决基于树的问题的自然选择。的inOrder()在二叉树类实现的方法中的逻辑使用递归遍历二叉树。

从Interview的角度来看，InOrder遍历非常重要，因为它也以排序的顺序打印二叉搜索树的节点，但前提是给定的树是二叉搜索树。

如果您还记得的话，在BST中，左子树中的节点的值低于根，而右子树中的节点的值高于根。InOrder遍历字面意思是IN顺序，我的意思是，节点是按顺序或排序顺序打印的。

顺便说一句，尽管这三种算法（预排序，有序排序和后排序）是流行的二叉树遍历算法，但它们并不是唯一的算法。您还可以使用其他广度优先的方式遍历二叉树，例如级别顺序遍历。

实现二叉树有序遍历的递归算法 InOrder遍历的递归算法非常简单。您只需要按照要访问树的顺序调用BinaryTree类的inOrder（）方法即可。最重要的是包括基本情况，这是任何递归算法的关键。

例如，在此问题中，基本情况是您到达叶节点并且没有更多要探索的节点，此时递归开始逐渐减弱。以下是使用InOrder遍历遍历二叉树的确切步骤：

访问左节点
打印根的值
访问正确的节点，这是在Java中使用递归实现该算法的示例代码：

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

这就是如何使用递归在Java中实现二叉树的inOrder遍历的全部内容。您可以看到该代码与preOrder遍历非常相似，唯一的区别在于我们递归调用该方法的顺序。在这种情况下，我们inOrder(node.left)先调用然后打印节点的值。

值得记住的是，顺序遍历是一种深度优先算法，如果给定的二叉树是二叉搜索树，则按排序顺序打印树节点。

原文链接：http://codingdict.com

Java中的有序遍历算法

热门标签