二叉樹先序、中序、後序、層次周遊遞歸以及非遞歸算法實作

最近寫了一下關于二叉樹的三種周遊算法的遞歸以及非遞歸實作，以及層次周遊算法實作

先序周遊遞歸實作

/**
     * 先序周遊，根》左》右
     */
    public void beforeTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + "->");
        if (root.left != null) {
            beforeTraverse(root.left);
        }
        if (root.right != null) {
            beforeTraverse(root.right);
        }
    }
           

先序周遊非遞歸實作

/**
     * 通過棧周遊二叉樹，先序（思想就是：入棧即記錄）
     */
    public List<String> beforeTraverseByStack(TreeNode root) {
        List<String> list = new ArrayList<>(); // 接受結果
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        // 先序周遊（根 》左 》右），先周遊所有左結點，将他們放到棧中
        while (root != null) {
            // 周遊的所有左結點都要加入到結果集中
            list.add(root.value);
            stack.push(root);
            root = root.left;
        }
        while (!stack.empty()) {
            TreeNode node = stack.pop();
            if (node.right != null) {
                // 入棧及記錄
                list.add(node.right.value);
                TreeNode push = stack.push(node.right);
                while (push.left != null) {
                    // 入棧及記錄
                    list.add(push.left.value);
                    stack.push(push.left);
                    push = push.left;
                }
            }
        }
        return list;
    }
           

中序周遊遞歸實作

/**
     * 中序周遊，左》根》右
     */
    public void middleTraverse(TreeNode root) {
        if (root.left != null) {
            middleTraverse(root.left);
        }
        System.out.print(root.val + "->");
        if (root.right != null) {
            middleTraverse(root.right);
        }
    }
           

中序周遊非遞歸實作

/**
     * 通過棧周遊二叉樹，中序（思想就是：出棧即記錄）
     */
    public List<String> middleTraverseByStack(TreeNode root) {
        List<String> list = new ArrayList<>(); // 接受結果
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        // 中序周遊（左 》根 》右），先周遊所有左結點，将他們放到棧中
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        while (!stack.empty()) {
            // 出棧及記錄
            TreeNode node = stack.pop();
            list.add(node.value);
            if (node.right != null) {
                TreeNode push = stack.push(node.right);
                while (push.left != null) {
                    stack.push(push.left);
                    push = push.left;
                }
            }
        }
        return list;
    }
           

後序周遊遞歸實作

/**
     * 後序周遊，左》右》根
     */
    public void afterTraverse(TreeNode root) {
        if (root.left != null) {
            afterTraverse(root.left);
        }
        if (root.right != null) {
            afterTraverse(root.right);
        }
        System.out.print(root.val + "->");
    }
           

後序周遊非遞歸實作

/**
     * 通過棧周遊二叉樹，後序
     */
    public List<String> afterTraverseByStack(TreeNode root) {
        List<String> list = new ArrayList<>(); // 接受結果
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>(); //這個棧用于儲存二叉樹元素結點（按順序，根+右+左）
        // 後序周遊（左 》右 》根），先将所有右結點加入到兩個棧中
        while (root != null) {
            stack.push(root);
            stack2.push(root);
            root = root.right;
        }
        while (!stack.empty()) {
            TreeNode pop = stack.pop();
            if (pop.left != null) {
                TreeNode push = stack.push(pop.left);
                stack2.push(pop.left);
                while (push.right != null) {
                    stack.push(push.right);
                    stack2.push(push.right);
                    push = push.right;
                }
            }
        }

        // 将stack2中一個一個彈出，放到結果集中（這裡就是利用了後序，倒着周遊的特點）
        while (!stack2.empty()) {
            list.add(stack2.pop().value);
        }
        return list;
    }
           

層次周遊算法實作

/**
     * 層次（順序）周遊，一層一層，從左向右
     * 需要引入隊列這種資料結構，隊列：先進先出，頭進尾出
     * 因為既需要找到一個結點的左結點又需要找到右結點
     */
    public List<String> orderTraverse(TreeNode root) {
        // 使用集合代替隊列，先進先出（出隊列就是移除第0個元素）
        List<TreeNode> list = new ArrayList<>();
        List<String> result = new ArrayList<>();    // 接受結果
        if (root == null) {
            return result;
        }
        list.add(root);
        while (!list.isEmpty()) {
            TreeNode node = list.remove(0);
            result.add(node.val);
            if (node.left != null) {
                list.add(node.left);
            }
            if (node.right != null) {
                list.add(node.right);
            }
        }
        return result;
    }
           

總的來說，非遞歸算法就是引入輔助資料結構棧（或者其他），利用他們特殊的結構先進後出（其他）的特點，完成按要求的周遊

關于樹的很多算法都是由他們變形而來的，但還是需要靈活的轉變思維才能解決相應的問題