内容简介：后序遍历也是深度优先算法，在后顺序遍历中，首先访问左子树，然后访问右子树，最后打印节点或根的值。这就是为什么根值总是在后序遍历中最后打印的原因。与许多树算法一样，实现后序遍历的最简单方法是使用递归。实际上，如果您知道如何使用递归编写先序，则可以使用相同的算法稍作调整来实现后序遍历。使用递归进行后序遍历递归算法很容易理解，因为它与递归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>
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- 算法 | 广度优先遍历BFS
- 从JS遍历DOM树学算法
- 数组常见的遍历循环方法、数组的循环遍历的效率对比
- C++拾趣——STL容器的插入、删除、遍历和查找操作性能对比（Windows VirtualStudio）——遍历和删除
- Js遍历数组总结
- 遍历
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
