二叉树递归非递归遍历算法整理

一、二叉树前序遍历

• 1 前序递归遍历

    public void preOrder(BinaryNode root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

• 2.前序非递归遍历

    public void preOrderTraverse(BinaryNode root) {
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode node = root;
        while (node != null || !stack.empty()) {
            while (node != null) {
                stack.push(node);
                System.out.print(node.data + " ");
                node = node.left;
            }
            if (!stack.empty()) {
                node = stack.pop();
                node = node.right;
            }
        }
    }

一、二叉树中序遍历

• 2.中序递归遍历

    public void inOrder(BinaryNode root) {
        if (root != null) {
            inOrder(root.left);
            System.out.print(root.data + " ");
            inOrder(root.right);
        }
    }

• 1.中序非递归遍历

    public void inOrderTraverse(BinaryNode root) {
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode node = root;
        while (node != null || !stack.empty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.empty()) {
                node = stack.pop();
                System.out.print(node.data + " ");
                node = node.right;
            }
        }
    }

一、二叉树后序遍历

• 1.后序递归遍历

    public void postOrder(BinaryNode root) {
        if (root != null) {
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.data + " ");
        }
    }

• 2.后序非递归遍历

    public void postOrderTraverse(BinaryNode root) {
        Stack<BinaryNode> stack1 = new Stack<>();
        Stack<BinaryNode> stack2 = new Stack<>();
        stack1.push(root);
        while (!stack1.empty()) {
            BinaryNode node = stack1.pop();
            stack2.push(node);
            if (node.left != null) {
                stack1.push(node.left);
            }
            if (node.right != null) {
                stack1.push(node.right);
            }
        }
        while (!stack2.empty()) {
            BinaryNode node = stack2.pop();
            System.out.print(node.data + " ");
        }
    }

四、二叉树层次遍历

    public void level(BinaryNode root) {
        ConcurrentLinkedQueue<BinaryNode> queue = new ConcurrentLinkedQueue<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            BinaryNode node = queue.peek();
            queue.remove();
            System.out.print(node.data + " ");
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }