Example code sharing about non-recursive traversal of binary trees-javaTutorial-php.cn

Example code sharing about non-recursive traversal of binary trees

零下一度

Release： 2017-07-18 17:56:53

Original

1681 people have browsed it

What is the non-recursive traversal of a binary tree? Non-recursive traversal of binary trees also uses recursive ideas. Take preorder traversal as an example: first find the node in the lower left corner, then output it, and then perform the next operation on the right subtree of this node.

Pre-order traversal:

 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;
            }
        }
    }Copy after login

Mid-order traversal:

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;
            }
        }
    }Copy after login

Post-order traversal: (stack2 is used to record Whether the right subtree of the current node has been traversed)

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);
            }
        }
    }Copy after login

The above is the detailed content of Example code sharing about non-recursive traversal of binary trees. For more information, please follow other related articles on the PHP Chinese website!