递归Post Order遍历算法

栏目: 编程工具 · 发布时间: 6年前

内容简介：后序遍历也是深度优先算法，在后顺序遍历中，首先访问左子树，然后访问右子树，最后打印节点或根的值。这就是为什么根值总是在后序遍历中最后打印的原因。与许多树算法一样，实现后序遍历的最简单方法是使用递归。实际上，如果您知道如何使用递归编写先序，则可以使用相同的算法稍作调整来实现后序遍历。使用递归进行后序遍历递归算法很容易理解，因为它与递归preOrder和递归inOrder遍历完全相似。唯一不同的是访问或遍历左子树，右子树和根的顺序，如下面的代码片段所示。

后序遍历也是深度优先算法，在后顺序遍历中，首先访问左子树，然后访问右子树，最后打印节点或根的值。这就是为什么根值总是在后序遍历中最后打印的原因。与许多树算法一样，实现后序遍历的最简单方法是使用递归。实际上，如果您知道如何使用递归编写先序，则可以使用相同的算法稍作调整来实现后序遍历。

使用递归进行后序遍历

递归算法很容易理解，因为它与递归preOrder和递归inOrder遍历完全相似。唯一不同的是访问或遍历左子树，右子树和根的顺序，如下面的代码片段所示。

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

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

在后序遍历中打印二叉树的 Java 程序

这里是一个完整的Java程序，用于在后序遍历中打印二叉树的所有节点。

先创建一个名为BialayTrand的类来表示Java中的二叉树。此类有一个静态嵌套类来表示树节点，称为TreeNode。这类似于map.entry类，用于表示哈希表中的条目。该类只保留对root的引用，Treenode负责照顾左右子项。

这个类有两个方法postOrder（）和postOrder（TreeNode root），第一个是public，第二个是private。实际遍历是在第二种方法中完成的，但由于root是类内部的，客户端无法访问root，因此创建了postOrder（）方法来调用私有方法。这是实现递归算法的常用技巧。

这也使您可以在不影响客户端的情况下更改算法。我们可以将递归算法改为迭代算法，客户端仍然会调用post order方法而不知道现在迭代算法已经到位了。

按后序打印二叉树节点

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

<font><i>/*
 * Java Program to traverse a binary tree 
 * using postOrder traversal without recursion. 
 * In postOrder traversal first left subtree is visited, followed by right subtree
 * and finally data of root or current node is printed.
 * 
 * input:
 *     55
 *    /  \
 *   35   65
 *   / \    \
 *  25  45   75
 *  /  /  \
 * 15 87  98
 * 
 * output: 15 25 45 35 87 98 75 65 55 
 */</i></font><font>

<b>public</b> <b>class</b> Main {

  <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 post-order traversal using recursion</i></font><font>
    System.out.println(</font><font>"printing nodes of a binary tree on post order in Java"</font><font>);

    bt.postOrder();

  }

}

<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 post order traversal algorithm
   */</i></font><font>
  <b>public</b> <b>void</b> postOrder() {
    postOrder(root);
  }

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

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

  </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>"55"</font><font>);
    tree.root = root;
    tree.root.left = <b>new</b> TreeNode(</font><font>"35"</font><font>);
    tree.root.left.left = <b>new</b> TreeNode(</font><font>"25"</font><font>);
    tree.root.left.left.left = <b>new</b> TreeNode(</font><font>"15"</font><font>);

    tree.root.left.right = <b>new</b> TreeNode(</font><font>"45"</font><font>);
    tree.root.right = <b>new</b> TreeNode(</font><font>"65"</font><font>);
    tree.root.right.right = <b>new</b> TreeNode(</font><font>"75"</font><font>);
    tree.root.right.right.left = <b>new</b> TreeNode(</font><font>"87"</font><font>);
    tree.root.right.right.right = <b>new</b> TreeNode(</font><font>"98"</font><font>);

    <b>return</b> tree;
  }

}

Output
printing nodes of a binary tree on post order in Java
15 25 87 98 45 35 75 65 55  
</font>

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

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

How to Build a Billion Dollar App

George Berkowski / Little, Brown Book Group / 2015-4-1 / USD 24.95

Apps have changed the way we communicate, shop, play, interact and travel and their phenomenal popularity has presented possibly the biggest business opportunity in history. In How to Build a Billi......一起来看看《How to Build a Billion Dollar App》这本书的介绍吧!

码农工具

MD5 加密

MD5 加密工具

HEX HSV 转换工具

HEX HSV 互换工具