Java中二叉树的PreOrder遍历——递归与迭代实例

栏目: 数据库 · 发布时间: 5年前

内容简介：与只能线性遍历的链表和数组不同，遍历二叉树有几种方法。树遍历算法主要分为深度优先和广度优先两部分。顾名思义，在深度优先的情况下，在访问下一个同级树之前，树向下（向深度）遍历，二叉树的PreOrder，InOrder和PostOrder遍历实际上是深度优先遍历。在广度优先上，树的整个宽度在移到下一个级别之前被遍历，因此它也被称为级别顺序遍历。还有其他遍历二叉树的算法，例如蒙特卡洛树搜索，它集中于分析最优的移动，但先序、后序和顺序遍历是在Java中遍历二叉树的最流行的方法。它们也是初级和中级阶段最流行的数据结构

与只能线性遍历的链表和数组不同，遍历二叉树有几种方法。树遍历算法主要分为深度优先和广度优先两部分。顾名思义，在深度优先的情况下，在访问下一个同级树之前，树向下（向深度）遍历，二叉树的PreOrder，InOrder和PostOrder遍历实际上是深度优先遍历。在广度优先上，树的整个宽度在移到下一个级别之前被遍历，因此它也被称为级别顺序遍历。还有其他遍历二叉树的算法，例如蒙特卡洛树搜索，它集中于分析最优的移动，但先序、后序和顺序遍历是在 Java 中遍历二叉树的最流行的方法。它们也是初级和中级阶段最流行的数据结构和算法问题。

当你以深度优先的方式遍历一棵树时，你有三个选择，例如根、左子树和右子树。根据您访问这三个目录的顺序，会产生不同的树遍历算法。在PreOrder遍历中，首先访问根目录，然后访问左子树，然后访问右子树，因此它也被称为NLR（nod left right）算法。

对于那些不知道遍历二叉树的意义的人，访问二叉树的所有节点是一个过程。它还用于搜索二叉树中的节点。我还建议你读一本关于数据结构和算法的好书，例如《算法导论》，了解更多关于二叉树和各种树算法的知识。

您可以使用递归或迭代在Java中实现二叉树PreOrder遍历算法。正如我在文章中提到的，在二叉树中查找叶节点时，大多数基于树的算法都可以使用递归轻松实现，因为二叉树是一种递归数据结构。

在本文中，我将展示如何使用Java中的递归和迭代，以及PreOrder遍历来编写程序，遍历二叉树。

如何使用递归在Java中遍历PreOrder中的二叉树

由于二叉树是递归数据结构（为什么？因为在删除节点后，结构的其余部分也是二叉树，例如左右二叉树，类似于链表，也是递归数据结构），自然使用递归算法解决基于树的问题是比较好的选择。

PreOrder遍历算法的步骤

1. 访问节点

2. 访问左子树

3. 访问右子树

通过打印节点的值，然后递归调用具有左子树和右子树的同一pre order（）方法，可以很容易地使用递归实现PreOrder遍历算法，如下程序所示：

<b>private</b> <b>void</b> preOrder(TreeNode node) {
    <b>if</b> (node == <b>null</b>) {
      <b>return</b>;
    }
    System.out.printf(<font>"%s "</font><font>, node.data);
    preOrder(node.left);
    preOrder(node.right);
  }
</font>

你可以看到它只是几行代码。这里最重要的是基本情况，递归算法从这里开始展开。这里node == null是我们的基本情况，因为你现在已经到达了叶节点，现在不能再深入了，是时候回溯到另一条路径了。递归算法也非常易读的，您可以看到，首先打印节点值，然后访问左子树，最后是右子树。建议阅读Robert Sedgewick的Algorithms第4版，以了解更多关于Java的回归算法。

在Java中不使用递归的二叉树PreOrer遍历

将递归算法转换为迭代算法的一种简单方法是使用堆栈数据结构。如果您还记得，递归隐式地使用一个堆栈，当您的算法达到基本情况时，该堆栈将开始展开。您可以使用外部堆栈替换该隐式堆栈，并在不实际使用递归的情况下解决问题。这也更安全，因为现在你的代码不会抛出StackOverFlowError，即使对于巨大的二叉搜索树也是如此，但它们通常不像递归树一样简洁易读。无论如何，这里是在Java中不使用递归的PreOrer算法。

<b>public</b> <b>void</b> preOrderWithoutRecursion() {
    Stack<TreeNode> nodes = <b>new</b> Stack<>();
    nodes.push(root);

    <b>while</b> (!nodes.isEmpty()) {
      TreeNode current = nodes.pop();
      System.out.printf(<font>"%s "</font><font>, current.data);

      <b>if</b> (current.right != <b>null</b>) {
        nodes.push(current.right);
      }
      <b>if</b> (current.left != <b>null</b>) {
        nodes.push(current.left);
      }
    }
  }
</font>

