转载

Java中用递归和迭代实现二叉树的中序（ InOrder )遍历

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

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

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

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

Java中InOrder遍历二叉树 - 递归

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

1）访问左节点

2）访问root

3）访问右节点

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

在inOrder（TreeNode节点）中编写方法

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

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

打印节点的值

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

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

<b>private</b> <b>void</b> inOrder(TreeNode node) {
    <b>if</b> (node == <b>null</b>) {
      <b>return</b>;
    }

    inOrder(node.left);
    System.out.printf(<font>"%s "</font><font>, node.data);
    inOrder(node.right);
  }
</font>

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

Java中InOrder遍历二叉树 - 迭代

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

  4
   / /
  2   5
 / /   /
1   3   6 

<b>public</b> <b>void</b> inOrderWithoutRecursion() {
    Stack nodes = <b>new</b> Stack<>();
    TreeNode current = root;

    <b>while</b> (!nodes.isEmpty() || current != <b>null</b>) {

      <b>if</b> (current != <b>null</b>) {
        nodes.push(current);
        current = current.left;
      } <b>else</b> {
        TreeNode node = nodes.pop();
        System.out.printf(<font>"%s "</font><font>, node.data);
        current = node.right;
      }

    }
  }

Output
1 2 3 4 5 6 
</font>

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

Java中使用InOrder算法遍历二叉树

这是我们在Java中使用InOrder算法遍历二叉树的完整程序。类似于我们之前看到的preOrder示例，唯一的区别是root的访问顺序不是首先而是其次。递归算法很简单，但迭代算法有点难以理解。您必须记住，堆栈是一个后进先出的数据结构，您先推的节点将最后弹出。因为您需要按左--右的顺序访问节点，所以您必须先推左树的节点，直到到达叶节点。然后打印该值并开始访问右子树。

我们使用了相同的BinaryTree和TreeNode类，在早期的基于树的问题（例如计算叶节点）中，它用于表示二叉树。二叉树是常规二叉树，TreeNode表示二叉树中的节点。

<b>import</b> java.util.Stack;

<font><i>/*
 * Java Program to traverse a binary tree 
 * using inorder traversal without recursion. 
 * In InOrder traversal first left node is visited, followed by root
 * and right node.
 * 
 * input:
 *     4
 *    / /
 *   2   5
 *  / /   /
 * 1   3   6
 * 
 * output: 1 2 3 4 5 6 
 */</i></font><font>

<b>public</b> <b>class</b> InOrderTraversal {

  <b>public</b> <b>static</b> <b>void</b> main(String args) throws Exception {

    </font><font><i>// construct the binary tree given in question</i></font><font>
    BinaryTree bt = BinaryTree.create();

    </font><font><i>// traversing binary tree using InOrder traversal using recursion</i></font><font>
    System.out
        .println(</font><font>"printing nodes of a binary tree on InOrder using recursion"</font><font>);

    bt.inOrder();

    System.out.println(); </font><font><i>// insert new line</i></font><font>

    </font><font><i>// traversing binary tree on InOrder traversal without recursion</i></font><font>
    System.out
        .println(</font><font>"printing nodes of binary tree on InOrder using iteration"</font><font>);
    bt.inOrderWithoutRecursion();
  }

}

<b>class</b> BinaryTree {
  <b>static</b> <b>class</b> TreeNode {
    String data;
    TreeNode left, right;

    TreeNode(String value) {
      <b>this</b>.data = value;
      left = right = <b>null</b>;
    }

    <b>boolean</b> isLeaf() {
      <b>return</b> left == <b>null</b> ? right == <b>null</b> : false;
    }

  }

  </font><font><i>// root of binary tree</i></font><font>
  TreeNode root;

  </font><font><i>/**
   * traverse the binary tree on InOrder traversal algorithm
   */</i></font><font>
  <b>public</b> <b>void</b> inOrder() {
    inOrder(root);
  }

  <b>private</b> <b>void</b> inOrder(TreeNode node) {
    <b>if</b> (node == <b>null</b>) {
      <b>return</b>;
    }

    inOrder(node.left);
    System.out.printf(</font><font>"%s "</font><font>, node.data);
    inOrder(node.right);
  }

  <b>public</b> <b>void</b> inOrderWithoutRecursion() {
    Stack nodes = <b>new</b> Stack<>();
    TreeNode current = root;

    <b>while</b> (!nodes.isEmpty() || current != <b>null</b>) {

      <b>if</b> (current != <b>null</b>) {
        nodes.push(current);
        current = current.left;
      } <b>else</b> {
        TreeNode node = nodes.pop();
        System.out.printf(</font><font>"%s "</font><font>, node.data);
        current = node.right;
      }

    }
  }

  </font><font><i>/**
   * Java method to create binary tree with test data
   * 
   * @return a sample binary tree for testing
   */</i></font><font>
  <b>public</b> <b>static</b> BinaryTree create() {
    BinaryTree tree = <b>new</b> BinaryTree();
    TreeNode root = <b>new</b> TreeNode(</font><font>"4"</font><font>);
    tree.root = root;
    tree.root.left = <b>new</b> TreeNode(</font><font>"2"</font><font>);
    tree.root.left.left = <b>new</b> TreeNode(</font><font>"1"</font><font>);

    tree.root.left.right = <b>new</b> TreeNode(</font><font>"3"</font><font>);
    tree.root.right = <b>new</b> TreeNode(</font><font>"5"</font><font>);
    tree.root.right.right = <b>new</b> TreeNode(</font><font>"6"</font><font>);

    <b>return</b> tree;
  }

}

Output
printing nodes of a binary tree on InOrder using recursion
1 2 3 4 5 6 
printing nodes of a binary tree on InOrder using iteration
1 2 3 4 5 6 
</font>

这就是如何使用InOrder遍历算法访问二叉树的所有节点。正如我之前所说，InOrder是一种深度优先遍历算法，在访问root之前首先探索左子树，最后探索右子树，因此它也被称为LNR（左节点右）算法。 inorder遍历还有一个独特的属性，如果给定的二叉树是二叉搜索树，它会按排序顺序打印节点。因此，如果必须按BST的排序顺序打印所有节点，则可以使用此算法。

原文 https://www.jdon.com/51890

正文到此结束