【数据结构】二叉树的三种遍历（非递归讲解）

拼搏现实的明天。 2024-04-20 11:46 26阅读 0赞

**目录**

1、前言

2、二叉树的非递归遍历

2.1、先序遍历

2.2、中序遍历

2.3、后序遍历

![355278a599a54455b77cf596c50ac244.gif][]

## 1、前言 ##

> 学习二叉树的三种非递归遍历前，首先来了解一下**递归序**：
> 
> **递归序**就是按照先序遍历的顺序，遇到的所有结点按顺序排列，重复的结点也必须记录。

![ff1f28e1acbc4f1a87dc8593b227dbef.png][]

> 我们可以发现递归序中每个结点都会遇到三次。
> 
> 这是因为当进入某一结点时，对该结点进行**第一次操作**，然后调用其左孩子结点，等左孩子结点结束调用时会返回自己，此时就可以对自己进行**第二次操作**，然后再调用其右孩子结点，等左孩子结点结束调用时又会返回自己，此时就可以对自己进行**第三次操作，因为不管怎样，调用完孩子结点后终究会返回到父结点。**
> 
> **直接给出结论：**
> 
> 递归序中**第一次**遇到该节点时打印结点，第二次第三次均不做任何操作，这就是**先序遍历**。
> 
> 递归序中**第二次**遇到该节点时打印结点，第一次第三次均不做任何操作，这就是**中序遍历**。
> 
> 递归序中**第三次**遇到该节点时打印结点，第一次第二次均不做任何操作，这就是**后序遍历**。

![8e609d677fc04d71bf40faef17d2454a.png][]

![50b33f1bd7c54abda535e908944a3a35.png][]

![0e84b6729276467f89be13b118ae52cd.png][]

关于**递归序**详细的讲解，可以看我之前写的一篇博客，里面有详细讲解，这里就不过多赘述：