老实说，这个代码很容易理解，但在算法的中间有一个棘手的部分，即在左子树之前必须推右子树，这与递归算法不同。我们首先推动栈中的根来开始遍历，然后使用while循环遍历栈，直到栈为空。在每次迭代中，我们都会弹出元素来访问它。

如果您还记得，stack是一个后进先出的数据结构，因为我们想按照node left right的顺序访问树，所以我们先推右node，然后推左node，这样在下一个迭代中，当我们从stack中弹出（）时，我们得到左子树。通过这种方式，二叉树在PreOrer遍历中被遍历。如果更改插入堆栈的顺序，将在后顺序遍历中遍历树。参见ThomasS.Cormen的算法简介，了解更多关于栈数据结构及其在将递归算法转换为迭代算法中的作用的信息。

在PreOrder算法中遍历二叉树的Java程序

这是我们在PreOrder中遍历给定二叉树的完整程序。在这个程序中，您将找到递归和迭代的PreOrer遍历算法的实现。您可以从命令行或Eclipse IDE运行此程序以测试并了解树遍历的工作原理。

这个程序有一个名为BinaryTree的类，它代表一个BinaryTree，记住它不是二叉搜索树，因为TreeNode没有实现Comparable或Comparator接口。 TreNode类表示二叉树中的节点，它包含数据部分和对左右子节点的两个引用。

我在BinaryTree类中创建了一个preOrder（）方法来按预先遍历树。这是一个公共方法，但实际工作是由另一个私有方法完成的，该方法是此方法的重载版本。该方法接受TreeNode。类似地，还有另一个名为preOrderWithoutRecursion（）的方法来实现二叉树的迭代PreOrer遍历。

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

<font><i>/*
 * Java Program to traverse a binary tree using PreOrder traversal. 
 * In PreOrder the node value is printed first, followed by visit
 * to left and right subtree. 
 * input:
 *     1
 *    / \
 *   2   5
 *  / \   \
 * 3   4   6
 * 
 * output: 1 2 3 4 5 6 
 */</i></font><font>
<b>public</b> <b>class</b> PreOrderTraversal {

  <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 = <b>new</b> BinaryTree();
    BinaryTree.TreeNode root = <b>new</b> BinaryTree.TreeNode(</font><font>"1"</font><font>);
    bt.root = root;
    bt.root.left = <b>new</b> BinaryTree.TreeNode(</font><font>"2"</font><font>);
    bt.root.left.left = <b>new</b> BinaryTree.TreeNode(</font><font>"3"</font><font>);

    bt.root.left.right = <b>new</b> BinaryTree.TreeNode(</font><font>"4"</font><font>);
    bt.root.right = <b>new</b> BinaryTree.TreeNode(</font><font>"5"</font><font>);
    bt.root.right.right = <b>new</b> BinaryTree.TreeNode(</font><font>"6"</font><font>);

    </font><font><i>// printing nodes in recursive preOrder traversal algorithm</i></font><font>
    bt.preOrder();

    System.out.println();

    </font><font><i>// traversing binary tree in PreOrder without using recursion</i></font><font>
    bt.preOrderWithoutRecursion();

  }

}

<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>/**
   * Java method to print tree nodes in PreOrder traversal
   */</i></font><font>
  <b>public</b> <b>void</b> preOrder() {
    preOrder(root);
  }

  </font><font><i>/**
   * traverse the binary tree in PreOrder
   * 
   * @param node
   *          - starting node, root
   */</i></font><font>
  <b>private</b> <b>void</b> preOrder(TreeNode node) {
    <b>if</b> (node == <b>null</b>) {
      <b>return</b>;
    }
    System.out.printf(</font><font>"%s "</font><font>, node.data);
    preOrder(node.left);
    preOrder(node.right);
  }

  </font><font><i>/**
   * Java method to visit tree nodes in PreOrder traversal without recursion.
   */</i></font><font>
  <b>public</b> <b>void</b> preOrderWithoutRecursion() {
    Stack<TreeNode> nodes = <b>new</b> Stack<>();
    nodes.push(root);

    <b>while</b> (!nodes.isEmpty()) {
      TreeNode current = nodes.pop();
      System.out.printf(</font><font>"%s "</font><font>, current.data);

      <b>if</b> (current.right != <b>null</b>) {
        nodes.push(current.right);
      }
      <b>if</b> (current.left != <b>null</b>) {
        nodes.push(current.left);
      }
    }
  }

}

Output
1 2 3 4 5 6 
1 2 3 4 5 6 
</font>

这就是关于如何在Java中以PreOrder遍历二叉树的问题。我们已经了解了如何使用递归和迭代（例如使用堆栈数据结构）来实现PreOrder遍历算法。作为一名计算机工程师或程序员，您应该了解基本的树遍历算法，例如先顺序、顺序和后顺序遍历。

无论如何，要记住在先排序遍历中，节点值在访问左、右子树之前被打印出来。它也是一种深度优先遍历算法，遍历顺序为 node-left-right,，因此又称为NLR算法。

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持码农网