递归Post Order遍历算法

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

内容简介:后序遍历也是深度优先算法,在后顺序遍历中,首先访问左子树,然后访问右子树,最后打印节点或根的值。这就是为什么根值总是在后序遍历中最后打印的原因。与许多树算法一样,实现后序遍历的最简单方法是使用递归。实际上,如果您知道如何使用递归编写先序,则可以使用相同的算法稍作调整来实现后序遍历。使用递归进行后序遍历递归算法很容易理解,因为它与递归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>

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

查看所有标签

猜你喜欢:

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

深度探索Linux操作系统

深度探索Linux操作系统

王柏生 / 机械工业出版社 / 2013-10-15 / 89.00

《深度探索linux操作系统:系统构建和原理解析》是探索linux操作系统原理的里程碑之作,在众多的同类书中独树一帜。它颠覆和摒弃了传统的从阅读linux内核源代码着手学习linux操作系统原理的方式,而是基于实践,以从零开始构建一个完整的linux操作系统的过程为依托,指引读者在实践中去探索操作系统的本质。这种方式的妙处在于,让读者先从宏观上全面认清一个完整的操作系统中都包含哪些组件,各个组件的......一起来看看 《深度探索Linux操作系统》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器