先交代一个背景这是C/C基础数据结构系列的下篇上篇我们讲完了顺序表、链表、栈和队列这篇把最让人头疼的两块硬骨头一起啃掉——二叉树和图然后再把基础算法串一遍。写这篇文章的直接触发点是我最近在社群里看到好几个朋友问同一个问题写二叉树程序时为什么总是报运行时错误这句话几乎每个星期都会出现在C/C相关讨论区而且翻来覆去都是那几个原因空指针没判断、节点没初始化、递归边界写错。所以这篇我不打算干巴巴地列概念定义而是把理解原理和动手排错揉在一起讲带着你把C/C的二叉树、图以及配套算法真正跑起来。适合正在学数据结构的学生、准备实习面试的开发者以及所有被树和图的递归搞到怀疑人生的自学者。1. 二叉树为什么同样的代码别人跑得稳你却总崩溃1.1 链式存储的指针本质先从struct说起只要写二叉树第一件事就是定义节点结构。绝大多数教科书和工程代码用的都是链式存储struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };这个结构本身没什么好说的真正的坑在你怎么用这三块内存。很多初学者第一次写二叉树脑子里只有节点连着节点却忽略了left和right是指针指针就得指向一块真实存在的内存。我在代码评审里见过最典型的一种错误是只给根节点分配了内存左右孩子全是悬空的TreeNode* root new TreeNode(1); root-left new TreeNode(2); // 只建了一个子节点 // root-right 呢没建但构造函数里已经初始化为 nullptr 了构造函数里把left和right初始化为nullptr这一步怎么强调都不为过。你别小看这个初始化C里new出来的对象不会自动清零如果手写结构体忘了把left、right置空后面遍历时if(root-left)这种判断就会读到随机地址轻则结果错乱重则直接Segmentation Fault。我自己带新人时反复强调一件事指针不初始化等于给程序埋了一颗定时炸弹。那么为什么树要用指针而不能像数组那样连续存储你可以把数组理解成酒店的一排房间房号连续找隔壁房间直接1就行。但二叉树的节点增删频繁而且父子关系不是线性的如果强行用连续内存存每次插入都得搬动大片数据。指针更像每个人手里拿着一张写着别人地址的纸条——你只要找到根节点顺着纸条就能走遍整棵树而不需要所有人住在同一栋楼里。这就是链式存储的核心逻辑用额外的指针开销换来插入删除的灵活性和结构的动态性。1.2 三种深度优先遍历理解递归的顺序感二叉树的遍历是后面所有算法的地基先序、中序、后序这三种写法几乎是面试必考。很多人背代码背得滚瓜烂熟但让他讲一下为什么中序的结果是左-根-右就卡住了。其实递归遍历的本质极简单每个节点都做三件事——访问自己、访问左子树、访问右子树区别只是顺序。void preorder(TreeNode* root) { if (!root) return; printf(%d , root-val); // 先序先访问自己 preorder(root-left); preorder(root-right); } void inorder(TreeNode* root) { if (!root) return; inorder(root-left); printf(%d , root-val); // 中序左子树处理完再访问自己 inorder(root-right); } void postorder(TreeNode* root) { if (!root) return; postorder(root-left); postorder(root-right); printf(%d , root-val); // 后序最后访问自己 }注意递归函数里那个if(!root) return这是所有树递归的终止条件。很多报错就报在这里你递归进去的时候没有判空然后访问了nullptr的成员变量比如root-left空指针哪来的left程序当场崩溃。所以我的习惯是不管什么递归函数第一行永远先写空指针判断这应该是肌肉记忆级别的操作。至于为什么会用递归这种看上去不太聪明的方式因为函数调用栈天然就帮你记住了下一步该干嘛。你去商场找某个店铺电梯到了三楼发现走错了就得回到一楼重新看指示牌——递归调用正是在返回时接着执行之前没做完的事情。树的遍历完美匹配这种先深入、再回溯的结构递归实现写起来只有三行换成非递归用显式栈模拟代码量翻倍还容易出错。1.3 层序遍历队列的经典应用场景深度优先遍历是从跟节点一路捅到叶子广度优先遍历则是一层一层扫过去也就是层序遍历。实现层序遍历需要队列这个思路其实是上篇栈队列知识的自然延伸void levelOrder(TreeNode* root) { queueTreeNode* q; if (root) q.push(root); while (!q.empty()) { TreeNode* cur q.front(); q.pop(); printf(%d , cur-val); if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } }如果你需要把每一层单独输出成一行就多用一个技巧while循环内部先记下当前队列的size这size个节点就是当前层的全部节点处理完它们再进入下一层。这个技巧在求二叉树宽度、判断完全二叉树、或者做锯齿形遍历时非常实用。我见过不少人在层序遍历里漏判cur-left为空的情况直接把空指针push进队列取出来再访问-val一大半的运行时错误就是这么来的。层序遍历的要点其实只有一条入队之前先确认这个指针不是nullptr。2. 树的进阶操作与报错玄学的真相2.1 求二叉树深度递归返回值的传参陷阱求二叉树的深度高度是另一个必考问题递归写法其实很简洁int maxDepth(TreeNode* root) { if (!root) return 0; return max(maxDepth(root-left), maxDepth(root-right)) 1; }这段代码的逻辑是一棵树的高度 左子树和右子树高度的较大值 1空树高度为0。看起来简单但我在辅导时发现很多人会写成一个经典的错误版本——把深度当成参数往下传// 错误示范这么写每个节点都会拿到一个全新的depth副本 void getDepth(TreeNode* root, int depth) { if (!root) return; depth; getDepth(root-left, depth); getDepth(root-right, depth); }问题在于参数传递是按值拷贝的你在左子树里加出来的depth根本不会传回给根节点右子树拿到的还是根节点那个值。要是改成传引用int depth又容易在回溯时忘了恢复现场。我自己更推荐直接用返回值方案干净利落。如果你非要传引用一定要在递归返回后手动减回去这个恢复现场的操作就是下一节要讲的回溯思想雏形。2.2 搜索二叉树和平衡二叉树两个高频判定题搜索二叉树BST的判定是典型的看着容易一写就错的题。很多人的第一反应是递归判断左右孩子的值是否满足大小关系像这样// 错误示范只比较父节点和直接孩子 bool isBST(TreeNode* root) { if (!root) return true; if (root-left root-left-val root-val) return false; if (root-right root-right-val root-val) return false; return isBST(root-left) isBST(root-right); }但BST的约束是全局性的左子树所有节点的值都必须小于根节点右子树所有节点的值都必须大于根节点。上面这段代码会漏掉一种情况根节点的左子树的右孩子可能比根节点还大但它大于自己的父节点所以局部的递归判断发现不了。正确做法是给每个递归调用传一个允许的取值范围bool isBST(TreeNode* root, long long minV, long long maxV) { if (!root) return true; if (root-val minV || root-val maxV) return false; return isBST(root-left, minV, root-val) isBST(root-right, root-val, maxV); }还有一个更聪明的等价做法中序遍历BST得到的结果必然严格递增。所以你可以先中序遍历把结果存到数组里再检查数组是否单调递增。这个思路在面试中很好用而且能顺便加深你中序遍历和BST关系极强的印象。平衡二叉树AVL的判定也经常和深度问题绑在一起每个节点的左右子树高度差不超过1。这题的递归写法需要返回两个信息——这棵树平不平衡和这棵树有多高。C写起来返回结构体或者用引用参数都行我习惯用结构体struct Info { int height; bool balanced; }; Info checkBalance(TreeNode* root) { if (!root) return {0, true}; Info left checkBalance(root-left); Info right checkBalance(root-right); bool balanced left.balanced right.balanced abs(left.height - right.height) 1; return {max(left.height, right.height) 1, balanced}; }这种一次递归同时算多个指标的思路在二叉树题目里特别常见比如同时求直径和深度、同时判断BST和平衡性都是这个套路。2.3 线索二叉树利用空指针做文章线索二叉树是教材里一定会提、但很多人觉得没什么用的内容实际上它是理解指针还能这么玩的绝佳素材。一个n节点的二叉树有n1个空指针没被利用线索二叉树的思路就是让这些空指针指向前驱或后继节点从而在遍历时不需要递归、不需要栈。结构上需要两个标记位struct ThreadNode { int val; ThreadNode* left; ThreadNode* right; bool ltag; // false表示left指向左孩子true表示left指向前驱 bool rtag; // false表示right指向右孩子true表示right指向后继 };中序线索化的核心是一个边走边改的过程用一个pre指针记录当前节点的前一个访问节点void inorderThread(ThreadNode* root, ThreadNode* pre) { if (!root) return; inorderThread(root-left, pre); if (!root-left) { root-left pre; root-ltag true; } if (pre !pre-right) { pre-right root; pre-rtag true; } pre root; inorderThread(root-right, pre); }构建完之后中序遍历就可以非递归地顺着线索走了。这个过程最锻炼人的地方是你要时刻区分left到底是孩子还是线索判断条件就是ltag。我刚学那会儿老是搞混后来想通了一个类比线索二叉树像城市里占用了盲道的电线杆平时用不上但真要在没有导航的情况下走一遍这些电线杆就是路标。这个知识点在面试里出现频率不算高但因为大部分人学得含糊你能说清楚反而容易加分。2.4 运行时错误排查空指针、野指针与递归爆栈回到这个大家最关心的为什么总是报运行时错误。我总结了四个高频原因按出现频次排序错误类型典型场景排查方法空指针访问未判空直接访问root-left-val递归函数第一行判空调试看调用堆栈野指针delete节点后没置nullptr后续又访问delete后立即置空不要怀抱侥幸内存泄漏new了节点析构时没有递归释放写析构函数递归delete或用智能指针栈溢出递归深度过大例如单链树递归改显式栈或考虑非递归写法空指针访问是最常见的。比如你写了一个查找函数目标值不存在时返回nullptr然后调用方直接对返回值取成员不崩才怪。对付空指针没什么高端技巧就是你得形成一套防御式编程的习惯每个指针用之前先问一句它可能为空吗。野指针在二叉树里出现得比较隐蔽。看这段delete root-left; // 注意delete只是释放了那块内存root-left仍然存着那个地址 // 如果后面再访问 root-left-val行为完全不确定 root-left nullptr; // 这才是干净的做法内存泄漏在二叉树里尤其容易发生你只delete了根节点左右子树的节点全部泄漏。C里必须手动写递归释放void destroyTree(TreeNode* root) { if (!root) return; destroyTree(root-left); destroyTree(root-right); delete root; }还有一种是调试时才能看出来的栈溢出。当二叉树退化成链表比如插入顺序是1,2,3,4,5树的高度变成5递归深度也变成5看起来没事但如果插入一万个有序节点递归函数调用栈直接爆掉。遇到这种问题要么用迭代遍历要么提前做好平衡化。我的排查建议是不要只用printf大法学会用调试器看调用堆栈。在VSCode或Visual Studio里下断点程序崩溃时打开调用堆栈窗口你就能一眼看到崩溃发生在哪个函数的第几行、是谁调用了它。绝大多数二叉树运行时错误靠这个操作十分钟内就能定位。3. 图从邻接矩阵到邻接表的选型实战3.1 两种存储结构的选择逻辑别只会背定义图论是很多人的劝退点但如果你把存储结构吃透后面的算法基本就是套模板。图的两种经典存储方式是邻接矩阵和邻接表它们没有绝对的好坏只看你的图长什么样。邻接矩阵用二维数组存g[i][j] 1表示i到j有边。判断任意两个节点是否直接相连是O(1)代价是空间始终是O(V^2)。如果一张图有10000个节点光矩阵就要开一亿个位置就算每个位置只存一个bool也是100MB级别这还没算运行时的内存碎片。所以邻接矩阵只适合稠密图——节点不多、边很多的时候比如几十个节点的带权图。邻接表用vectorvectorint存每个节点的邻居都放在一个vector里。空间只和边数相关O(VE)遍历某个节点的所有邻居也只要扫一遍它的vector这在做DFS、BFS时效率极高。绝大多数算法题和工程场景都推荐邻接表。两者对比看这张表就够了维度邻接矩阵邻接表空间O(V^2)与边数无关O(VE)稀疏图省空间判断i到j是否有边O(1)需要扫邻居列表最坏O(V)遍历i的所有邻居O(V)要扫一整行O(degree)只扫真实邻居适合场景稠密图、需要频繁查边稀疏图、图算法标配C写邻接表最常见的就是这种形式带权图就把int换成pairvectorvectorint adj(n); // 无权图 vectorvectorpairint, int wadj; // 带权图pairto, weight // 添加无向边 adj[u].push_back(v); adj[v].push_back(u);3.2 DFS递归框架、visited数组与连通分量图的DFS和树的DFS非常像唯一多出来的就是visited数组。因为树天然没有环你从根往下递归永远不会回到已经到过的节点但图可能有环不记录访问状态就会死循环。void dfs(int u, vectorvectorint adj, vectorint visited) { visited[u] 1; printf(%d , u); for (int v : adj[u]) { if (!visited[v]) { dfs(v, adj, visited); } } }这个模板几乎可以解决所有从某个点出发能到达哪些点的题目。比如求连通分量数量遍历所有节点没访问过就调用一次dfs调用次数就是连通分量个数。这个思路在处理朋友关系网省份数量这类题时直接套就行。递归DFS有一个常被忽略的坑如果图是一条长链比如几万个节点串在一起递归会爆栈。工程上我会提前评估递归深度或者直接用显式栈写法void dfsIter(int start, vectorvectorint adj, vectorint visited) { stackint st; st.push(start); visited[start] 1; while (!st.empty()) { int u st.top(); st.pop(); printf(%d , u); for (int v : adj[u]) { if (!visited[v]) { visited[v] 1; st.push(v); } } } }注意显式栈写法里visited标记是在入栈时设置的不是出栈时。如果出栈时才标记同一个节点可能被多个邻居反复入栈既浪费又容易出逻辑问题。这个细节我在代码评审里至少强调过十遍。3.3 BFS与最短路径dist数组的天然作用BFS在图上最常见的应用就是求无权图的最短路径。因为BFS一层一层扩展第一次到达某个节点时走的路径必然最短所以用一个dist数组记录从起点到每个节点的最短步数非常自然void bfs(int start, vectorvectorint adj, vectorint dist) { queueint q; dist[start] 0; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { // 没访问过 dist[v] dist[u] 1; q.push(v); } } } }这里用dist[v] -1代替单独的visited数组一举两得。BFS的经典应用包括迷宫最短路把格子转成图、单词接龙、社交网络六度分隔等。学到这里如果你回头再看二叉树的层序遍历会发现两个套路惊人的一致都是队列、都是逐层扩展只不过图的下一层要通过邻接表去取邻居。拓扑排序也是BFS思想的延伸核心是从入度为0的节点开始一层层剥掉// 思路伪代码 计算每个节点的入度indegree 把入度为0的节点全部入队 while (队列不空) { u 出队 把u加入拓扑序列 for (v : adj[u]) if (--indegree[v] 0) 入队 }如果最后拓扑序列长度不等于节点总数说明图里有环。这个有环检测在很多依赖关系题目里都是核心步骤比如课程表问题。4. 基础算法串讲从排序到回溯的刷题映射4.1 三种必须手写的排序快排、归并、堆排数据结构学完基础算法里第一个绕不开的就是排序。虽然工程上大多数时候直接调std::sort但面试和刷题时手写排序的频率相当高因为排序背后藏着分治、递归、堆这三种更底层的思维。快速排序的partition可以说是面试题里的常青树TopK问题、寻找第K大元素都基于这个思想。核心逻辑是选一个基准值把数组分成小于基准和大于基准两块然后递归处理两边int partition(vectorint a, int l, int r) { int pivot a[r]; int i l; for (int j l; j r; j) { if (a[j] pivot) { swap(a[i], a[j]); i; } } swap(a[i], a[r]); return i; } void quickSort(vectorint a, int l, int r) { if (l r) return; int p partition(a, l, r); quickSort(a, l, p - 1); quickSort(a, p 1, r); }归并排序的价值在于它是稳定的而且可以用来求逆序对数量。思路是先把数组拆成两半分别排好序再合并成一个有序数组。合并的过程是经典的双指针操作单独拿出来也能解决合并两个有序数组这类题。堆排序的价值在于优先队列这个概念。C里直接用priority_queue就能拿TopK但你要知道堆的本质是一个完全二叉树存储在数组里parent的下标是(i-1)/2。也就是说你刚学完二叉树立刻就能在数组上体验树形结构的实际应用这种联系非常有意思。4.2 二分查找边界的翻车点与防溢出写法二分查找代码短、思路简单但边界条件堪称翻车重灾区。最经典的问题是while (l r) 还是 while (l r)mid取左中位还是右中位这些细节在不同题目里有不同答案死记硬背容易记混。我自己的模板是这样遇到找某个target的下标用闭区间版本int binarySearch(vectorint nums, int target) { int l 0, r (int)nums.size() - 1; while (l r) { int mid l (r - l) / 2; // 防止 int 溢出 if (nums[mid] target) return mid; else if (nums[mid] target) l mid 1; else r mid - 1; } return -1; }这里有一个很多新手不知道的小技巧用mid l (r - l) / 2 而不是 (l r) / 2。因为当l和r都接近int上限时l r可能溢出成负数这在LeetCode那种大数case下真的会发生。另外while循环结束后l和r的位置也有信息量——如果target不存在l是第一个大于target的位置r是最后一个小于target的位置这个性质可以用来解决查找插入位置的题。4.3 回溯算法树的深度遍历就是天然的回溯框架回溯算法是基础算法里和树结合最紧密的一个。全排列、组合总和、N皇后、岛屿数量这些题的代码框架几乎一样。要理解回溯先想清楚一件事每一层递归就是决策树的一个节点递归下去是做选择递归返回是撤销选择。我总结的模板是这样void backtrack(vectorint path, vectorbool used, vectorint nums) { if (path.size() nums.size()) { // 找到一个排列保存结果 return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; used[i] true; path.push_back(nums[i]); backtrack(path, used, nums); path.pop_back(); // 撤销选择 used[i] false; } }backtrack函数内部这个过程想象你站在二叉树的一个节点上往左走一步记录一下回来再往右走一步——这就是DFS也就是回溯。所以你会发现学好了二叉树的递归遍历回溯算法的骨架你已经会了差的只是状态怎么保存和怎么撤销这两步。这也是为什么我强烈建议初学者先啃透二叉树再碰图和回溯顺序绝对不能乱。剪枝是回溯的进阶话题。比如组合总和里如果当前和已经超过目标值直接return不需要再往下递归。别小看这个if判断它是回溯算法从能跑到能过题的关键。5. 环境配置与工具链VSCode跑C/C的完整经验5.1 VSCode配置时最容易踩的三个坑这个章节必须写因为我发现很多读者不是不会写树和图的代码而是压根没把运行环境配好导致写二叉树程序时总是报运行时错误这个问题的另一半其实是根本跑不起来。VSCode只是一个编辑器它自己不会编译C/C代码。你要装编译器Windows上最常用的是MinGW-w64自带g和gdb或者直接装Visual Studio用MSVC。配置流程说穿了只有三个文件tasks.json定义编译任务。核心参数是-g生成调试信息和-Wall打开所有警告launch.json定义调试任务。核心是miDebuggerPath指向gdb路径c_cpp_properties.json配置includePath让IntelliSense认识头文件最常见的问题tasks.json里编译器路径写错或者编译器没加入PATH。你可以在终端里先敲g --version确认能不能输出版本信息这是最快的诊断方式。第二个坑是路径不能有中文和空格VSCode的很多插件对中文路径支持并不友好这也是程序崩溃的隐藏帮凶。第三个坑是你打开了文件夹却忘了在根目录建.vscode目录配置永远不生效——注意.vscode必须和你的源码在同一个工作区根目录下。我建议最小可用的tasks.json配置参考{ version: 2.0.0, tasks: [ { type: cppbuild, label: build, command: g, args: [ -g, -Wall, -stdc17, ${file}, -o, ${fileDirname}\\${fileBasenameNoExtension}.exe ], group: build } ] }这里的${file}指当前打开的源文件-stdc17按需要调整用C11还是C17都行。要调试的话launch.json里的program字段要和tasks.json生成的exe路径完全一致否则调试器起不来。5.2 Win11下用Visual Studio跑C/C代码的注意事项如果你不想折腾VSCodeWindows 11下直接用Visual StudioVS其实更省心。流程是新建空项目→右键源文件添加新建项→选C文件.cpp→写代码→按F5调试。注意VS里C和C有点小区别如果你的文件后缀是.c编译器按C语言标准处理结构体前面要加struct比如struct TreeNode* t如果后缀是.cpp就可以直接用TreeNode* tC的struct不需要struct前缀。VS下经常遇到的报错有两种都是环境层面的。一是无法启动程序系统找不到指定的文件说明你没有编译成功就按了F5或者main函数写错导致链接失败。二是LNK2019无法解析的外部符号多半是写了声明没写定义比如声明了createTree()但没实现或者用了某个函数但头文件没包含。这些问题只要看输出窗口的错误信息按行号定位基本都能解决。VS调试树的递归函数其实比VSCode更直观。我把断点打在递归调用那一行然后看调用堆栈窗口每一次递归调用都在栈上留一层记录你能对着堆栈一层层看每个节点的值这样分析为什么这个节点的left指针是空的就非常清晰。5.3 调试技巧条件断点让递归排查事半功倍最后分享几个实战调试技巧这些是我在排查二叉树和图程序时真正用过的。第一个是条件断点。比如你想在某个节点的值等于5的时候停下来不要在循环里写if (root-val 5)打个普通断点那样每个节点都会停一次。正确做法是在断点上右键设置条件输入root-val 5调试器只在满足条件时才触发。这在树特别大的时候效率极高。第二个是观察递归调用栈。很多二叉树报错的本质是访问了空指针。崩溃那一刻打开调用堆栈窗口你会看到类似inorder: 没有可用源代码后面跟着一串调用记录。从栈顶往下数就能看到这次访问是怎么一路递归下来的。配合自动窗口查看当前root的值马上就能发现某个节点是nullptr。第三个技巧和BFS有关调试图算法时我习惯把visited数组或dist数组添加到监视窗口每次入队出队都看一眼数组状态。这样能非常直观地看到BFS的层次扩散过程比盯着代码空想要清楚得多。这些技巧不是学院派教给你的纯靠平时踩坑积累。你现在调试一次空指针比我当初对着屏幕发呆两个小时效率高得多。6. 一些书本之外的个人体会写到这里这篇下篇该收尾了。回头看二叉树、图和基础算法这三块内容其实有一条暗线串着递归的理解深度决定你能走多远。树的遍历是递归图的DFS是递归回溯是递归甚至二分查找也可以用递归视角理解。我见过很多同学问为什么我每次看题解都懂自己写就废答案往往是递归的递和归没有真正融入直觉。我给新人的建议是学二叉树的时候拿一张纸手动模拟每一个递归调用的进出栈过程模拟五六个节点的小树就够重点体会递归返回之后发生了什么。这一步跨过去了后面图算法和回溯算法都会顺很多。最后再分享一个小技巧写树的递归函数前先在注释里写清楚三件事——这个函数的输入是什么、返回什么、终止条件是什么。我自己的代码风格是任何树函数都强制写这三行注释。听起来很麻烦但它能在你递归到一半忘记自己在干什么的时候像路标一样把你拉回来。数据结构和算法这条路没有捷径但有了顺手的环境配置、扎实的递归功底和清晰的调试手段至少能把为什么别人跑得稳我却总崩溃这个心结解开一大半。