1. 从线性表走到树为什么数据非得分叉不可刚把顺序表和链表啃完的那阵子我一度觉得数据结构也就那么点东西——数据排成一条线用下标或者指针把它们串起来查找、插入、删除各写几行代码就完事。这种一条线的结构学名就叫线性结构。它的天花板其实很明显数组随机访问是 O(1)但要在中间插一个元素后面全部得往后搬家O(n)链表反过来插入删除只要改几个指针可你想访问第 k 个元素只能从头一个个数过去还是 O(n)。用 C语言写起来不难难的是遇到它处理不了的问题。线性结构真正吃不下的是一对多的层级关系。你想想公司的组织架构一个总经理下面三个部门经理每个部门经理下面又有若干小组长这种关系你拿数组怎么摆再想想磁盘上的文件夹一个目录里既能放文件又能放子目录子目录里还能继续套。还有 JSON 数据、HTML 页面结构、一个算术表达式1 2 * (3 - 4)的嵌套括号——它们的共同点是每个节点可以有多个下属而每个节点最多只有一个上级。这种结构就是树。1.1 树到底换来了什么很多人学树的时候只知道背树是 n 个节点的有限集合但不清楚它到底解决了什么痛点。我把话说直白点树是用额外的结构约束换取更快的查找和更自然的层级表达。普通二叉树本身并不保证查找快但一旦你给它加上左子树所有节点都小于根右子树所有节点都大于根这条规则也就是二叉搜索树查找的期望复杂度立刻降到 O(log n)插入删除也在同一量级。再进一步如果树是平衡的AVL 树、红黑树最坏情况也能稳住 O(log n)。这就是为什么数据库索引用的是 B 树、B 树而不是有序数组——数组虽然二分查找也是 O(log n)可每次插入删除都要整体挪动磁盘上这么干代价太大了。一个直观的类比有序数组像一排按身高站好的队伍找人快二分但中间插个人后面全得挪。二叉搜索树像一棵家族谱系找人快加人也只是挂到某个枝丫下面别人不用动。1.2 用家谱一次讲透所有术语教材上树的术语又碎又多硬背效率极低。我的经验是全部映射到家谱上一遍就记住了根节点家族的始祖整棵树唯一没有父节点的那一个。叶子节点没有孩子的节点也就是家谱里没有后代的那一支末端。父节点 / 子节点 / 兄弟节点就是字面意思同一个爹的两个节点互为兄弟。节点的度这个节点有几个孩子。二叉树的度最大是 2。树的度整棵树中节点度的最大值。层次 / 深度根在第 1 层有的教材写第 0 层看教材口径从上往下数。高度从下往上数叶子节点高度为 1根的高度就是整棵树的高度。深度和高度这两个词最容易混也是考试最爱挖的坑。我自己的记法是深度是往下挖多深从根开始数高度是往上长多高从叶子开始数。对整棵树来说两者数值相等但对中间某个节点它俩通常不一样。写代码的时候如果递归返回值代表深度还是高度一定要在注释里写清楚否则查 bug 的时候能让你怀疑人生。然后是满二叉树和完全二叉树这俩只差一个字含义差很多类型定义直观理解满二叉树每一层的节点数都达到最大叶子全在最底层完美对称的一颗金字塔完全二叉树除最后一层外全满最后一层的节点从左到右连续排列中间不能有空位按层序编号后编号与满二叉树一一对应完全二叉树的价值在于它可以用数组存、且不浪费空间堆优先队列就是靠这个性质实现的。判断一棵二叉树是不是完全二叉树最经典的思路就是层序遍历一旦遇到某个节点只有右孩子没有左孩子或者遇到第一个孩子不全的节点之后又出现了带孩子的节点那就不是完全二叉树。1.3 树结构平时都藏在哪这东西不是只在课本里活着。你每天用的东西里到处是树文件系统的目录树ls -R打出来的就是一棵树。编译器里的抽象语法树AST你写的每一行代码都会被解析成一棵树再走一遍中序遍历就能生成表达式。数据库索引里的 B 树、B 树撑起了绝大多数查询性能。字典树Trie做前缀搜索、输入法联想、敏感词过滤的标准方案。哈夫曼树无损压缩的经典算法靠它给高频字符分配短编码。红黑树很多标准库的有序容器底层比如 C 的std::map用的就是它。机器学习里的决策树、回归树本质也是在特征空间上做递归划分。Linux 内核里的设备树用来在启动阶段描述板子上的硬件资源虽然格式和算法课上的树不一样但层级描述这个思路是通的。看出规律了吗凡是需要表达分类嵌套优先级前缀的场景树几乎都是第一选择。你学它不是为了考试是为了在遇到层级数据的时候脑子里能第一时间跳出正确的结构。2. 二叉树的两种存储方式指针版和数组版怎么选搞清楚概念只是第一步真正动手写的时候第一个卡点永远是这棵树在内存里到底长什么样有两种主流答案——链式存储和顺序存储。选错了后面写遍历、建树、销毁都会被拖累。2.1 链式存储结构体怎么写才规范C语言里链式存储的核心就是一个自引用结构体#include stdio.h #include stdlib.h typedef int ElemType; /* 想换成 char 或者结构体只改这一行 */ typedef struct TreeNode { ElemType data; /* 数据域 */ struct TreeNode *left; /* 左孩子 */ struct TreeNode *right; /* 右孩子 */ } TreeNode, *BiTree;这里有两个细节必须说清楚很多初学者栽在这上面第一指针域必须写成struct TreeNode *不能写TreeNode *。因为在结构体定义的内部TreeNode这个别名还没生效typedef 要到分号之后才完成。很多人图省事写TreeNode *left;编译直接报错然后挠头半天。第二typedef struct TreeNode { ... } TreeNode, *BiTree;这一行同时定义了两个东西TreeNode是结构体类型BiTree是指向它的指针类型。这样后面写BiTree T;和TreeNode *T;是一个意思。我个人不太推荐在教学代码里滥用BiTree因为它会让你一眼看不出这到底是个节点还是个指针调试的时候脑子要绕一圈。我自己的习惯是老老实实写TreeNode *可读性优先。创建一个节点标准写法是这样TreeNode *CreateNode(ElemType value) { TreeNode *node (TreeNode *)malloc(sizeof(TreeNode)); if (node NULL) { /* 这一句千万别省 */ return NULL; } node-data value; node-left NULL; node-right NULL; return node; }这里的if (node NULL)检查是我见过被跳过最多、出事也最多的一行。内存紧张、或者你在循环里疯狂建节点的时候malloc是有可能返回 NULL 的。省掉这个判断程序会在某个你完全想不到的地方崩掉而且崩的位置往往离真正的错误很远排查起来极其痛苦。2.2 顺序存储算好下标一行代码搞定父子关系顺序存储就是拿一个数组装节点。它只适合完全二叉树因为完全二叉树的节点可以按层序连续编号不留空洞。父子下标关系有两套口径必须记牢编号起点父节点下标左孩子下标右孩子下标从 1 开始i / 22 * i2 * i 1从 0 开始(i - 1) / 22 * i 12 * i 2#define MAXN 100 typedef struct { ElemType nodes[MAXN]; /* 从下标 1 开始用0 号位空着 */ int size; /* 当前节点个数 */ } SqBiTree;从 1 开始编号的好处是公式干净2 * i和2 * i 1一眼就能看懂代价是浪费一个数组元素。教材和考题大多用从 1 开始的口径工程代码里为了和for (i 0; ...)的习惯统一一般用从 0 开始。两套口径混用是低级但极高频的错误我在代码 review 里见过不止一次。顺序存储的致命弱点在于如果这棵树退化成一条斜树每个节点只有左孩子深度为 n 的斜树要占2^n - 1个位置但你实际只用了 n 个。深度 30 就直接爆掉了。所以顺序存储的使用范围很窄基本只用在两个地方堆和考试题。2.3 两种存储的选型对照对比项链式存储顺序存储空间开销每个节点多两个指针但按需分配无指针开销但可能大片浪费找父节点需要额外线索或遍历O(n)一行公式O(1)找孩子直接取指针O(1)一行公式O(1)插入删除改指针不搬数据可能触发大量搬移适用场景一般二叉树、形态不规则的树完全二叉树、堆、数组化实现是否怕退化不怕极怕空间指数级膨胀我给的结论很直接除非你在写堆或者做考试题否则一律用链式存储。顺序存储在一般二叉树上省下的那点指针空间远远抵不上它在形态不规则时的浪费。3. 四种遍历递归只有三行难点全在换个写法遍历是二叉树的核心操作没有之一。因为绝大多数对树的操作求深度、数节点、判断形态、查找、释放内存都是遍历 顺手做点事。你把遍历写熟了剩下的都是套路。3.1 先序、中序、后序差别只在访问放在哪一行递归版的三种遍历代码短到你会怀疑它凭什么是个考点void PreOrder(TreeNode *T) /* 先序根 - 左 - 右 */ { if (T NULL) return; printf(%d , T-data); /* 访问位置 1 */ PreOrder(T-left); PreOrder(T-right); } void InOrder(TreeNode *T) /* 中序左 - 根 - 右 */ { if (T NULL) return; InOrder(T-left); printf(%d , T-data); /* 访问位置 2 */ InOrder(T-right); } void PostOrder(TreeNode *T) /* 后序左 - 右 - 根 */ { if (T NULL) return; PostOrder(T-left); PostOrder(T-right); printf(%d , T-data); /* 访问位置 3 */ }规律是递归调用左右子树的顺序永远不变变的只是访问当前节点这句话插在哪个位置。插在第一次递归之前是先序插在两次递归之间是中序插在两次递归之后是后序。我把它叫做三行位置记忆法比背定义可靠得多考试紧张的时候也不会记错。但光会背顺序没用得知道每种遍历在实战里干什么先序适合做复制一棵树输出目录结构序列化这类工作因为根的信息最先处理。中序在二叉搜索树上中序遍历的结果就是从小到大的有序序列。这是 BST 最值钱的性质判断一棵树是不是 BST直接中序遍历看是否递增就行比递归比较上下界要直观。后序适合先处理孩子再处理自己的场景比如释放整棵树的内存、计算表达式树的值、统计子树大小。释放内存必须用后序原因在第五节细说。3.2 非递归遍历把递归的隐含栈自己搭出来面试里问非递归遍历不是为难你而是想看你知不知道递归调用背后发生了什么事。递归本质上是靠系统调用栈保存现场函数一路向左递归返回时再回来接着走右子树。非递归就是把这个现场用我们自己的栈管理起来。先序非递归最直白思路是先压右、再压左因为栈是后进先出后压的左孩子会先出来void PreOrderIter(TreeNode *T) { TreeNode *stack[100]; int top -1; if (T ! NULL) stack[top] T; while (top 0) { TreeNode *p stack[top--]; printf(%d , p-data); if (p-right ! NULL) stack[top] p-right; if (p-left ! NULL) stack[top] p-left; } }中序非递归稍微绕一点口诀是一路向左压栈弹出来就访问然后转向右子树void InOrderIter(TreeNode *T) { TreeNode *stack[100]; int top -1; TreeNode *p T; while (p ! NULL || top 0) { while (p ! NULL) { /* 一路向左边走边压 */ stack[top] p; p p-left; } p stack[top--]; /* 弹出即访问 */ printf(%d , p-data); p p-right; /* 转向右子树重复上面的过程 */ } }后序非递归是最麻烦的一个因为根必须在左右子树都处理完之后才能访问。我常用两个办法办法一双栈法。先按根 → 右 → 左的顺序做类似先序的遍历把结果压进第二个栈最后全部弹出顺序正好变成左 → 右 → 根。这个办法代码短、不易错代价是多一个栈的空间。办法二单栈加标记。用一个lastVisit指针记录上一次访问的节点或者给每个节点配一个入栈次数标记。逻辑上更省空间但边界条件多写的时候容易漏情况。我的建议是平时用双栈法空间换清晰度是划算的只有面试官明确要求单栈时再上标记法。3.3 层序遍历终于轮到队列登场层序就是一层一层从左到右扫。它和前三种不是一家人因为它靠队列而不是栈void LevelOrder(TreeNode *T) { TreeNode *queue[100]; int front 0, rear 0; if (T NULL) return; queue[rear] T; while (front rear) { TreeNode *p queue[front]; printf(%d , p-data); if (p-left ! NULL) queue[rear] p-left; if (p-right ! NULL) queue[rear] p-right; } }层序的价值被很多人低估了。它能干的活不少求树的宽度每层节点数的最大值、判断完全二叉树、求某个节点的层号、按层打印每层换行只要记录每层的节点数即可。求树宽度的时候有个小技巧不要边出队边入队地数而要在每轮循环开始时把当前的rear - front记下来那就是这一层的节点数然后只处理这么多个节点。3.4 把遍历变成顺手统计的工具遍历框架搭好之后统计类问题全是填空。求节点总数用先序或后序都行int CountNodes(TreeNode *T) { if (T NULL) return 0; return 1 CountNodes(T-left) CountNodes(T-right); }求叶子节点数只多一个判断int CountLeaves(TreeNode *T) { if (T NULL) return 0; if (T-left NULL T-right NULL) return 1; return CountLeaves(T-left) CountLeaves(T-right); }求树的高度取左右子树高度的较大值再加一int TreeHeight(TreeNode *T) { if (T NULL) return 0; int lh TreeHeight(T-left); int rh TreeHeight(T-right); return (lh rh ? lh : rh) 1; }注意if (T NULL) return 0;这个空树高度定为 0 还是 -1不同教材口径不同。定为 0 的话只有一个根节点的树高度是 1定为 -1 的话高度就是边数单节点树高度为 0。你写代码之前先跟题目或项目约定好不然算出来的结果差一测试用例就过不了。再举个稍微有意思的表达式树求值。中缀表达式建成树以后叶子是操作数内部节点是运算符后序遍历一遍就能算出结果。这也是很多计算器程序的底层实现思路——先转后缀表达式用栈再建树再后序求值。4. 二叉搜索树那条有序规则带来的收益和麻烦普通二叉树只是形状不带任何顺序约束查找得老老实实遍历O(n)。真正让树变得有用的是二叉搜索树BST它加的规则只有一句话对任意节点左子树上所有节点的值都小于它右子树上所有节点的值都大于它。4.1 查找和插入递归下来就是一条路径查找的逻辑顺着规则走就行比线性查找少走很多冤枉路TreeNode *BSTSearch(TreeNode *T, ElemType key) { while (T ! NULL) { if (key T-data) return T; else if (key T-data) T T-left; else T T-right; } return NULL; }插入也一样找到空位挂上去TreeNode *BSTInsert(TreeNode *T, ElemType key) { if (T NULL) { TreeNode *node CreateNode(key); return node; } if (key T-data) T-left BSTInsert(T-left, key); else if (key T-data) T-right BSTInsert(T-right, key); /* key 相等时不插入也可以按需求改成计数加一 */ return T; }这里有个坑必须提醒T-left BSTInsert(T-left, key);这个赋值不能省。很多人写成BSTInsert(T-left, key);就完事然后发现树永远是空的。原因是形参T是值传递函数内部的修改不会影响调用方只有把返回的新指针赋回给父节点的左右指针链接才建立起来。这个错误新手犯得特别多而且因为编译不报错、运行也不崩只是插入没效果排查时容易往错误的方向找。4.2 删除节点三种情况一种比一种烦删除是 BST 里最容易写错的操作。按被删节点的孩子数量分三类情况处理方式注意点叶子节点直接释放父节点对应指针置 NULL别忘了置 NULL否则成野指针只有一个孩子用唯一的孩子顶替它的位置要接回父节点不能只改自己的指针有两个孩子找左子树最大前驱或右子树最小后继替换再删掉那个替换节点替换的是数据不是节点指针这点最容易搞混有两个孩子时的标准做法我习惯用右子树最小值中序后继TreeNode *BSTDelete(TreeNode *T, ElemType key) { if (T NULL) return NULL; if (key T-data) { T-left BSTDelete(T-left, key); } else if (key T-data) { T-right BSTDelete(T-right, key); } else { if (T-left NULL) { /* 无左孩子右孩子顶替 */ TreeNode *tmp T-right; free(T); return tmp; } if (T-right NULL) { /* 无右孩子左孩子顶替 */ TreeNode *tmp T-left; free(T); return tmp; } /* 两个孩子找右子树最小节点 */ TreeNode *minNode T-right; while (minNode-left ! NULL) minNode minNode-left; T-data minNode-data; /* 数据搬过来 */ T-right BSTDelete(T-right, minNode-data); /* 删掉那个替身 */ } return T; }为什么用中序后继而不是随便挑一个因为后继节点一定大于左子树所有元素、小于右子树所有元素除了它自己把它放到根的位置上BST 的有序性质能完整保持。如果你图省事挑个别的节点顶上去整棵树的顺序就坏了后面查找会给出错误结果。而且后继节点最多只有一个右孩子删除它退化成了前两种简单情况逻辑自然收敛。4.3 退化BST 最大的软肋BST 的性能依赖树的形状。如果插入序列本身是有序的比如 1、2、3、4、5你会发现每个新节点都挂在右边最后长成一条右斜树查找退化成 O(n)跟链表没区别。这就是为什么工程里几乎不用裸 BST而是用 AVL 树或红黑树。AVL 树要求任意节点左右子树高度差不超过 1靠四种旋转LL、RR、LR、RL维持平衡。查找效率最高但插入删除时旋转频繁适合读多写少的场景。红黑树用颜色规则约束不追求严格平衡最长路径不超过最短路径的两倍。插入删除的调整次数更少适合读写都频繁的场景。标准库里的有序容器大多用它。理解这两种树不需要你手写全套旋转代码但必须明白它们存在的原因是防止 BST 退化。面试被问到为什么不用 BST 而用红黑树答因为 AVL 旋转太多、红黑树插入删除更省事、且两者都是 O(log n)比背定义有用得多。4.4 堆和哈夫曼树树上最实用的两个分支除了 BST 家族还有两个树结构在实际工程里出现频率极高。堆本质是一棵用数组存的完全二叉树分大顶堆和小顶堆。它只维护一条弱规则父节点不小于或不大于子节点。正因为规则弱插入删除都是 O(log n)建堆是 O(n)。优先队列、Top-K 问题、任务调度、Dijkstra 算法里的最小值选取全靠它。堆的上浮和下沉两个操作建议手写至少三遍写到不看代码就能默出来为止。哈夫曼树是带权路径长度最短的二叉树。构造方法很朴素每次从集合里挑出权值最小的两个节点合并新节点的权值是两者之和放回集合继续挑直到只剩一个节点。它的经典应用是哈夫曼编码——出现频率高的字符给短编码频率低的给长编码而且保证任何一个编码都不是另一个的前缀这叫前缀码靠字符只在叶子节点上来保证解码时不会产生歧义。这里有个细节值得点出来哈夫曼编码的解码之所以能唯一确定就是因为所有有效字符都放在叶子节点。如果某个字符放在内部节点上它的编码就会成为其他字符编码的前缀解码到一半就会歧义。这个设计不是随手定的是推导出来的。5. 建树、销毁与运行时错误的完整排查链前面讲的都是理想情况。真正上手写代码八成会遇到的问题是编译通过一运行就崩或者崩得莫名其妙。这一节我把最常见的坑和排查路径完整走一遍。5.1 一次真实的排查过程程序为什么报运行时错误假设你写了个程序从键盘输入一串数据来建一棵二叉树运行后控制台直接报了个内存访问违规。别急着一行行看代码按下面的顺序排查效率最高。第一步把输入规模缩到最小。只输入一个节点看程序是否正常。如果单节点就崩那问题一定在初始化或者输入逻辑不在递归。我见过太多人拿着 100 个节点的数据去调其实错误在第一行就发生了。第二步检查所有指针是否初始化。C语言里malloc出来的内存不会自动清零你必须手动把left、right置为 NULL。如果漏了这一步递归里的if (T NULL)判断就会失效程序拿着一个垃圾地址去解引用必崩。/* 错误示范left/right 是随机值 */ TreeNode *node (TreeNode *)malloc(sizeof(TreeNode)); node-data value; /* 忘记置 NULL后面递归进去就完了 */ /* 正确做法 */ TreeNode *node (TreeNode *)malloc(sizeof(TreeNode)); node-data value; node-left NULL; node-right NULL;第三步检查递归有没有终止条件。递归函数的第一句必须是if (T NULL) return;而且必须是第一句。有人把它写在递归调用之后逻辑上就变成了先递归再判断直接无限递归直到栈溢出。第四步检查建树时的边界判断。用先序序列建树时必须约定一个空节点标记比如#或者 -1否则递归不知道哪里该停。如果输入里没有空标记程序会把后面所有数据都吃掉越界访问。第五步检查局部数组是否过大。非递归遍历里的TreeNode *stack[100]这种写法如果树的节点数超过 100就会栈溢出。这类数组开小了的 bug 特别隐蔽因为小数据测试完全正常一上大数据就崩。工程代码里应该改成动态分配或者用足够大的容量并加上边界检查。我把常见崩溃原因整理成一张表出问题时按表逐条对现象最可能的原因定位方法立即崩溃指针未初始化、malloc失败未检查用单节点数据测试打印每个指针值递归很深后崩溃递归无终止条件、树退化成链打印递归深度检查空节点判断小数据正常、大数据崩栈数组容量不够、深递归栈溢出加大容量或改非递归实现结果不对但不崩BST 插入没赋值回父节点、访问顺序写错中序遍历看输出是否有序释放时报错重复释放、释放了非堆内存检查每个free是否只执行一次5.2 销毁树为什么必须是后序遍历释放整棵树的内存顺序搞错会直接导致内存泄漏或者访问已释放内存。正确做法只有一个——后序void DestroyTree(TreeNode *T) { if (T NULL) return; DestroyTree(T-left); /* 先释放左子树 */ DestroyTree(T-right); /* 再释放右子树 */ free(T); /* 最后释放自己 */ T NULL; /* 只是形参置空调用方要用二级指针才能真正置空 */ }为什么不能用先序因为先序会先把根free掉然后你还想访问T-left那块内存已经还给系统了读到的可能是任意值行为完全不可预期。这就是典型的释放后使用有时候不崩有时候崩最难查。还有一点要点破函数末尾那句T NULL;只是把形参置空了调用方手里的指针依然指向已释放的内存也就是野指针。如果调用方之后还拿这个指针去用一样会出问题。想让调用方的指针也变成 NULL得传二级指针TreeNode **T或者定个规矩调用DestroyTree(root)之后立刻写root NULL;。我个人倾向前者虽然麻烦点但不容易忘。5.3 从输入序列建树三种常见场景场景一扩展先序序列建树。输入里用#表示空节点比如AB#D##C##递归读一个字符遇到#就返回 NULLTreeNode *CreateByPreOrder(char **str) { char ch **str; (*str); if (ch #) return NULL; TreeNode *node CreateNode(ch); node-left CreateByPreOrder(str); node-right CreateByPreOrder(str); return node; }这里用char **str是为了让游标在递归过程中持续前进。如果直接传char *str每次递归拿到的都是同一个位置就会无限建同一个节点。场景二先序 中序序列还原二叉树。这是经典考题先序的第一个元素一定是根拿这个根去中序里找位置中序左边就是左子树、右边是右子树两边的长度又反过来告诉你先序里哪一段属于左子树、哪一段属于右子树然后递归下去。核心代码TreeNode *BuildTree(char *pre, char *in, int len) { if (len 0) return NULL; char rootVal pre[0]; int pos 0; while (pos len in[pos] ! rootVal) pos; /* 在中序里定位根 */ TreeNode *root CreateNode(rootVal); root-left BuildTree(pre 1, in, pos); root-right BuildTree(pre 1 pos, in pos 1, len - pos - 1); return root; }这段代码有一个必须注意的前提序列里不能有重复元素。如果有重复值中序定位根的位置就不唯一了还原出来的树也不唯一。后序 中序同理只是根在后序的最后一个位置。场景三层序序列建树。用队列实现先建根入队然后每出一个节点就从输入里读两个孩子可能是空标记挂上去并入队。这个写法在处理按层给出的数据时最自然。6. 手写练到什么程度算过关学数据结构最忌讳的一件事是看懂了三个字。看代码的时候觉得逻辑很顺一合上书自己写指针就不知道往哪挂了。我自己的判断标准是第一先序、中序、后序的递归和非递归六种写法能不能不看参考默写出来。默写不出来的话说明你记住的是代码的样子不是代码背后的栈的进出过程。第二BST 的插入和删除能不能一次写对。删除尤其关键二叉的删除情况能不能想到用后继替换数据再递归删除这条路直接反映你对 BST 有序性的理解深度。第三能不能在纸上画出任意序列对应的树并说清楚为什么先序加后序不能唯一确定一棵二叉树因为分不清左右子树谁先谁后而先序加中序可以。练题的时候别一上来就找难题。我给的顺序是求深度、数叶子、判断完全二叉树、中序非递归、BST 删除、按层打印、表达式树求值最后才是 AVL 旋转。这个顺序里的前五个是面试和课程设计的绝对高频区练到形成肌肉记忆为止。最后分享一个我调试树结构代码时用了几年的小技巧写一个PrintTree函数把树按缩进形式打印出来。左子树缩进多一点右子树缩进少一点每行打印缩进 节点值。这个函数不长但它能把抽象的内存结构变成你能用眼睛看的图形。插入删除之后调一次一眼就能看出指针是不是挂错了位置比盯着代码看半小时都管用。void PrintTree(TreeNode *T, int depth) { if (T NULL) return; PrintTree(T-right, depth 1); for (int i 0; i depth; i) printf( ); printf(%d\n, T-data); PrintTree(T-left, depth 1); }为什么会是这个奇怪的顺序因为它把树横过来了——右边在上面左边在下面看起来就像一棵自然生长的树根在左侧。这个可读性上的小设计比功能本身更值得花心思。