后序遍历也是深度优先算法,在后顺序遍历中,首先访问左子树,然后访问右子树,最后打印节点或根的值。这就是为什么根值总是在后序遍历中最后打印的原因。与许多树算法一样,实现后序遍历的最简单方法是使用递归。实际上,如果您知道如何使用递归编写先序,则可以使用相同的算法稍作调整来实现后序遍历。
使用递归进行后序遍历
递归算法很容易理解,因为它与递归preOrder和递归inOrder遍历完全相似。 唯一不同的是访问或遍历左子树,右子树和根的顺序,如下面的代码片段所示。
private void postOrder(TreeNode node) { if (node == null) { return; }
postOrder(node.left); postOrder(node.right); System.out.printf("%s ", node.data); }
|
在后序遍历中打印二叉树的Java程序
这里是一个完整的Java程序,用于在后序遍历中打印二叉树的所有节点。
先创建一个名为BialayTrand的类来表示Java中的二叉树。此类有一个静态嵌套类来表示树节点,称为TreeNode。这类似于map.entry类,用于表示哈希表中的条目。该类只保留对root的引用,Treenode负责照顾左右子项。
这个类有两个方法postOrder()和postOrder(TreeNode root),第一个是public,第二个是private。实际遍历是在第二种方法中完成的,但由于root是类内部的,客户端无法访问root,因此创建了postOrder()方法来调用私有方法。这是实现递归算法的常用技巧。
这也使您可以在不影响客户端的情况下更改算法。我们可以将递归算法改为迭代算法,客户端仍然会调用post order方法而不知道现在迭代算法已经到位了。
按后序打印二叉树节点
import java.util.Stack;
/* * 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 */
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 post-order traversal using recursion System.out.println("printing nodes of a binary tree on post order in Java");
bt.postOrder();
}
}
class BinaryTree { static class TreeNode { String data; TreeNode left, right;
TreeNode(String value) { this.data = value; left = right = null; }
boolean isLeaf() { return left == null ? right == null : false; }
}
// root of binary tree TreeNode root;
/** * traverse the binary tree on post order traversal algorithm */ public void postOrder() { postOrder(root); }
private void postOrder(TreeNode node) { if (node == null) { return; }
postOrder(node.left); postOrder(node.right); System.out.printf("%s ", node.data); }
/** * 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("55"); tree.root = root; tree.root.left = new TreeNode("35"); tree.root.left.left = new TreeNode("25"); tree.root.left.left.left = new TreeNode("15");
tree.root.left.right = new TreeNode("45"); tree.root.right = new TreeNode("65"); tree.root.right.right = new TreeNode("75"); tree.root.right.right.left = new TreeNode("87"); tree.root.right.right.right = new TreeNode("98");
return tree; }
}
Output printing nodes of a binary tree on post order in Java 15 25 87 98 45 35 75 65 55
|