1. 从一道考研真题说起为什么树是数据结构的分水岭我见过太多人学数据结构前面线性表、栈、队列都学得好好的一到树就突然掉队。这不是能力问题而是思维没有切换过来——之前的逻辑是“一个接一个”到了树这里变成了“一个下面挂多个”。你从单向思维跳到了分叉思维不适应太正常了。但树这个章节无论是期末考、考研408还是后续的算法刷题、系统设计都绕不开。先说清楚“树”到底是什么。按严蔚敏那本经典教材的说法树是nn≥0个结点的有限集。n0时叫空树这是合法的定义代码里对应的就是空指针。n0时有且仅有一个根结点其余的结点可以划分成m个互不相交的有限集每个子集又是一棵树。这个定义你反复读三遍你就能看出来树本质上是递归的所以后面你写遍历、写查找、写删除都会大量用到递归。从408考研的角度来说树的考点非常固定基础概念、二叉树的性质、二叉树的四种遍历、线索二叉树、哈夫曼树与编码、BST与AVL再往上是B树、B树和红黑树的概念。这套体系以前我也觉得是“为了考试而考试”直到我后来真正去写编译器相关的东西、去调数据库索引、去看文件系统实现时才发现教材里的每一个概念都能在工程里找到对应物。所以这篇博文我的主线是“树的基础概念 二叉树全套代码 常见变种树的用途”用C/C一步步把代码写出来并把我自己写过、坑过的地方全部标出来。无论你是考研党、期末复习党还是转码需要系统补数据结构这篇文章的目标是让你跟着代码过一遍之后自己能独立把一棵二叉树建出来、遍历出来并且能说清楚每种变种树到底解决什么问题。提示本文所有代码基于C编写但尽量兼容C的写法。如果你正在用C语言只需要把new换成malloc、把delete换成free再顺手把引用参数换成指针*即可。2. 树的定义与存储结构先把“地基”打牢2.1 术语与概念度、深度、叶子结点怎么理解树的术语看着多其实背后全是生活化的场景。拿公司组织架构来类比CEO是根结点下面挂CTO、CFO、COO每个人再往下挂自己的下属一挂就是一棵树。几个必须烂熟于心的术语结点树的基本单位存储数据本身。度一个结点拥有的子树个数。树的度就是所有结点里最大的度。度为0的结点叫叶子结点或者叫终端结点。双亲与孩子结点的直接上层叫双亲也就是父结点它引出的子树的根叫孩子。兄弟同一个双亲的孩子之间互称兄弟。深度从根开始根为第1层从上往下数到某个结点经过的层数。整个树的最大层数叫树的深度也叫高度。森林nn≥0棵互不相交的树的集合。这个概念在后缀表达式、并查集相关的题目里都出现过。这些概念为什么要背因为后面所有的算法、代码、证明都建立在这些术语之上。比如二叉树的性质里“度为0的结点数 度为2的结点数 1”这条性质你不理解“度”就完全懵圈。2.2 树的三种存储方式各有各的脾气树因为每个结点的孩子数量不固定存储方式不能像线性表那样“从头到尾排一条线”。实际工程和教材中主要用三种方式存储方式核心思路优点缺点双亲表示法每个结点记录自己的数据 父结点的下标找父结点O(1)结构简单找孩子要遍历整个数组孩子表示法每个结点记录数据 所有孩子结点的指针/下标列表找孩子方便每个结点要动态维护孩子链表孩子兄弟表示法每个结点记录数据 第一个孩子指针 下一个兄弟指针把任意树转成二叉树统一形态找父结点麻烦双亲表示法在写并查集Union-Find时是最自然的结构——每个结点只需要记录它的父结点是谁路径压缩时直接改父指针就行。孩子表示法更适合“从上往下查”的场景。而孩子兄弟表示法是树转二叉树的理论基础考试经常考“如何把多叉树用二叉树存储”答案就是孩子兄弟表示法。有意思的是这三种方式都不完美这正好说明了一件事数据结构没有银弹只有权衡。你想快速知道父亲就别想快速知道孩子你想方便遍历子树就得接受找父结点费劲。3. 二叉树树结构里的“一等公民”3.1 为什么是二叉树它到底特殊在哪因为二叉树是“所有树形态里最简单又能表达一切树结构的形态”。任何一棵多叉树用孩子兄弟表示法都能转成二叉树。而且二叉树性质极其规整一个结点最多两个孩子左子树和右子树是严格区分的这就带来了很多数学上的好性质。必须记住的3条核心性质第i层最多有2^(i-1)个结点i≥1。深度为k的二叉树最多有2^k - 1个结点k≥1。对于任意一棵非空二叉树n₀ n₂ 1其中n₀是叶子结点数n₂是度为2的结点数。第三条性质特别有意思它是我当年期末考必考的一道填空题。证明思路也不难从边的角度考虑。二叉树中每个结点除根外都有一条边从它的父结点连过来所以总边数 n - 1。另一方面度为2的结点贡献2条边度为1的结点贡献1条边度为0的结点贡献0条边所以n - 1 2n₂ n₁。又因为n n₀ n₁ n₂带入一算就出来了。完全二叉树和满二叉树的概念也常考。满二叉树是“除了叶子结点外每个结点都有两个孩子”完全二叉树是“只有最后一层可能不满而且最后一层的结点必须从左到右连续排列”。堆Heap就是完全二叉树在数组上的经典应用这也是为什么堆排序能直接在数组里原地操作的底层原因。3.2 顺序存储还是链式存储其实不用纠结二叉树的存储有两种主流方案。顺序存储就是按“从上到下、从左到右”给结点编号存在数组里。如果根结点下标为1那么任意下标为i的结点它的左孩子下标是2i右孩子是2i1父结点是i/2整数除法。这个性质让完全二叉树可以用极低的存储成本实现——不需要存指针只用数学公式就能找到孩子的地址。堆、线段树都是这么干的。但普通二叉树用顺序存储就很浪费空间了极端情况下会退化成一条“斜树”可能深度是n数组长度要开到2^n的量级绝大多数位置都是空的。所以工程里更常见的是链式存储每个结点长这样struct TreeNode { int val; // 数据域 TreeNode* left; // 左孩子指针 TreeNode* right; // 右孩子指针 TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} };三个字段干净利落。这种写法几乎所有讲二叉树的教材都用你刷LeetCode的时候也是这个定义。从这里就能看出二叉树之所以是“一等公民”很大程度上因为它天然适合用指针来表示两路分支而多叉树如果每个结点挂的孩子数量不固定要么用vector要么用链表写起来都没这么优雅。4. 遍历算法递归不亏迭代是加分项4.1 前序/中序/后序递归遍历代码短到你不敢信二叉树的遍历是后面一切tree题目的基础。所谓前序、中序、后序指的是“根结点什么时候被访问”前序是“根左右”中序是“左根右”后序是“左右根”。很多初学者背这个口诀背得滚瓜烂熟但真到手写代码就不知道从哪下手。其实诀窍是把每个结点都当成一棵独立的树递归调用就是“让子树自己处理自己”。// 前序遍历根 - 左 - 右 void preorder(TreeNode* root) { if (root nullptr) return; visit(root); // 先访问根 preorder(root-left); // 再遍历左子树 preorder(root-right); // 最后遍历右子树 } // 中序遍历左 - 根 - 右 void inorder(TreeNode* root) { if (root nullptr) return; inorder(root-left); // 先遍历左子树 visit(root); // 再访问根 inorder(root-right); // 最后遍历右子树 } // 后序遍历左 - 右 - 根 void postorder(TreeNode* root) { if (root nullptr) return; postorder(root-left); // 先遍历左子树 postorder(root-right); // 再遍历右子树 visit(root); // 最后访问根 }上面三个函数的结构一模一样只是visit的位置不同。你如果打印出来看中序遍历一棵BST的结果一定是有序的——这个性质后面所有基于BST的算法都会用到。而前序遍历的结果配合空指针标记可以用来序列化一棵树这也是很多序列化方案比如LeetCode的题面表示法的底层原理。递归遍历为什么好理解因为“以当前结点为根的子树”和“整棵树”是同构的大问题拆成小问题小问题和原问题一模一样这是递归的最理想场景。但递归也有代价——函数调用栈深度跟树高成正比当树退化成链表时深度就是n容易爆栈。所以你需要会写非递归版本。4.2 非递归遍历手动维护栈思路完全不一样非递归遍历的核心思想是用显式的栈std::stack模拟系统函数调用栈。前序和中序的非递归写法可以共用一个模板// 非递归前序遍历 vectorint preorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* st; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { result.push_back(cur-val); // 访问根 st.push(cur); cur cur-left; // 一直往左走 } cur st.top(); st.pop(); cur cur-right; // 左子树完了转向右子树 } return result; }这个写法的关键点在于“一路向左”先沿着左子树把沿途所有结点压栈走到最左边为nullptr时弹出栈顶结点然后处理它的右子树。前序遍历的访问是在入栈之前中序遍历的访问是在弹出之后// 非递归中序遍历 vectorint inorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* st; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); result.push_back(cur-val); // 弹出时访问 cur cur-right; } return result; }对比一下就能发现前序和中序的非递归代码几乎只差一行——访问动作是放在“压栈前”还是“出栈后”。后序的非递归是最繁琐的因为根结点要在左右子树都访问完之后才能访问必须引入一个“是否已经访问过右子树”的状态。常见做法是用一个lastVisited指针或者把结点标记为“第二次出栈”再访问// 非递归后序遍历双栈法思路最清晰 vectorint postorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* st1, st2; if (root) st1.push(root); while (!st1.empty()) { TreeNode* node st1.top(); st1.pop(); st2.push(node); if (node-left) st1.push(node-left); if (node-right) st1.push(node-right); } while (!st2.empty()) { result.push_back(st2.top()-val); st2.pop(); } return result; }双栈法的原理很巧妙前序是“根左右”后序是“左右根”后序刚好是“根右左”的逆序。所以第一个栈先按“根右左”入栈先压左再压右遍历时先出右然后全部倒到第二个栈里输出顺序就变成了“左右根”。这个方法不要求你理解复杂的回溯状态写起来还不会出错面试笔试都很推荐。4.3 层序遍历队列就完事了没那么简单层序遍历是按“从上到下、从左到右”逐层访问最自然的实现是用队列做广度优先搜索BFS。vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (root nullptr) return result; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); // 当前层的结点数 vectorint level; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } result.push_back(level); } return result; }这里的重点是int size q.size()这一行。很多人第一次写BFS遍历二叉树时会直接写成while (!q.empty())然后每次pop一个结点、push两个孩子但这样根本分不清当前处理的是哪一层。先把size记录下来再把这一层固定数量的结点全处理完下一批孩子结点再进入下一轮循环才能按层输出。层序遍历的应用也很多求树的最大宽度、判断一棵树是否是完全二叉树、之字形遍历。热搜词里“树的之字形遍历”指的就是在偶数层反着输出实现方式也不难加一个bool isOdd标记每层处理完取反就行。我用Swift和Python都实现过同样的逻辑算法思想完全一致区别基本只在语法糖和内存模型上。5. 进阶树结构从BST到红黑树再到B树和哈夫曼5.1 二叉排序树与平衡二叉树链表的进化版二叉排序树BST的定义很好记对于任意一个结点左子树所有结点的值都小于它右子树所有结点的值都大于它而且左右子树也都是BST。这个定义决定了中序遍历BST的结果一定是有序的递增序列。BST的查找效率本来能到O(log n)但前提是树长得“平衡”。如果你按顺序插入1、2、3、4、5每次新结点都是右孩子BST就退化成了一条链表查找效率变成O(n)。这就是AVL平衡二叉树被提出的原因AVL要求每个结点的左右子树高度差平衡因子绝对值不超过1一旦失衡就通过旋转来调整。四种旋转LL、RR、LR、RL是408的老考点但工程里其实很少有手写AVL的场景因为C标准库的std::map和std::set用的是红黑树不是AVL。红黑树也可以理解为一种“软平衡”的BST——它不要求左右子树严格等深而是通过颜色约束和旋转保证从根到叶子结点的最长路径不超过最短路径的两倍。这个“不那么严格”的特点带来了一个工程上的好处插入删除时需要的旋转次数更少综合性能更好。所以数据库索引、Linux内核的进程调度器、Java的TreeMap底层全是红黑树。5.2 B树、B树数据库索引与文件系统的真相如果你接触过MySQL的InnoDB一定听说过B树。为什么数据库不用红黑树核心原因是磁盘IO。红黑树每个结点只存一个键值树高可能在几十层而每一层结点都存放在不同的“磁盘页”里。查一次要找十几个页每找一个页就是一次磁盘寻道性能直接崩掉。B树和B树的思路是“让一个结点装很多个键值”降低树的高度从而把磁盘IO次数压缩到二到三次。B树相比B树还有个关键区别B树只有叶子结点存储真正的数据记录内部结点只存索引键用于路由并且所有叶子结点用链表串起来范围查询时只需从头到尾遍历叶子链表。数据库的SELECT ... WHERE id BETWEEN 1 AND 100用B树做就是“树上的范围遍历”效率远高于B树逐结点回溯。在C/C工程里你基本不会亲手实现B树但了解它的“每个结点多键 层级更深 磁盘友好”这套思想对于理解数据库调优非常重要。很多同学问为什么自己写的SQL慢一看执行计划发现全表扫描本质就是没有利用好索引这种B树结构。5.3 哈夫曼树与哈夫曼编码一棵树解决压缩问题哈夫曼树也叫最优二叉树它的定义是“所有叶子结点都带权值且带权路径长度WPL最小”的二叉树。WPL的计算公式是每个叶子结点的权值乘以其路径长度再全部相加。构造哈夫曼树的贪心过程非常直白把所有结点看成只有根的单结点树放进优先队列小顶堆。每次取出权值最小的两棵树合并成一棵新树新树的根权值等于两者之和。把新树放回队列。重复2、3直到只剩一棵树。对应C的实现用std::priority_queue配合结构体排序即可。哈夫曼编码的应用场景很常见压缩软件里把出现频率高的字符用短编码出现频率低的用长编码整体编码长度就能缩短。你需要保证任意一个字符的编码都不是另一个字符编码的前缀这样才能无歧义地解码——哈夫曼树天然满足这个性质因为所有数据都存放在叶子结点上。注意哈夫曼编码的“带权路径长度”这个概念期末和408考试几乎必考一道计算题。你需要熟练掌握从“一组权值”构造哈夫曼树并求出WPL的完整手算过程因为考试不让你写代码但你得能算出和机器一样的结果。6. 实操中踩过的坑指针、递归深度与内存管理6.1 指针悬挂与空指针是新手翻车重灾区用C/C写树最常见的问题就是空指针。前序遍历、层序遍历前必须判空这个容易记得。但有个很容易忽视的场景是“删除结点”时更新父结点的指针。我在早期写BST删除函数时犯过一个经典错误只更新了本地变量没有更新父结点指向当前结点的指针。结果树里还残留着一个悬空指针访问越界程序直接崩掉。后来我总结出一个经验删除结点的本质是修改它的父结点指针所以要么使用二级指针要么在递归函数中返回新的子树根。// 使用返回值的方式避免指针悬挂 TreeNode* deleteNode(TreeNode* root, int key) { if (root nullptr) return root; if (key root-val) { root-left deleteNode(root-left, key); } else if (key root-val) { root-right deleteNode(root-right, key); } else { // 找到了待删结点 if (root-left nullptr) { TreeNode* rightChild root-right; delete root; return rightChild; // 把右孩子返回给上一层 } else if (root-right nullptr) { TreeNode* leftChild root-left; delete root; return leftChild; // 把左孩子返回给上一层 } else { // 两个孩子的场景找中序后继右子树最小值替代 TreeNode* successor root-right; while (successor-left ! nullptr) successor successor-left; root-val successor-val; root-right deleteNode(root-right, successor-val); } } return root; }这段代码模式非常通用不是直接操作父结点的指针而是通过递归的返回值把“新子树根”交还给上一层。这样就不存在悬空指针的问题了。你写树相关的代码时建议默认采用“返回子树根”的递归风格能省掉很多麻烦。6.2 递归深度二叉树也会栈溢出递归是否安全取决于树的高度。完全二叉树的深度大约log2(n)一万个结点深度也就是14非常安全。但最坏情况下树退化成链表递归深度等于结点数如果结点数目上了百万递归就会爆栈。实际工程里我遇到过一个场景一个解析表达式树的程序输入表达式嵌套太深几千层括号构建成的二叉树高度也随之变得很大递归计算表达式值的时候直接段错误。解决思路有两种把递归遍历改成显式栈的非递归版本前面写过的那个模板。在递归函数开头做深度限制超过阈值就报错退出。用C/C写树的时候递归深度问题一定要放在心上。你可以通过ulimit -s查看系统默认栈大小通常是8MB栈每层调用大概消耗几十到几百字节算一下就知道你的树高极限大概在哪里。6.3 内存泄漏每个new都要对应一个deleteC完全没有垃圾回收new出来的TreeNode如果不delete内存就泄漏了。树这种结构尤其容易漏因为结点之间互相引用你只delete根结点下面的子结点就全成了孤儿内存。所以销毁一棵二叉树时要采用后序遍历的顺序先销毁左右子树再销毁根结点。最好封装到一个析构函数或独立函数里void destroyTree(TreeNode* root) { if (root nullptr) return; destroyTree(root-left); destroyTree(root-right); delete root; }如果你用智能指针std::unique_ptr、std::shared_ptr内存管理的负担会小很多但shared_ptr在树上有个坑如果子结点反过来持有父结点的shared_ptr就会形成循环引用导致内存永远无法释放。所以在树这种“天然有环”的意识尽管父子关系是单向的但互相引用容易误加下要么用unique_ptr要么就老老实实手动管理。7. 树的工程应用不只是考试是真的有用7.1 文件系统目录本身就是一棵树你在Linux里执行find /看到的整个文件系统从根目录/开始一层层往下是典型的树结构。每个目录都可以包含子目录和文件子目录又可以继续包含下一级这是一棵“孩子数量不固定”的树。更进一步看Linux内核源码内存管理子系统里有大量数据结构其中红黑树用于管理虚拟内存区域VMA设备树Device Tree则是描述硬件拓扑的结构。从热搜词里能看到“linux如何进行设备树配置”“瑞芯微rk3568设备树”这类问题——设备树本质上就是描述板级硬件信息的树形结构驱动开发时要靠它告诉内核“哪个外接设备在哪个地址上、中断号是多少”。你理解了树这个基础形态再去看设备树的dts文件瞬间会觉得特别亲切无非就是一棵大的配置树。7.2 表达式树编译器里隐藏的树表达式求值、编译原理里最常见的一个结构是表达式树。表达式(a b) * (c - d)可以表示成一棵二叉树根是*左子树是a b右子树是c - d。中序遍历表达式树得到中缀表达式后序遍历得到后缀表达式逆波兰式前序遍历得到前缀表达式。我曾经写过一个小型的四则运算计算器用到的就是表达式树的思想先把中缀表达式转成后缀表达式再构建表达式树然后对树后序遍历求值。这个方法比直接在中缀上处理运算符优先级清晰得多因为树的层次天然表达了运算优先级——越深的子树优先级越高。如果你接到跟C/C语法分析、规则引擎相关的任务表达式树是绕不开的。7.3 前缀匹配字典树和高效检索字典树Trie是我个人很偏爱的一种树结构它把字符串公共前缀合并起来存储。比如cat、car、card共享ca这个前缀字典树就用一个结点表示共享前缀大幅降低了存储开销同时实现了O(字符串长度)级别的查询时间。搜索框自动补全、输入法词库匹配、IP路由表的最长前缀匹配用的都是Trie或其变体。热搜词里提到的“CTF”这类安全竞赛里也经常考Trie的字符串哈希和前缀统计。C/C实现Trie时最常见的方案是每个结点存一个长度为26的指针数组对应26个小写字母或者用哈希表存子结点。前者的查询速度快但空间固定就算只有两个字符每个结点也要占26个sizeof(指针)的空间后者节省空间但哈希计算有开销。实际项目我偏向于用map/unordered_map存子结点兼顾扩展性和空间。8. 常见问题速查表与避坑心得8.1 遇到问题先查这几条症状可能原因解决办法程序莫名其妙崩溃空指针未判空遍历/删除前检查root是否为nullptr遍历结果顺序不对递归中visit位置放错前序“根左右”、中序“左根右”、后序“左右根”对比代码重新定位中序遍历BST结果无序结点插入逻辑违反BST定义检查插入时比较方向确认左小右大递归层数深时崩溃栈溢出改用非递归栈版本或增加迭代式遍历内存泄漏严重只delete根结点用后序顺序销毁整棵树或改智能指针层序遍历分不清层未缓存queue.size()进入每层前先记录size再循环处理该层固定数量结点删除结点后树结构错乱父结点指针未更新改用返回新子树根的方式实现删除8.2 我自己总结的避坑心得先说VS Code配置C/C环境这件事。很多初学者在热词里搜“vscode配置c/c环境”装上C/C插件后直接点运行却说“gcc不是内部或外部命令”。这基本是环境变量没配好。MinGW-w64安装后需要把它的bin目录加到系统的Path里然后在终端输入g --version验证一下看到版本号再回去点F5就顺了。写树的调试我建议你在VS Code里装好Code Runner或者直接配置好tasks.json和launch.json这样点一下就能编译运行效率高很多。另外写树的时候强烈建议先用小规模样例测试。比如BST的插入手工在纸上画一个插入序列1、2、3、4、5你就能直观看到它退化成了链表。然后在代码里加一个计算树高的函数实测根深多少验证你的理解对不对。别上来就雕花先把最基础的建树、遍历、求高度、求叶子数这四件事写稳了再去挑战红黑树、B树的实现。链表和树之间的关系也可以加深一下——如果你会C/C的链表操作树结点的指针操作本质上就是“每个结点有多个next指针”只是这些指针指向的不再是线性后继而是左孩子和右孩子。所以链表学扎实了树的很多操作会自然迁移过去。9. 动手实践三步从零建一棵BST9.1 插入结点把代码写到肌肉记忆里BST插入的逻辑很简单但足够新手练习指针操作TreeNode* insertNode(TreeNode* root, int val) { if (root nullptr) { return new TreeNode(val); } if (val root-val) { root-left insertNode(root-left, val); } else if (val root-val) { root-right insertNode(root-right, val); } return root; }递归插入的终止条件是遇到空结点此时直接new一个新结点并返回。若值小于当前结点就去左子树插入若值大于当前结点就去右子树插入。等于的情况视题目要求决定是否去重这里选择忽略。注意这里同样用了“返回子树根”的模式。如果没有返回只是单纯递归调用父结点就永远不知道应该把新结点挂到它的左孩子或右孩子上。9.2 查找与求树高检验代码理解程度查找操作利用BST的性质比普通二叉树遍历更高效TreeNode* searchBST(TreeNode* root, int val) { if (root nullptr || root-val val) return root; if (val root-val) return searchBST(root-left, val); return searchBST(root-right, val); }求树高则用递归的典型结构树的高度等于左子树高度和右子树高度中较大的那个加1int treeHeight(TreeNode* root) { if (root nullptr) return 0; int leftH treeHeight(root-left); int rightH treeHeight(root-right); return (leftH rightH ? leftH : rightH) 1; }这两个函数加起来不到二十行。如果你能把它们和前面的四种遍历一次性写出来而且中途不卡壳说明你的树的基础已经打得不错了。9.3 完整示例create、insert、traverse一把梭最后给一个可以在本地直接编译运行的完整示例把上面的代码串起来。我习惯边写边用注释标记关键位置这样后续调试时能快速定位#include iostream #include vector #include queue #include stack using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} }; TreeNode* insertNode(TreeNode* root, int val) { if (root nullptr) return new TreeNode(val); if (val root-val) root-left insertNode(root-left, val); else if (val root-val) root-right insertNode(root-right, val); return root; } void inorder(TreeNode* root) { if (root nullptr) return; inorder(root-left); cout root-val ; inorder(root-right); } void levelOrder(TreeNode* root) { if (root nullptr) return; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); cout node-val ; if (node-left) q.push(node-left); if (node-right) q.push(node-right); } cout endl; // 每一层输出一行 } } void destroyTree(TreeNode* root) { if (root nullptr) return; destroyTree(root-left); destroyTree(root-right); delete root; } int main() { TreeNode* root nullptr; vectorint nums {5, 3, 7, 2, 4, 6, 8}; for (int x : nums) root insertNode(root, x); cout 中序遍历: ; inorder(root); cout endl; cout 层序遍历: endl; levelOrder(root); destroyTree(root); return 0; }这段代码在VS Code里配置好C/C环境后直接编译运行就能看到效果。中序遍历输出有序序列层序遍历按层打印出一个形状清晰的二叉树结构。你可以试着改一下插入的序列观察中序遍历结果始终有序这能加深你对BST定义的理解。我个人在实际操作中的体会是树这种结构看十遍不如自己写一遍。你去看别人的代码觉得都懂但真正自己动手建一棵树、遍历它、删一个结点才会碰到各种指针、边界和递归理解的问题。数据结构这门课最大的学习成本不是记忆概念而是把概念转化成能跑起来的代码。别怕出错出错了就把调试信息print出来一步一步看遍历顺序和结点的值比干瞪眼强十倍。最后再分享一个小技巧如果你在准备面试或者考研复试建议把“手写二叉树的四种遍历 求树高 求叶子数 判断两棵树是否相同”这些基础操作练到能默写的程度。这些代码量不大但覆盖了树这个主题80%的核心逻辑。有了这个基础再去啃红黑树、B树和哈夫曼树你会发现它们绝大多数复杂度都来自于操作细节而底层的“递归处理左右子树”这套思维方式早就已经刻在你的脑子里了。