二叉树的非递归遍历是怎么样的?二叉树的非递归遍历也是采用的是递归的思想,拿前序遍历为例:先通过找到最左下角的节点,然后将其输出,并且对此节点的右子树再进行下一步的操作。
前序遍历:
public void pre_iteration(Node p) {if (p == null) return; Stack<Node> stack = new Stack<>();while (!stack.isEmpty() || p != null) {while (p != null) { System.out.println(p.val); stack.push(p); p = p.left; }if (!stack.isEmpty()) { p = stack.pop(); p = p.right; } } }
中序遍历:
public void in_iteration(Node p) {if (p == null) return; Stack<Node> stack = new Stack<>();while (!stack.isEmpty() || p != null) {while (p != null) { stack.push(p); p = p.left; }if (!stack.isEmpty()) { p = stack.pop(); System.out.println(p.val); p = p.right; } } }
后序遍历:(stack2是用来记载当前节点的右子树是否已经被遍历过)
public static void post_iteration(Node p) {if (p == null) return; Stack<Node> stack = new Stack<>(); Stack<Boolean> stack2 = new Stack<>();while (!stack.isEmpty() || p != null) {while (p != null) { stack.push(p); stack2.push(false); p = p.left; }while (!stack.isEmpty() && stack2.peek()) { System.out.println(stack.pop().val); stack2.pop(); }if (!stack.isEmpty()) { p = stack.peek().right; stack2.pop(); stack2.push(true); } } }
以上是关于二叉树的非递归遍历实例代码分享的详细内容。更多信息请关注PHP中文网其他相关文章!