二叉树核心知识全解析：从遍历到AVL树与嵌入式实践

1. 先搞懂二叉树到底是什么以及为什么非学不可1.1 从“数组/链表”到二叉树结构演进我在嵌入式开发和算法面试两个方向都待过不少时间发现一个特别普遍的现象很多人对数组、链表用得挺溜一提到二叉树就开始头皮发麻。其实你换个角度看就很自然——数组是“一条线”链表是“一条带指针的线”当你要处理的数据开始有“分支”关系时线性结构就撑不住了。比如你要表示一个公司组织架构、一个文件目录、一场淘汰赛的赛程这些天生就是树形结构一根线串不起来。二叉树就是树结构里最典型、约束最清晰的一种每个节点最多有两个孩子分别叫左孩子和右孩子。别小看这个“最多两个”的约束恰恰是它让二叉树在数学性质、存储方式、遍历算法上都变得非常规整。我在带新手的时候经常说你把二叉树学扎实了再去学B树、红黑树、堆、线段树都会觉得自己在“吃老本”因为这些高级结构本质上都是在二叉树骨架上做文章。从更实际的角度看二叉树也是一切树形算法的基础。搜索、排序、动态维护最值、表达式解析、哈夫曼编码、路由表查找底层多多少少都有二叉树的影子。所以不管你以后做后端、客户端、算法岗还是往嵌入式底层走二叉树都是绕不过去的一关。1.2 一堆名词先理清深度、高度、满、完全、平衡很多人一开始被二叉树劝退不是因为代码难写而是被概念名词砸晕了。其实真正要分清楚的就几个。深度和高度是最容易混的。我教你一个不会记错的方法深度是从上往下数的根节点深度为0也有教材从1开始高度是从下往上数的叶子节点高度为0。你想想“坑有多深”是从地面往下量的“楼有多高”是从地面往上量的一个道理。二叉树的最大深度其实就等于整棵树的高度。满二叉树所有层都填满了节点总数是2的n次方减1n是层数。完全二叉树只有最后一层可能不满而且最后一层的节点必须从左到右连续排列。完全二叉树这个性质特别重要因为数组存储二叉树时只有完全二叉树能做到不浪费空间。平衡二叉树左右子树高度差不超过1的二叉树。这个概念是AVL树的基础后面我会专门讲。现在你只需要知道一棵二叉树如果退化成“一条线”那就跟链表没区别了所有树形的优势都会丢掉。1.3 二叉树的存储方式链表和数组到底选哪个二叉树在代码里怎么存基本就两种路数。第一种是链式存储也是最直观的。每个节点定义一个结构体包含数据域和两个指针域typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;每个节点就是一个独立分配的内存块通过指针串起来。这种方式的优点是直观、方便增删节点缺点是每个节点要额外花掉两个指针的内存而且在嵌入式等对内存敏感的场景里频繁malloc容易产生碎片。第二种是顺序存储直接用数组存二叉树。根节点放下标1或者0然后某个节点下标为i时它的左孩子是2i或2i1右孩子是2i1或2i2父节点是i/2整数除法。这个公式非常有用我到现在写堆排序、写线段树都还在用。顺序存储的最大优点就是省内存不需要存指针。但缺点也很明显只有完全二叉树才能高效利用空间。如果树很不规则数组里会空出大量“洞”浪费严重。所以我的建议是做题和写业务代码默认用链式存储设计底层数据结构、嵌入式环境优先考虑顺序存储。2. 遍历是二叉树绕不过去的门槛2.1 先序、中序、后序递归写法为什么是三行代码二叉树的遍历是热词里出现最多的也是最高频的考题。所谓先序、中序、后序指的是根节点被访问的时机——根先被访问就是先序也叫前序根在中间就是中序根最后就是后序。三个顺序的递归写法骨架完全一样只是打印/收集节点的位置不同。// 先序根-左-右 void preorder(TreeNode* root) { if (!root) return; process(root); // 访问根 preorder(root-left); // 遍历左子树 preorder(root-right); // 遍历右子树 } // 中序左-根-右 void inorder(TreeNode* root) { if (!root) return; inorder(root-left); process(root); inorder(root-right); } // 后序左-右-根 void postorder(TreeNode* root) { if (!root) return; postorder(root-left); postorder(root-right); process(root); }我见过太多人硬背这三段代码我问你一个问题你就知道硬背多危险了这三段代码里有两个递归调用你能说出来“先序”和“后序”的递归调用顺序为什么是相同的吗答案是不管哪种遍历都是先递归左子树、再递归右子树区别只在于process(root)这一行代码放在哪个位置。放在开头就是先序放在中间就是中序放在最后就是后序。递归的终止条件都是空节点直接返回这也是为什么“三行代码”看起来那么对称。2.2 迭代遍历手动维护栈的细节递归写法虽然简洁但有两个现实问题一是面试官爱问迭代写法考察你对栈的理解二是在嵌入式或高实时性场景里递归调用有栈溢出风险必须用迭代。先序的迭代版本最简单先把根压栈然后循环弹出节点、处理、先压右孩子再压左孩子因为栈是后进先出要让左孩子先被弹出。void preorderIter(TreeNode* root) { if (!root) return; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); process(node); if (node-right) st.push(node-right); // 先压右 if (node-left) st.push(node-left); // 再压左 } }中序的迭代就稍微绕一点。核心思路是一直往左走到头过程中把节点全压栈走到空节点后弹出栈顶处理然后转向右子树继续。这个“一路向左压栈弹出后跳右子树”的模式就是中序迭代的精髓。void inorderIter(TreeNode* root) { stackTreeNode* st; TreeNode* cur root; while (cur || !st.empty()) { while (cur) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); process(cur); cur cur-right; } }后序的迭代最麻烦因为要保证左右子树都处理完才能处理根节点。有一个取巧的方法是用“先序变体”按照“根-右-左”的顺序遍历再把结果反转就得到“左-右-根”的后序。这个技巧做题时非常省事不过严格刷题的场景下我还是建议你掌握带标记位或双栈的标准写法。2.3 层序遍历就是BFS模板要背熟层序遍历就是从上到下、从左到右一层一层地扫本质就是广度优先搜索BFS用队列实现。这个模板几乎到处都能用求二叉树深度可以基于它判断完全二叉树可以基于它打印之字形遍历还是基于它。void levelOrder(TreeNode* root) { if (!root) return; queueTreeNode* q; q.push(root); while (!q.empty()) { int levelSize q.size(); for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); process(node); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } } }注意这里的levelSize q.size()一定要在循环开始前取好。我见过有新手在for循环里直接写i q.size()因为队列在不断插入新节点size是动态变化的结果一层遍历到一半突然多跳了几个节点。3. 只给两种遍历序列怎么把树还原3.1 为什么一定要中序先序/后序热词里有一条“知道二叉树先序和中序确定树的样子”这是非常经典的面试题也经常出现在考研和求职笔试里。你首先要明白一个前提光靠先序后序是还原不出一棵唯一的二叉树的。原因很简单。先序的第一个节点一定是根后序的最后一个节点也一定是根但这两者都不能告诉你“左子树到底有哪些节点”。举个例子根只有左孩子和只有右孩子时先序结果可能一模一样都是“根, 某节点”你分不清他是左边那条还是右边那条。而中序序列就特别关键了在中序序列里根的左边一定全是左子树的节点右边全是右子树的节点。这一下子就划出了左右子树的分界线。所以只要你有了“先序/后序 中序”的组合就能一步步把树的结构确定下来。3.2 手把手拆解先序中序还原的步骤给你一个具体例子我们一起走一遍。先序A B D E C F G 中序D B E A F C G第一步看先序第一个节点A它就是整棵树的根。 第二步在中序里找到A的位置中序变成 [D B E] A [F C G]所以左子树是D B E右子树是F C G。 第三步回到先序A后面是B D E C F G去掉根A剩下B D E C F G。其中前3个B D E属于左子树后3个C F G属于右子树这个数量是从中序划分的长度推出来的。 第四步在左子树里递归先序是B D E中序是D B E。B是左子树的根中序里B左边是D、右边是E。于是左子树根为B左孩子D右孩子E。 第五步对右子树递归先序是C F G中序是F C G。C是右子树的根F在C左边G在C右边。于是右子树根为C左孩子F右孩子G。就这么拆下去整棵树的结构就完全出来了。整个过程的核心思想是先序确定根中序划左右不断递归切分。3.3 还原过程的代码实现和边界处理用递归代码实现上面这个思路最直观的写法是基于数组下标切分。TreeNode* build(char* preorder, int preLeft, int preRight, char* inorder, int inLeft, int inRight, unordered_mapchar, int inIndex) { if (preLeft preRight) return NULL; char rootVal preorder[preLeft]; TreeNode* root new TreeNode(rootVal); int rootIdx inIndex[rootVal]; // 根在中序中的位置 int leftSize rootIdx - inLeft; // 左子树节点个数 root-left build(preorder, preLeft 1, preLeft leftSize, inorder, inLeft, rootIdx - 1, inIndex); root-right build(preorder, preLeft leftSize 1, preRight, inorder, rootIdx 1, inRight, inIndex); return root; }这里用哈希表提前存好中序序列里每个字符的下标把每次查找从O(n)降到了O(1)整体时间复杂度是O(n)。这个优化我在实际刷题时经常用笔试里数据量一大差距就很明显。边界处理上最容易出错的点有两个。第一个是leftSize的计算必须用rootIdx - inLeft而不是rootIdx因为要考虑中序子数组的起点。第二个是递归参数的确定建议每次写都自己走一遍最小用例比如只有单个节点的树看下标能不能正确收束。4. 求深度和判断属性二叉树算法题的“基础操作”4.1 最大深度、最小深度递归迭代两条路“二叉树的深度”是热词里的高频词也是很多二叉树题目的前置条件。最大深度的递归写法非常优雅一句话就够。int maxDepth(TreeNode* root) { if (!root) return 0; return 1 max(maxDepth(root-left), maxDepth(root-right)); }思路就是空树深度为0非空树的深度等于左右子树中较深的那棵的深度再加1。这是最经典的“分而治之”思想。如果要求迭代版本那直接用层序遍历遍历了多少层深度就是多少。这个改造特别适合层序模板已经熟练的人。最小深度就有一个大坑了。不少人觉得“把max换成min就完事了”写出来是这样int minDepth(TreeNode* root) { if (!root) return 0; return 1 min(minDepth(root-left), minDepth(root-right)); }这代码表面看没问题但遇到“只有右子树、没有左子树”的树时就会算错。比如根节点只有右孩子这个递归会因为minDepth(NULL)返回0而给出深度1但实际上根到叶子的最短路径应该是根到右孩子再到右孩子深度至少是2。正确写法要加判断如果一个子树为空就直接返回另一棵子树的深度不能把空子树当成深度0来算。int minDepth(TreeNode* root) { if (!root) return 0; if (!root-left) return 1 minDepth(root-right); if (!root-right) return 1 minDepth(root-left); return 1 min(minDepth(root-left), minDepth(root-right)); }这类“边界条件反直觉”的坑恰恰是面试官最爱挖的。我在实际编码时也吃过亏后来养成一个习惯写完递归先自己造几个非对称树测一下。4.2 判断平衡二叉树与对称二叉树热词里提到了“AVL树”而AVL树的前提就是平衡判断。判断一棵树是不是平衡二叉树的经典思路是每个节点的左右子树高度差不超过1并且左右子树自身也都要平衡。最容易想到的写法是在求深度的函数里递归判断每个节点但这样会重复计算子树高度时间复杂度变成O(n^2)了。我建议用“后序遍历剪枝”的思路先递归处理左子树和右子树如果发现不平衡就直接返回-1作为标记否则返回真实高度。int height(TreeNode* root) { if (!root) return 0; int leftH height(root-left); if (leftH -1) return -1; int rightH height(root-right); if (rightH -1) return -1; if (abs(leftH - rightH) 1) return -1; return 1 max(leftH, rightH); } bool isBalanced(TreeNode* root) { return height(root) ! -1; }这个“用-1做违规标记”的技巧用一次就能记住因为比维护外部标志位干净得多。判断对称二叉树其实用的是“镜像相等”的递归思路两棵树对称当且仅当它们的根值相等、左子树和另一棵的右子树对称、右子树和另一棵的左子树对称。这个题目能帮你理解“传入两个节点”这种递归模式后面对你理解红黑树旋转、AVL旋转都很有帮助。4.3 常见误区与调试技巧二叉树调试比普通代码麻烦因为没有直观的图形界面。我自己的调试三板斧分享给你。第一板斧是“造树函数”。写一个根据数组构建二叉树的辅助函数测试的时候直接传一个层序数组就行省得每次都手动new节点。第二板斧是“打印树”。我常用层序遍历打印每个节点再顺便打印空节点为#这样一眼就能看出树长什么样也能快速确认递归过程中的传参对不对。void printTree(TreeNode* root) { if (!root) return; queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* node q.front(); q.pop(); if (node) { cout node-val ; q.push(node-left); q.push(node-right); } else { cout # ; } } cout endl; }第三板斧是“小数据验证”。遇到递归算法我永远先用3个以内节点的最小用例完整地手跑一遍然后再上复杂数据。很多边界条件的错小数据一跑就暴露了。5. 实战中的二叉树搜索树、平衡树与线索化5.1 二叉搜索树的增删查为什么高效热词里的“搜索二叉树”其实就是二叉搜索树BST它给二叉树加了一个非常实用的规则任意节点的左子树所有值都小于它右子树所有值都大于它。这个规则带来的直接好处就是查找可以像二分一样走从根出发目标值比当前节点小就往左走比当前节点大就往右走每一步都能砍掉一半的搜索空间。在平衡的情况下查找的时间复杂度是O(log n)这在数据量大的场景下比链表的O(n)好太多。插入操作也简单从根开始比当前节点小就往左大就往右直到找到一个空位挂上去。删除操作分三种情况这套逻辑值得好好背被删节点没有孩子直接删掉。被删节点只有一个孩子用孩子顶替它。被删节点有两个孩子用左子树的最大值或右子树的最小值顶替它。这个“替身”选择策略能保证替换后仍然满足BST的性质。5.2 AVL树旋转四种情况其实是一件事BST有一个致命弱点如果插入的数据恰好是有序的比如1、2、3、4、5依次插入BST会直接退化成链表查找复杂度变成O(n)。AVL树就是为解决这个问题诞生的——它要求每个节点的左右子树高度差不超过1一旦插入或删除打破了平衡就通过旋转来恢复。很多人看到AVL树的“LL、RR、LR、RL四种旋转”就头皮发麻其实你只要抓住一个核心旋转的本质是把不平衡的子树重新“提”起来让高度较高的一侧往上走。四种情况不用死记理解了就能推。LL就是左子树的左子树太重做一次右旋RR就是右子树的右子树太重做一次左旋LR就是左子树的右子树太重先对左子树做左旋再对整棵树做右旋RL则是对右子树做右旋再对整棵树做左旋。我自己的记忆口诀是“单边拉一下交叉翻两下”。单边失衡就一个旋转解决交叉型失衡就要先局部转一次、再整体转一次。5.3 线索二叉树省掉递归栈的“隐藏指针”线索二叉树这个概念在热词里也出现了它解决的问题非常实在普通二叉树里有很多空指针没利用起来而遍历时又需要递归或栈来记录后继信息。线索二叉树的想法是把那些空指针利用起来——左孩子为空时就让它指向前驱节点右孩子为空时就让它指向后继节点。具体做法是在节点结构体中加两个布尔标志位标记当前指针是指向真实孩子还是指向前驱/后继typedef struct ThreadNode { int val; struct ThreadNode *left, *right; bool ltag, rtag; // false表示指向孩子true表示指向前驱/后继 } ThreadNode;中序线索化后你可以不用递归、不用栈就能沿线索线性地遍历整棵树。这在嵌入式等对调用栈深度敏感的场景里是个很大的优势我后面会专门展开讲。6. 嵌入式场景里的二叉树内存、效率与取舍6.1 嵌入式环境下的数据结构选型热词里有一组“嵌入式二叉树”“嵌入式 二叉树之avl树”这其实是很多做MCU、RTOS开发的工程师绕不开的话题。嵌入式环境内存小、算力有限、实时性要求高数据结构的选型思路跟PC上完全不同。在PC上你写二叉树节点直接malloc没人关心碎片问题。但在嵌入式环境里频繁的动态内存分配是危险的内存碎片会在长时间运行中被放大最后导致分配失败。所以嵌入式里用二叉树往往不是自己写一个通用二叉树而是基于固定大小的节点池来做分配。节点池的思路是在初始化阶段一次性分配一个足够大的结构体数组每个数组元素就是一个节点用一个空闲链表串起来。分配节点时从空闲链表头取一个释放时还回去。这种做法既避免了动态分配带来的不确定性又能用数组索引代替指针节省内存。6.2 嵌入式二叉树的实现注意事项嵌入式二叉树的实现有四个细节我觉得值得特别提醒第一能用数组就不用指针。数组天然适合嵌入式环境——内存连续、访问快、不存在指针悬空问题。只要你的树是接近完全二叉树的形态顺序存储就是最优解。第二递归深度要先算清楚。MCU的栈空间通常只有几KB递归深度稍微大一点就可能栈溢出。AVL树因为自平衡高度严格控制在O(log n)所以很适合嵌入式而普通BST在数据有序输入时会退化成链表递归深度直接变成O(n)这是灾难级的。第三访问越界的风险。数组表示二叉树时2*i1这个下标很容易越界特别是当树接近满二叉树时判断父节点和子节点都要先检查下标合法性。第四有限状态机配合遍历。在实时控制场景里一次完整的遍历不能阻塞太长时间。我常用的做法是把遍历函数设计成状态机每次调用只处理一个节点就返回让出CPU给更高优先级的任务。这样既完成了树的维护又不影响系统实时性。6.3 实战经验嵌入式环境里AVL树仍然值得用我见过不少嵌入式工程师一听到AVL树就说“太复杂嵌入式用不上”真实情况不是这样的。在一个持续不断插入和删除的动态数据场景里我实测过普通BST和AVL树的差异当数据总量超过几千条、分布又不均匀时BST的查找时间会时不时出现明显尖峰而AVL树的查找时间非常平稳。对实时系统来说“最坏情况可控”比“平均情况优秀”重要得多。当然如果你的数据量只有几十条或者数据是静态配置好的那还真没必要上AVL树直接把数据放在有序数组里用二分查找就足够了。嵌入式开发的本质就是在各种约束里找平衡点而不是一味追求某个单一指标。最后分享一个我调试二叉树代码时的小习惯不管在PC上还是嵌入式上先写好一个“可视化打印”的调试函数用缩进和分层把树结构打出来。这个工具我用了快十年每次遇到树相关的bug它能帮我省下至少一半的时间。