花一晚上也无法理解非递归遍历二叉树，我该继续学下去吗？

发布时间：2025-11-28 02:18

你知道吗，人类的大脑可以在你睡觉时继续学习和处理信息吗？ #生活乐趣# #日常生活趣事# #日常生活笑话# #轻松生活趣闻#

这是小星学DSA系列的第二篇，我会记录我学习的过程与理解，希望能够帮到你。

本篇文章的思维导图如下，在文章的末尾，我会给出更加详细的思维导图。

上篇我们一上来就介绍了红黑树，原因是红黑树在sde岗位面试中的重要分量。

当然，基础也要打好，因此这篇文章，我们来学习一下二叉树的基础。

二叉树的定义与性质

定义与表示

二叉树是一种特殊类型的通用树，它的每个节点最多可以有两个子节点，两个子节点是有序的，分为左子节点与右子节点。

链式表示（常用）

链式表示是通过指针把分布在散落在各个地址的节点串联一起。

二叉树通常由指向根节点的指针表示，二叉树的每个节点都包括以下三个部分：

节点的值指向左子节点的指针指向右子节点的指针

2. 顺序表示

顺序表示的元素在内存是连续分布的。

如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树的基本概念

以下列出了二叉树中的一些基本概念

二叉树的分类

满二叉树

若高度为h的二叉树恰好有$2^h -1$个元素，则称其为**满二叉树**（顾名思义，满了的二叉树）

完全二叉树

如果所有叶子节点都位于相同的高度，则称为**完全二叉树**（只有最后一层没满的二叉树）

二叉搜索树

所有节点的值唯一，且左子树的值都小于该节点的值，右子树的值都大于该节点的值。

平衡二叉树（AVL树）

左子树和右子树高度差至多为1的二叉搜索树

二叉树的性质

1. 含n个元素的二叉树有n-1条边

2. 若二叉树的高度为h，它最少有h个元素，最多有$2^h -1$个元素

3. 若二叉树有n个元素，它的最大高度为n，最下高度为$log_2(n+1)$

4. 对于完全二叉树的一个元素i，其父节点为[i/2]，左孩子为2i（或者不存在），右孩子为2i+1（或不存在）

这些性质证明起来都不难，初中数学难度，这里不再赘述。

二叉树的操作

二叉树的遍历

二叉树的遍历是老生常谈了，我在实习的面试里遇到过无数次（不过出这个一般也和放水差不多了）

二叉树的遍历有四种方式：前序、中序、后序、层序

小星说丨前中后序的区分方法——父节点在什么时候被访问（前序：先访问父节点，再访问左子树和右子树；中序：先访问左子树，再访问父节点，再访问右子树；后序：先访问左子树，再访问右子树，最后访问父节点）

前序遍历

二叉树前序遍历的步骤如下：

1. 访问根节点

2. 以前序遍历左子树

3. 以前序遍历右子树

具体到代码实现，我们通常可以使用递归方法（常用）或者迭代方法实现。

1. 递归方法非常简单粗暴，除了一个非空判定之外，与上面的步骤是一样的

2. 迭代法则需要用到栈，每次访问栈顶元素，并将它的右节点和左节点依次放入栈中，从而实现前序遍历的逻辑。

中序遍历

知道了前序遍历，中序遍历的思路也就很清楚了

二叉树中序遍历的步骤：

- 按顺序遍历左子树

- 访问根节点

- 按顺序遍历右子树

中序遍历同样可以使用递归法和迭代法实现

1. 递归法也没什么好说的，简单粗暴

2. 中序遍历的迭代法和前序遍历不同的是，这里的栈保存的是所有的根节点，一路向左一路保存根节点，当到达最左处时，可以从栈中取出一个根节点来访问，之后再遍历右子树，也是用同样的方法。

后序遍历

二叉树后序遍历的步骤如下：

- 按后序遍历左子树

- 按后序遍历右子树

- 访问根节点

同样可以使用递归法和迭代法来实现

1. 递归法还是一样

2. 迭代法中，我们仍使用一个栈保存待遍历的根节点，而当我们从栈中拿出一个待访问的根节点时，有两种情况：1. 我们刚从左边上来，要遍历右子树2. 我们已经遍历了右子树，要访问当前根节点，因此需要一个指针保存上一次访问的节点，以确定右子树是否已被访问

3. 我们注意到后序遍历（左右中）其实可以由变种的前序遍历（中右左）反转得到，因此可以使用反转的方法, cr代码随想录

层序遍历

层序遍历理解上更简单了，就是一层一层的遍历。

层序遍历同样可以使用迭代法和递归法，只不过这里迭代法可能更常用一些

1. 迭代法，使用一个队列存储待访问的节点，每次访问将左节点和右节点放入队列内，即可实现一层一层的遍历

2. 递归法：层序遍历的递归法，需要记录每层的高度，通过高度储存每一层的节点

二叉树的搜索

二叉树的搜索，二叉树的最值，二叉树的高度，二叉树的元素数目等操作均建立在二叉树的遍历基础上，选一种合适的遍历方法即可实现，这里不再赘述。

二叉树的重构

二叉树的重构，即从遍历的结果里重新构造一棵二叉树。

二叉树的重构需要两种遍历结果的综合，但是通常不能从前序和后序结果里重构二叉树，因为不能确定根节点的左子树和右子树信息。

从前序与中序遍历结果中重构二叉树

从前序与中序遍历结果中重构二叉树分为以下几步：

1. 从前序遍历结果中获得根节点值（前序遍历的第一个元素）

2. 找到该值在中序遍历结果中的索引rootIdx

3. 借助rootIdx，将前序结果和中序结果都切分成左子树的结果和右子树的结果

4. 递归实现重构

从中序和后序结果中重构二叉树

中序和后序重构二叉树的方法类似:

1. 从后序遍历结果中获得根节点值（后序遍历的第一个元素）

2. 找到该值在中序遍历结果中的索引rootIdx

3. 借助rootIdx，将前序结果和中序结果都切分成左子树的结果和右子树的结果

4. 递归实现重构

二叉树操作的时空复杂度

最后总结一下二叉树基本操作的时空复杂度

这里都是将二叉树视作退化的链表来计算的，如果二叉树是搜索树或平衡树，则时间复杂度进一步降低。

总结

最后我们再给出本篇文章的详细内容导图

源代码

本文代码已在github上开源，包含c++，python(待补充), golang(待补充)的二叉树及其操作代码，如果你觉得这篇文章对你有帮助的话，还请帮忙在github上点个Star，谢谢！

同时，欢迎访问我的个人网站小星code我会分享更多关于CS学习的心得与经验。

参考资料

1. 清华大学计算机系邓俊辉教授DSA课件[05.二叉树]，[下载地址](http://dsa.cs.tsinghua.edu.cn/~deng/ds/dsacpp/)

2. 萨尼 S, 王立柱, 刘志红数据结构、算法与应用 C++语言描述[M]. 北京: 机械工业出版社, 2015.

网址：花一晚上也无法理解非递归遍历二叉树，我该继续学下去吗？ https://klqsh.com/news/view/292034

⬅️上一篇：二叉树的非递归遍历花一晚上也无

➡️下一篇：【算法】递归的艺术：从本质思想到