初学二叉树：从概念到递归，我的理解与思考
初学二叉树：从概念到递归，我的理解与思考
刚学完普通二叉树的基础内容，趁热整理一下自己的理解和学习思路，既是复盘，也希望能给同样入门的同学一点参考。
一、我对二叉树的初印象：从倒立的树说起
最开始理解二叉树，我总把它想象成一棵倒立的树—— 根在最上面，向下分叉生长。和堆那种有固定规则的结构不一样，普通二叉树的形态更灵活，节点排布没有严格约束。
和之前学的栈、队列相比，最直观的区别就是：栈和队列是线性结构，二叉树是非线性结构。栈和队列底层都可以用数组轻松实现，而二叉树天然更适合用链表来构造。线性结构里每个元素最多只有一个前驱和一个后继，是一条线；但二叉树里一个节点可以分出两个分支，结构一下子就铺开了。
二、核心概念梳理：度、叶子节点与万能公式
1. 什么是节点的度
简单说，节点的度就是它有几个孩子。在二叉树里，节点的度只能是 0、1、2 三种：
- 度为 0：没有孩子，也就是叶子节点
- 度为 1：只有一个孩子，单分支节点
- 度为 2：左右孩子都有，双分支节点
我自己记的时候就类比树枝：一根枝条分到最末端、不再分叉的地方就是叶子；分一个叉就是单分支，分两个叉就是双分支。
这里有个容易混淆的点：叶子节点是「度为 0 的节点」，不等于「最下面一层的所有节点」。严格来说，只要没有孩子，无论在哪一层都是叶子节点，只不过最底层的节点天然都是叶子。
2. 万能公式 n₀ = n₂ + 1 的推导
这个公式是做计算题的核心，我是通过边数守恒推导理解的：
- 从总节点数看：整棵树的总边数 = 总节点数 - 1 = n₀ + n₁ + n₂ - 1
- 从节点分支看：总边数 = 所有节点发出的分支数 = 2×n₂ + 1×n₁ + 0×n₀
两边相等化简之后，就能得到n₀ = n₂ + 1。
做题的时候这个公式非常好用，可以直接消掉一个未知数。再结合题目给出的附加条件，比如完全二叉树中 n₁ 只能是 0 或 1，再利用「节点数必须是整数」这个隐含条件，通常就能排除一个错误结果，快速选出答案。
验证一棵二叉树是否存在也很简单： 已知总节点数和度为 2 的节点数时，先用公式算出 n₀，再求出 n₁，只要 n₁ ≥ 0 且符合对应二叉树的约束（比如完全二叉树 n₁ 只能 0 或 1），就是合法的。
三、三种二叉树的区分
这三个概念刚开始很容易搞混，我自己总结了一句话：
- 普通二叉树：怎么长都行，没有任何约束
- 满二叉树：每一层都长满了，所有节点度都是 2，没有空缺
- 完全二叉树：除了最后一层，上面所有层都是满的；最后一层的节点必须从左到右依次排列，中间不能有空缺
完全二叉树「从左到右连续」这个规则很容易踩坑，也是我刚开始反复确认的点 —— 哪怕最后一层节点少，但只要右边缺、左边连续，就是完全二叉树；如果左边空了、右边还有节点，那就不是。
四、代码实现：为什么优先用链式结构？
我最开始实现二叉树，直接就选择了链式结构。原因很直观：普通二叉树形态灵活，如果用数组存，很难快速定位一个节点的左右孩子，遍历和操作都不方便。
不过这也是我后续要补的一个点：数组其实也可以实现二叉树，尤其是完全二叉树和满二叉树，用数组下标就能非常方便地计算父子节点关系。普通二叉树用数组会浪费很多空间，但不是完全不能实现，这个误区我后面会专门再理清楚。
链式二叉树的节点结构体设计很清晰：一个数据域，加上两个指针分别指向左孩子和右孩子，保存的是左右子树的首地址。
c
运行
typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;五、二叉树遍历：递归的本质就是函数调用栈
1. 前中后序记忆技巧
三种遍历顺序我总结了一句口诀：左右顺序永远不变，根的位置决定前中后。
- 前序：根 → 左 → 右
- 中序：左 → 根 → 右
- 后序：左 → 右 → 根
只要记住「根在哪就是什么序」，基本不会记混。
2. 递归的底层就是栈
递归遍历写起来代码很短，但刚开始总觉得很神奇。学明白之后发现，它的底层本质就是系统的函数调用栈。
每递归调用一次函数，系统就会在栈里压入一个栈帧，保存当前节点、局部变量和返回地址；一直递归到叶子节点、函数执行结束，栈帧再依次弹出，回到上一层继续执行剩下的代码。整个「一路向下、再逐层返回」的过程，完全符合栈「后进先出」的特性。
非递归遍历我目前还没有深入研究，只知道它本质就是我们自己手动建一个栈，去模拟系统调用栈的过程。至于「什么情况不能用递归」，我也还在思考 —— 目前只知道递归深度太大的时候会栈溢出，比如一条很长的单链二叉树，递归层数上万就会崩，这时候就必须用非递归写法。
另外还有一个小疑问：层序遍历算不算递归遍历？我自己觉得不算，因为层序遍历是用队列实现的，一层一层往下走，实现过程中函数也没有调用自身，应该属于迭代遍历的一种。
六、学习中的疑问与反思
- 二叉树的现实意义到底是什么？它到底解决了哪些线性结构做不到的事情？这个问题我目前还只有模糊的感觉，没有特别清晰的答案，也是我接下来想搞明白的地方。
- 数组实现普通二叉树的具体方式，以及它和链式实现各自的适用场景，还需要补全。
- 非递归遍历的写法、适用场景和优缺点，是接下来的重点学习内容。
不过可以确定的是，把普通二叉树的结构、递归和遍历吃透，后面学二叉搜索树、平衡树、堆这些内容，基础就会扎实很多。
七、给初学同学的一点小建议
如果是刚接触二叉树，我个人最大的感受是：先培养对递归的感觉。
二叉树的很多操作天然适合递归写法，刚开始可能觉得绕，但写多了、画多了递归展开图，慢慢就会形成一种直觉，遇到问题会下意识地想到「这个可以用递归拆成子问题」。不用一开始就死磕非递归，先把递归的逻辑理解透，很多东西会自然而然地通。
以上就是我初学二叉树的全部心得，后续学了新内容再继续补充～