[【算法与数据结构】二叉树的三种遍历代码实现（上）—— 用递归序知识点讲解-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://blog.csdn.net/zzzzzhxxx/article/details/133609612?spm=1001.2014.3001.5501][_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133609612_spm_1001.2014.3001.5501]

## 2、二叉树的非递归遍历 ##

> **任何递归函数都可以改成非递归函数**，因为递归函数不是什么玄学，只是递归时系统帮忙解决了压栈问题。那么不用递归方式的话**只要自己手动进行压栈**依然可以完成递归能够实现的功能。
> 
> 有了**上面递归序**的知识点作为铺垫，就可以很好的理解非递归的实现了。

### 2.1、先序遍历 ###

> 递归序中**第一次**遇到该节点时打印结点，第二次第三次均不做任何操作，这就是**先序遍历**。
> 
> 首先使用cur依次将二叉树**所有左边界节点**入栈，并且打印节点。当此时cur走到叶子节点后，将栈顶元素出栈，并让cur指向出栈元素的右孩子，继续进行左边界节点入栈操作。

public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> list = new LinkedList<>();
            if(root == null) {
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while(cur != null || !stack.isEmpty()) {
                if(cur != null) {
                    stack.push(cur);
                    System.out.print(cur.val + " ");  //第一次遇到时进行打印
                    cur = cur.left;
                } else {
                    cur =  stack.pop();   //第二次遇到
                    cur = cur.right;
                }
            }
            return list;
        }

### 2.2、中序遍历 ###

> 递归序中**第二次**遇到该节点时打印结点，第一次第三次均不做任何操作，这就是**中序遍历**。
> 
> 首先使用cur依次将二叉树**所有左边界节点**入栈。当此时cur走到叶子节点后，将栈顶元素出栈后并打印，此时第二次遇到该元素。然后让cur指向出栈元素的右孩子，继续进行左边界节点入栈操作。

public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> list = new LinkedList<>();
            if(root == null) {
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while(cur != null || !stack.isEmpty()) {
                if(cur != null) {
                    stack.push(cur);   //第一次遇到
                    cur = cur.left;
                } else {
                    cur =  stack.pop();
                    System.out.print(cur.val + " ");   //第二次遇到时进行打印
                    cur = cur.right;
                }
            }
            return list;
        }

### 2.3、后序遍历 ###

> 递归序中**第三次**遇到该节点时打印结点，第一次第二次均不做任何操作，这就是**后序遍历**。
> 
> 首先使用cur依次将二叉树**所有左边界节点**入栈。当此时cur走到叶子节点后，**使用peek()查找出栈顶元素top（并非出栈）**后并打印，然后判断top节点是否存在右孩子，当存在时则让cur指向top节点的右孩子，继续进行左边界节点入栈操作。当top不存在右孩子时则将栈顶元素出栈并打印栈顶元素，此时第三次遇到该元素。

public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> list = new LinkedList<>();
            if(root == null) {
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            TreeNode prev = null;
            while(cur != null || !stack.isEmpty()) {
                if(cur != null) {
                    stack.push(cur);   //第一次遇到
                    cur = cur.left;
                } else {
                    TreeNode top = stack.peek();   //第二次遇到
                    if(top.right != null && prev != top.right) {   //当该节点右子树不为空,并且之前没有去过右子树时
                        cur = top.right;						
                    } else {     //该节点右子树为空或者是已经去过一次右子树了
                        top = stack.pop();
                        System.out.print(cur.val + " ");   //第三次遇到时进行打印
                        prev = top;
                    }
                }
            }
            return list;
        }

![eaef75c920c6481ea410b5ef8525cb60.gif][]

**博主推荐：**

[【LeetCode力扣】单调栈解决Next Greater Number（下一个更大值）问题-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://blog.csdn.net/zzzzzhxxx/article/details/136030138?spm=1001.2014.3001.5501][LeetCode_Next Greater Number_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_136030138_spm_1001.2014.3001.5501] [【数据结构】二叉搜索树的模拟实现-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://blog.csdn.net/zzzzzhxxx/article/details/135910604?spm=1001.2014.3001.5501][-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_135910604_spm_1001.2014.3001.5501]

[【LeetCode力扣】面试题 17.14. 最小K个数（top-k问题）-CSDN博客![icon-default.png?t=N7T8][icon-default.png_t_N7T8]https://blog.csdn.net/zzzzzhxxx/article/details/135737266?spm=1001.2014.3001.5501][LeetCode_ 17.14. _K_top-k_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_135737266_spm_1001.2014.3001.5501]

**如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！**

[355278a599a54455b77cf596c50ac244.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/a31095e1c93e4f4ca0e950b801cd0918.gif
[ff1f28e1acbc4f1a87dc8593b227dbef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/d26c862187e343baa05de438ee46db58.png
[8e609d677fc04d71bf40faef17d2454a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/2ad17335f355487190d4f2b9896a9d2e.png
[50b33f1bd7c54abda535e908944a3a35.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/4b06d0c4794143909cd3db4c7d95fd82.png
[0e84b6729276467f89be13b118ae52cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/a47093c269bf487483a3a269586b5968.png
[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_133609612_spm_1001.2014.3001.5501]: https://blog.csdn.net/zzzzzhxxx/article/details/133609612?spm=1001.2014.3001.5501
[eaef75c920c6481ea410b5ef8525cb60.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/3247d5611a6641459a3e08ba633beb60.gif
[LeetCode_Next Greater Number_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_136030138_spm_1001.2014.3001.5501]: https://blog.csdn.net/zzzzzhxxx/article/details/136030138?spm=1001.2014.3001.5501
[-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_135910604_spm_1001.2014.3001.5501]: https://blog.csdn.net/zzzzzhxxx/article/details/135910604?spm=1001.2014.3001.5501
[LeetCode_ 17.14. _K_top-k_-CSDN_icon-default.png_t_N7T8_icon-default.png_t_N7T8_https_blog.csdn.net_zzzzzhxxx_article_details_135737266_spm_1001.2014.3001.5501]: https://blog.csdn.net/zzzzzhxxx/article/details/135737266?spm=1001.2014.3001.5501