一看就懂！Java实现二叉树的遍历

落日映苍穹つ 2023-06-11 10:25 8阅读 0赞

关于树的遍历顺序：

（1）先序遍历：先访问根节点，再访问左子树，最后访问右子树。

(2)  后序遍历：先左子树，再右子树，最后根节点。

（3）中序遍历：先左子树，再根节点，最后右子树。

（4）层序遍历：每一层从左到右访问每一个节点。

ps：我们只要记住 x序 x指根节点位置，并且保持先左后右。前序遍历：**中**左右，中序遍历：左**中**右，后续遍历：左右**中**。

### 递归版本： ###

**前序遍历： 中**左右

/**
         *     用递归的方法进行前序遍历
         */
        public void DLR(TreeNode treeNode) {
            res.add(treeNode.val);
            if (treeNode.left != null) {
                DLR(treeNode.left);
            }
            if (treeNode.right != null) {
                DLR(treeNode.right);
            }
        }

**中序遍历：**左**中**右

/**
         *    用递归的方法进行中序遍历
          */
        public void LDR(TreeNode treeNode) {
            if (treeNode.left != null) {
                LDR(treeNode.left);
            }
            res.add(treeNode.val);
            if (treeNode.right != null) {
                LDR(treeNode.right);
            }
        }

**后序遍历：**左右**中**

/**
         * 用递归的方法进行后序遍历
         */
        public void LRD(TreeNode treeNode) {
            if (treeNode.left != null) {
                LRD(treeNode.left);
            }
            if (treeNode.right != null) {
                LRD(treeNode.right);
            }
            res.add(treeNode.val);
        }

### 非递归版本： ###

**前序遍历：** **中**左右

/**
         * 用非递归的方法进行前序遍历
         */
        public void DLR2(TreeNode treeNode) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (treeNode != null || !stack.isEmpty()) {
                while (treeNode != null) {
                    res.add(treeNode.val);
                    stack.push(treeNode);
                    //不断向左遍历
                    treeNode = treeNode.left;
                }
                //当到达最左端叶子结点，向右遍历
                if (!stack.isEmpty()) {
                    // 栈弹出得到右节点
                    treeNode = stack.pop();
                    treeNode = treeNode.right;
                }
            }
        }

**中序遍历：**左**中**右

/**
         * 用非递归的方法进行中序遍历
         */
        public void LDR2(TreeNode treeNode) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (treeNode != null || !stack.isEmpty()) {
    
                while (treeNode != null) {
                    stack.push(treeNode);
                    //不断向左遍历
                    treeNode = treeNode.left;
                }
                //当到达最左端叶子节点 添加节点值并向左遍历
                if (!stack.isEmpty()) {
                    treeNode = stack.pop();
                    res.add(treeNode.val);
                    treeNode = treeNode.right;
                }
            }
        }

**后序遍历：**左右**中**

/**
         * 用非递归的方法进行后序遍历
         */
        public void LRD2(TreeNode treeNode) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (treeNode != null || !stack.isEmpty()) {
                while (treeNode != null) {
                    stack.push(treeNode);
                    // 不断遍历到最左端节点
                    treeNode = treeNode.left;
                }
                boolean tag = true;
                // 前驱节点
                TreeNode preNode = null;
    
                while (!stack.isEmpty() && tag == true) {
                    treeNode = stack.peek();
                    if (treeNode.right == preNode) {
                        // treeNode.right == preNode == null 时证明该节点不存在右节点 则当前节点为中节点
                        // treeNode.right == preNode != null 时证明前一个节点是当前节点（栈顶节点）的右节点 ，即已经遍历完了左 右 现在遍历 中
                        // 记住添加节点的思路是 左右中 就好理解了
                        treeNode = stack.pop();
                        res.add(treeNode.val);
                        if (stack.isEmpty()) {
                            return;
                        } else {
                            preNode = treeNode;
                        }
                    } else {
                        // treeNode.right != preNode != null 时证明前一个节点时当前节点(栈顶节点) 的左节点， 就要向右遍历
                        // 指向右节点后跳出循环，而后继续向左遍历
                        treeNode = treeNode.right;
                        tag = false;
                    }
                }
            }
        }

**层次遍历：**

/**
         * 利用队列层次遍历
         */
        public void levelOrder(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                // 每次都取出一层的所有数据
                for (int i = 0; i < queue.size(); i++) {
                    TreeNode node = queue.poll();
                    res.add(node.val);
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
            }
        }