首页 > 代码库 > Java数据结构系列之——树(5):二叉树的后序遍历的递归与非递归实现
Java数据结构系列之——树(5):二叉树的后序遍历的递归与非递归实现
package tree.binarytree; import java.util.Stack; /** * 二叉树后序遍历的递归与非递归实现 * * @author wl * */ public class BitreePostOrder { // 后序遍历的递归实现 public static void biTreePostOrderByRecursion(BiTreeNode root) { if (root == null) { return; } biTreePostOrderByRecursion(root.leftNode); biTreePostOrderByRecursion(root.rightNode); System.out.println(root.data); } /** * 后序遍历的非递归实现 要保证根节点在左孩子和右孩子访问之后才能访问,因此,对于任一结点current,先将其入栈,如果current不存在左孩子 * 和右孩子,则可以直接访问它;或者current存在左孩子或者右孩子,但是其左孩子和右孩子都已近访问过了,则同样可以直接 * 访问改结点。若非上述两种情况,则将current的右孩子和左孩子(注意是先右孩子后左孩子)依次入栈。这样就保证了每次取 * 栈顶元素的时候,左孩子在右孩子前被访问,左孩子和右孩子都在根结点前面被访问 * * @param root */ public static void biTreePostOrder(BiTreeNode root) { Stack<BiTreeNode> stack = new Stack<BiTreeNode>();// 栈,用于存放二叉树的结点 BiTreeNode current = root;// 当前结点 BiTreeNode pre = null;// 前一次被访问的结点 stack.push(root); while (!stack.empty()) { current = stack.peek(); if ((current.leftNode == null && current.rightNode == null) || (pre != null && (pre == current.leftNode || pre == current.rightNode))) { System.out.println(current.data); stack.pop(); pre = current; } else { if (current.rightNode != null) { stack.push(current.rightNode); } if (current.leftNode != null) { stack.push(current.leftNode); } } } } }
Java数据结构系列之——树(5):二叉树的后序遍历的递归与非递归实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。