Java 二叉树递归与非递归所有遍历

二叉树的递归与非递归遍历

/**
 * @ClassName: tree
 * @Description: TODO
 * @Author: Joker
 * @Date: 2020/3/12
 */


class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int data) {
        this.val = data;
    }
}

public class TreeBinary {

    //暴力构建一颗二叉树
    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(5);
        TreeNode n2 = new TreeNode(6);
        TreeNode n3 = new TreeNode(7);
        TreeNode n4 = new TreeNode(8);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = null;
        n3.left = null;
        n3.right = null;
        n4.left = null;
        n4.right = null;
        System.out.println("先序递归");
        preOrderRecur(n1);
        System.out.println("中序递归");
        inOrderRecur(n1);
        System.out.println("后序递归");
        posOrderRecur(n1);

        preOrderUnRecur(n1);
        inOrderUnRecur(n1);
        posOrderUnRecur(n1);
    }


    //先序递归遍历
    public static void preOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val + " ");
        preOrderRecur(root.left);
        preOrderRecur(root.right);
    }

    //中序递归遍历
    public static void inOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        preOrderRecur(root.left);
        System.out.println(root.val + " ");
        preOrderRecur(root.right);
    }

    //后序递归遍历
    public static void posOrderRecur(TreeNode root) {
        if (root == null) {
            return;
        }
        preOrderRecur(root.left);
        preOrderRecur(root.right);
        System.out.println(root.val + " ");
    }


   /***
     * 先序遍历非递归
     * 1、申请一个新的栈 stack 。将头节点 root 压入 stack 中。
     * 
     * 2、从 stack 中弹出栈顶节点，记为 cur ,然后打印 cur 节点的值，
     *    再将节点 cur 的右孩子（不为空的话）压入 stack 中，
     *    最后将 cur 的左孩子（不为空的话）压入 stack 中。
     * 
     * 3、不断重复步骤 2，直到 stack 为空，全部过程结束。
     * @param root
     */
    public static void preOrderUnRecur(TreeNode root) {
        System.out.println("非递归先序递归");
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                root = stack.pop();
                System.out.println(root.val + " ");
                if (root.right != null) {
                    stack.push(root.right);
                }
                if (root.left != null) {
                    stack.push(root.left);
                }
            }
        }
    }

    /***
     * 中序非递归遍历
     * 1、申请一个新的栈 stack 。初始时，令变量 cur = head。
     * 
     * 2、先把 cur 节点压入栈中，对以 cur 节点为头的整棵树来说，
     *    依次把左边界压入栈中，即不停的令 cur = cur.left，然后重复步骤 2
     * 
     * 3、不断重复步骤 2 ，直到发现 cur 为空。此时从 stack 中弹出一个节点，
     *    记为 node 。打印 node 的值，并且让 cur = cur.right, 然后重复步骤 2
     * @param root
     */
    public static void inOrderUnRecur(TreeNode root) {
        System.out.println("非递归中序遍历");
        if (root != null) {
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    root = stack.pop();
                    System.out.println(root.val + " ");
                    root = root.right;
                }
            }
        }
    }

    /***
     * 非递归后续遍历
     *  1、申请一个栈，记为 s1 ，然后将头节点 root 压入 s1 中。
     *  
     *  2、从 s1 中弹出的节点记为 cur ,然后依次将 cur 的左孩子和右孩子压入 s1 中。
     *  
     *  3、在整个过程中，每一个从 s1 弹出的节点都放入 s2 中。
     *  
     *  4、 不断重复步骤 2 和步骤 3 ，直到 s1 为空，过程停止
     *  
     *  5、从 s2 中依次弹出节点并打印。
     * @param root
     */
    public static void posOrderUnRecur(TreeNode root) {
        System.out.println("非递归后续遍历");
        if (root != null) {
            Stack<TreeNode> s1 = new Stack<>();
            Stack<TreeNode> s2 = new Stack<>();
            s1.push(root);
            while (!s1.isEmpty()) {
                    root = s1.pop();
                    s2.push(root);
                    if (root.left != null) {
                        s1.push(root.left);
                    }
                    if (root.right != null) {
                        s1.push(root.right);
                    }
            }
            while (!s2.isEmpty()) {
                System.out.println(s2.pop().val + " ");
            }
        }
    }
}

PS:非递归遍历搞得头脑发晕....

参考文献 :左神的书