[Java]前中后序遍历二叉树/递归与非递归

向右看齐 2024-02-20 09:39 50阅读 0赞

## 一、递归方法 ##

> 首先，树形结构都是由递归方式定义的。那么递归是怎么用的？
> 
> 1、终止条件；2、调用自身

### 分析 ###

1、什么时候停止？

当结点值为空的时候，返回null；

2、如何调用自身？

以前序遍历为例：前序遍历的顺序是——根节点、左节点、右节点

先打印根节点，然后打印经过前序遍历的左子树，最后打印经过前序遍历的右子树

其他两种遍历方法同理

### 前序遍历 ###

public void preOrder(TreeNode root){//前序遍历
            if (root == null){
                return;
            }
            System.out.print(root.val + " ");
            preOrder(root.left);
            preOrder(root.right);
        }

### 中序遍历 ###

public void inOrder(TreeNode root){//中序遍历
            if (root == null){
                return;
            }
            preOrder(root.left);
            System.out.print(root.val + " ");
            preOrder(root.right);
        }

### 后序遍历 ###

public void postOrder(TreeNode root){//后序遍历
            preOrder(root.left);
            preOrder(root.right);
            System.out.print(root.val + " ");
        }

## 二、非递归方法 ##

### 分析 ###

> 因为树形结构都是由递归方式定义的，所以非递归方法就是用其他方法来模拟递归。
> 
> 我们要通过栈中的结点才能从其左节点遍历到右节点。
> 
> 我这里使用的是栈，当然也可以使用其他结构

### 前序遍历 ###

以深度为2的二叉树举例：

1、将根节点A入栈，打印A，cur指向cur.left

![b75e365bfaf4463d8b9448405f67872d.png][]

2、将cur指向的结点cur入栈，并打印B。cur指向左节点，此时cur为空。

![4ccae1c5981b483e9e6c764f36af76c4.png][]

3、此时左节点已经遍历完毕，开始遍历右节点。弹出栈顶元素并设为top，使得cur等于top，cur移向右节点 。此时对于cur指向的B结点来说左子树为空，右子树也为空。说明B结点已经遍历完了。

![21d9b3805f06439a993814c656a59a19.png][]

4、上一个栈顶元素已经左右子树遍历完了。此时再弹出栈顶元素，开始遍历其右子树。cur指向top

![d1b4afc2d1a14ff7bb2c8a60a0fec5c9.png][]

5、如果此时top的右边有结点，则将其入栈。

![755cb90a7f8e4e09810ea9d57211729e.png][]

6、cur指向其左边，查看是否有左子树。cur = cur.left

![7b5eca35ad6749abb0e82667fcf56bb1.png][]

7、左侧为空则开始遍历其右子树。弹出栈顶元素，cur = top 。然后cur = cur.right

![f3a4762aea664c29a5e189a984b127d2.png][]

8、 发现右侧为空，且栈为空。遍历结束

代码如下

public void preOrderNor(TreeNode root){
            //模拟遍历的终止条件
            if (root == null){
                return;
            }
            TreeNode cur = root;
            Deque<TreeNode> stack = new ArrayDeque<>();
            //如果指针cur不为空且栈中还有元素，说明遍历未结束
            while (cur != null || !stack.isEmpty()){
                //如果cur不为空，将其入栈（用以和其右子树产生联系）并打印，然后查看其左子树，
                //直到左子树为空
                while (cur != null){
                    stack.push(cur);
                    System.out.println(cur.val + " ");
                    cur = cur.left;
                }
                //此时左子树为空，弹出栈顶元素开始遍历其右子树
                TreeNode top = stack.pop();
                cur = top.right;
            }
        }

> 中序遍历与后序遍历同理

### 中序遍历 ###

public void inOrderNor(TreeNode root){
            if (root == null){
                return;
            }
            TreeNode cur = root;
            Deque<TreeNode> stack = new ArrayDeque<>();
            while (cur != null || !stack.isEmpty()){
                while (cur != null){
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode top = stack.pop();
                System.out.println(cur.val + " ");
                cur = top.right;
            }
        }

### 后序遍历 ###

public void postOrderNor(TreeNode root){
            if (root == null){
                return;
            }
            TreeNode cur = root;
            TreeNode prev = null;
            Deque<TreeNode> stack = new ArrayDeque<>();
            while (cur != null || !stack.isEmpty()){
                while (cur != null){
                    stack.push(cur);
                    cur = cur.left;
                }
                //此时左子树已经遍历完了，但是还不能弹出栈顶元素。
                //因为这是后续遍历，根节点要在右结点打印后才能打印
                //现在弹出去后面就没法打印这个根节点了
                TreeNode top = stack.peek();
                if (top.right == null || top.right == prev){
                    System.out.println(top.val + " ");
                    stack.pop();
                    prev = top;
                }else {
                    cur = top.right;
                }
            }
            System.out.println();
        }

[b75e365bfaf4463d8b9448405f67872d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/db8264d339bd4899a8bbd20f593b95aa.png
[4ccae1c5981b483e9e6c764f36af76c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/8fa2f97f7dc1459cb380b48d8cb98824.png
[21d9b3805f06439a993814c656a59a19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/449c61f82d1c40c2b7ec32f1e586e052.png
[d1b4afc2d1a14ff7bb2c8a60a0fec5c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/9e6f5d9949d2488aa890b1b3b819b122.png
[755cb90a7f8e4e09810ea9d57211729e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/14044b36fdec4bc0a7adee64e0ef8512.png
[7b5eca35ad6749abb0e82667fcf56bb1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/3eeb12cabce84cabaf19ba3b1565dde8.png
[f3a4762aea664c29a5e189a984b127d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/5b2c2e40b762438a9c4a4e38ff412bd3.png