1. 先别急着写代码把二叉树的基础概念盘清楚提起二叉树我印象特别深。当年学数据结构C语言版的时候前面顺序表、链表、栈、队列都还算能应付一到树这块班里瞬间倒了一大片。原因很简单——从树开始数据结构不再只是“线性”地往前推而是出现了分叉人的直觉一下子跟不上节奏了。但二叉树这个概念本身并不难难的是你脑子里能不能建立一个立体的结构图景。树结构在真实场景里太常见了。文件系统目录、编译器里的语法树、数据库索引的B树底层、路由表的查找全是树的影子。而二叉树是所有树结构里最简单也最关键的一种因为任意一棵多叉树都可以通过“左孩子右兄弟”的方式转化为二叉树来处理。也就是说你把二叉树搞明白了其他树结构很大程度上也能顺势打通。1.1 二叉树的定义和几个必须记住的术语官方定义是这么说的二叉树是n个节点的有限集合该集合要么为空集要么由一个根节点加上两棵互不相交的左子树和右子树组成。注意这个定义里有一个递归的味道左右子树本身也是二叉树。这个递归味道很重要因为后面你写遍历、求深度、求叶子数全部都在用递归而递归的出口就是“树为空”。然后是几个高频术语考试和面试都绕不开度degree一个节点拥有的子树个数。二叉树里节点的度只可能是0、1、2。叶子节点终端节点度为0的节点。分支节点内部节点度不为0的节点。孩子、双亲、兄弟、祖先、子孙这些按字面理解就行。层次Level根节点所在层次为1往下依次递增。深度Depth根节点到最远叶子节点的最大层次数也叫高度。这里要小心有些教材把空树的高度定义为0有的定义为-1面试前一定先跟考官对齐定义别在这个小坑上翻车。第i层上的最大节点数是2^(i-1)深度为k的二叉树最大节点数是2^k - 1这个公式是后面判断完全二叉树和平衡二叉树的基础。1.2 为什么要单独拎出满二叉树和完全二叉树满二叉树和完全二叉树这两个概念初学的时候特别容易被搞混。满二叉树是指深度为k且含有2^k - 1个节点的二叉树也就是说每一层都是满的节点一个不多一个不少。完全二叉树则宽松一些最后一层可以不填满但必须从左到右连续排列中间不能有空位同时上面所有层必须都是满的。我把这两个概念放在一起讲是因为它们在存储和性质上有本质区别。满二叉树是“形态最完美”的二叉树但实际应用中完全二叉树出场率更高——堆排序用的就是完全二叉树的概念顺序存储二叉树时也只有完全二叉树才能做到“不浪费数组空间”。而且完全二叉树的节点编号有一个非常有用的性质如果某个节点的编号是i那么它的左孩子编号是2i右孩子是2i1双亲是i/2取整。这个性质在顺序存储结构里是核心逻辑务必要记牢。2. 顺序存储还是链式存储这是一个值得先想清楚的问题很多初学者拿到二叉树第一反应就是把节点放进数组里。这个思路没问题顺序存储确实存在而且对于完全二叉树来说非常高效。但如果你拿它去存一棵普通的二叉树代价可能大得离谱。2.1 顺序存储只适合完全二叉树的“省事方案”顺序存储的思路很简单把二叉树从上到下、从左到右编号存入数组每个位置存一个节点。对完全二叉树来说数组下标和树节点的编号一一对应利用下标2i和2i1就能找到左右孩子空间利用率100%。但问题来了如果树不是完全二叉树呢为了维持下标关系中间空缺的位置也得占着那就得用特殊值比如0或-1填充。极端情况下一个深度为4但只有4个节点的树如果节点集中在右子树数组要开到15个位置大量空间白白浪费。我自己在大一的时候干过这种事用顺序表实现了一个左子树为空的二叉树跑了半天发现内存占用高得离谱这才老实换回链式存储。所以顺序存储的结论很简单完全二叉树或者接近完全二叉树的场景用数组很香但一般形态的二叉树链式存储才是正道。2.2 二叉链表最常用的二叉树存储结构链式存储二叉树的经典方案是“二叉链表”。每个节点除了保存自己的数据域data之外再挂两个指针域lchild和rchild分别指向左孩子和右孩子。没有孩子的位置置为NULL。用C语言定义大概是这样的typedef struct BiTNode { char data; // 数据域考试里一般用char struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;这个定义看着简单但有几个点要提醒你。第一结构体里递归引用了自己前面必须加struct关键字或者用typedef先起别名否则编译器不认识。第二如果你后续要做线索化处理还需要在结构体里加入ltag和rtag两个标志位这个到线索二叉树章节再展开初学阶段先把两个指针域的版本吃透。有的同学会问为什么不用三叉链表也就是再多加一个parent指针我的看法是初学阶段不要加因为很多操作的递归写法是基于二叉链表设计的提前加parent指针反而容易让你在递归回溯时“抄近路”绕过了本该练习的递归思维。等你真正做了AVL树或者需要自底向上查找的场景再考虑加parent指针不迟。2.3 手把手教你用递归创建一个二叉树创建二叉树看起来像是一个“构建”操作但实现方式却高度依赖遍历顺序。最常用的建树方式是“扩展二叉树”把空指针位置用特定符号经常用‘#’或空格显式表示出来然后按照某种遍历顺序输入节点序列。比如你要建下面这棵树A / \ B C / \ \ D E F对应的先序扩展序列是ABD##E##C#F##。其中#表示当前位置是空指针。有了这个序列建树的递归代码就非常好写void CreateBiTree(BiTree *T) { char ch; scanf( %c, ch); if (ch #) { *T NULL; } else { *T (BiTNode *)malloc(sizeof(BiTNode)); if (!*T) { exit(-1); } (*T)-data ch; CreateBiTree((*T)-lchild); // 先递归建左子树 CreateBiTree((*T)-rchild); // 再递归建右子树 } }这里必须强调两点。第一参数要用二级指针BiTree *T因为我们要修改指针本身的值让它指向新malloc出来的节点。只传一级指针的话函数内部对指针的修改不会影响函数外部这是个非常经典且隐蔽的错误。第二scanf时格式串里加一个空格是为了跳过输入缓冲区里的换行符不然读入的字符会错位。用C语言做过字符输入的都知道这个坑几乎人人踩过。3. 遍历二叉树的灵魂所在如果说二叉树是数据结构里的“一座山”那遍历就是翻山的唯一一条路。先序、中序、后序遍历不仅本身是考点几乎所有基于二叉树的算法求深度、求叶子数、判断相等、线索化、由序列还原树都得借助遍历来完成。3.1 先序、中序、后序的本质区别是什么很多人背口诀先序是“根左右”中序是“左根右”后序是“左右根”。我会背但一开始并不理解为什么会这样。这里的核心逻辑是所谓“先/中/后”指的是访问根节点的时机左子树和右子树的访问顺序永远是先左后右从不变。先序遍历访问根节点先序遍历左子树先序遍历右子树。中序遍历中序遍历左子树访问根节点中序遍历右子树。后序遍历后序遍历左子树后序遍历右子树访问根节点。拿上面那棵树做例子三种序列分别是先序ABDECF根A在前然后左子树BD E再右子树CF中序DBEA C F具体是DBEAFC后序DEBFCA根A跑到最后了我建议你不要背序列而是把递归过程在纸上画几遍从根节点出发沿着左子树一直往下走碰到空就回头然后走右子树。每一节点会被“经过”三次分别对应先序、中序、后序的访问时机。理解到这一层你就能解释一个很经典的现象先序序列的第一位一定是根节点后序序列的最后一位一定是根节点而中序序列靠根节点把左右子树区间一分为二。后文我会讲怎么用这个性质从先序中序反推整棵树。3.2 三种遍历的递归实现代码只有三行不同C语言的递归遍历代码框架几乎一模一样差别只在三条语句的顺序上。这是你学完数据结构后最早能背下来的一类代码但我希望你不仅会写还能讲清楚递归过程。void PreOrderTraverse(BiTree T) { if (T NULL) { return; } printf(%c , T-data); // 先序先访问根 PreOrderTraverse(T-lchild); // 然后左子树 PreOrderTraverse(T-rchild); // 最后右子树 } void InOrderTraverse(BiTree T) { if (T NULL) { return; } InOrderTraverse(T-lchild); // 先左子树 printf(%c , T-data); // 中序再访问根 InOrderTraverse(T-rchild); // 最后右子树 } void PostOrderTraverse(BiTree T) { if (T NULL) { return; } PostOrderTraverse(T-lchild); // 先左子树 PostOrderTraverse(T-rchild); // 然后右子树 printf(%c , T-data); // 后序最后访问根 }你发现没有递归终止条件都是T NULL时返回这正好对应了二叉树定义里的“空树”情况。可以说这个判断是整个递归机制的安全阀没有它递归会无限深入空指针导致程序崩溃。我学这块的时候有个很蠢但很有效的练习找一个深度为4的树把每层递归的调用过程写成缩进列表模拟每个函数调用的栈帧。结构体指针T在每一层递归中的值是什么、函数什么时候返回写一遍就通了。这个方法也推荐给你。3.3 面试高频变体已知先序和中序怎么还原整棵树我先直接给结论先序序列找根中序序列切分左右子树递归进行。这个逻辑也是每年考研和软考数据结构的常客一定要做到手推和代码都会。拿先序序列ABDECF和中序序列DBEAFC来演示。先序的第一个字符是A所以根是A。到中序序列里找到AA左边的DBE就是左子树的中序序列右边的FC就是右子树的中序序列。再看先序序列A后面跟着的是B、D、E对应左子树的先序所以左子树的先序是BDE右子树的先序是CF。接下来递归处理左子树中序是DBE先序是BDE先序第一位B是左子树的根在中序里B左边是D右边是E于是D和E分别是B的左、右孩子。右子树同理中序FC先序CFC是根F是左孩子。最终还原出来的树就是上面那棵。这个反推过程的代码实现核心是一个递归函数参数是两段序列的下标区间。这里有个细节先序序列的特性是“根一直在当前区间最前面”中序序列的特性是“根的位置把区间切成两半”。根据这两个特性不断缩小区间就能重建二叉树。BiTree buildTree(char *pre, char *in, int preL, int preR, int inL, int inR) { if (preL preR) { return NULL; } BiTree root (BiTNode *)malloc(sizeof(BiTNode)); root-data pre[preL]; int pos -1; for (int i inL; i inR; i) { if (in[i] pre[preL]) { pos i; break; } } int leftLen pos - inL; root-lchild buildTree(pre, in, preL 1, preL leftLen, inL, pos - 1); root-rchild buildTree(pre, in, preL leftLen 1, preR, pos 1, inR); return root; }有个容易迷糊的点是leftLen的计算左子树的长度等于根在中序中的位置减去中序区间左边界。这个长度用来切分先序序列确定左、右子树的先序区间。初学者经常把preL1之后的边界算错建议你手动代入一个例子跑一遍下标变化。理论上只知道先序和后序是无法唯一确定一棵二叉树的因为当某个节点只有一棵子树时先序和后序无法区分它是左孩子还是右孩子。这一点面试经常拿来考务必记住。4. 深度、叶子数、节点数三个朴素但必考的操作我刷题和做实验时发现很多同学能把遍历背得滚瓜烂熟但一让他写“求二叉树深度”就卡住了。其实递归框架一模一样区别只在于递归返回值的利用方式。4.1 二叉树深度最典型的递归返回值应用求深度的思路特别直观一棵树的深度等于左子树深度和右子树深度较大值再加1。空树的深度为0。这个描述本身就是一个递归定义翻译成代码几乎没有障碍。int TreeDepth(BiTree T) { if (T NULL) { return 0; } int leftDepth TreeDepth(T-lchild); int rightDepth TreeDepth(T-rchild); return leftDepth rightDepth ? leftDepth 1 : rightDepth 1; }这里有几个细节要注意。第一递归计算完左右子树深度后不能直接返回leftDepth或rightDepth必须加1因为还要把当前这一层算进去。第二用临时变量接收左右深度是良好习惯避免同一棵子树被递归两遍。比如写成return TreeDepth(T-lchild) TreeDepth(T-rchild) ? TreeDepth(T-lchild) 1 : TreeDepth(T-rchild) 1性能会打折因为子树的深度被重复计算了。我还见过另一种写法利用函数参数传递当前层数层数打擂台更新最大值。那种思路也很不错尤其在非递归遍历时求深度比较常用。两者本质相同都是遍历所有节点并记录最大层次。4.2 叶子节点数和节点总数在遍历过程中计数求节点总数和叶子数的逻辑完全建立在遍历之上。节点总数就是“每访问一个节点就加1”叶子数就是“访问到左右孩子都为空的节点时加1”。下面给出一个统一框架int NodeCount(BiTree T) { if (T NULL) { return 0; } return NodeCount(T-lchild) NodeCount(T-rchild) 1; } int LeafCount(BiTree T) { if (T NULL) { return 0; } if (T-lchild NULL T-rchild NULL) { return 1; } return LeafCount(T-lchild) LeafCount(T-rchild); }NodeCount的思路和求深度很相似总节点数等于左子树节点数加右子树节点数再加自己。LeafCount则加了一个“叶子判定”的终止条件如果没有左右孩子说明是叶子直接返回1。我之前辅导学弟学妹的时候发现他们经常在LeafCount里漏掉“空树返回0”这个条件。如果T是NULL还去访问T-lchild程序直接就段错误了。所以递归函数的第一步永远是先想清楚空情况的返回值。4.3 实验报告和考试里常见的综合题套路数据结构实验报告和期末考试里二叉树基础部分很少单独考一个操作通常是把建树、遍历、深度、叶子数结合起来形成一个“实验四件套”输入先序扩展序列输出先序、中序、后序三种遍历结果然后输出深度和叶子数。这套流程我在本科做过后来指导研究生做本科课程设计时也见过一模一样的题目可以说是经典中的经典。对这种综合题我的建议是先把代码模块化CreateBiTree负责建树三个遍历函数分别输出序列TreeDepth和LeafCount负责统计main函数里按顺序调用。每个函数只干一件事出错了也容易定位。有些同学喜欢把所有逻辑塞进一个函数里虽然也能跑通但调试的时候会让你痛不欲生。再提一句调试技巧建树之后先用printf把根节点打出来确认树建对了再跑遍历。因为遍历结果错很多时候不是遍历逻辑的问题而是建树阶段输入的#位置不对导致树本身就长歪了。我见过太多人一上来就埋头debug遍历代码最后发现是输入的时候少打了一个#白白浪费一个晚上。5. 新手最容易踩的坑从环境配置到空指针二叉树这章虽然概念不复杂但写代码时新手NG率极高。我总结几个自己以及周围人踩过最多的坑希望能帮你少走弯路。5.1 本地环境VSCode配置C/C运行环境的建议不少朋友是在课程要求下开始写C语言版的二叉树而本地编译环境经常是第一个拦路虎。如果你用VSCode需要装C/C扩展和Code Runner并且要确保编译器路径正确。Windows下建议安装MinGW-w64装完把bin目录加到系统PATH里然后在终端输入gcc -v验证一下能看到版本信息就说明环境通了。这里有一个常见报错运行时会提示“gcc不是内部或外部命令”。多半是PATH没配好或者MinGW安装不完整。我自己的处理办法是在VSCode的tasks.json里写死编译器的绝对路径这样即使PATH有变动CtrlShiftB编译也不受影响。注意MinGW目录不要放在带空格的路径下比如Program Files否则可能引发奇怪的路径解析问题放到C盘根目录或者某个纯英文路径下最省心。还有一个和C语言课上练习经常混淆的坑如果你使用的是C编译器去编译C代码malloc返回的void指针在某些严格模式下需要强制转换否则会报错。但C语言本身不要求强转。如果你不想折腾这些建工程时直接把文件后缀命名为.c并且确保tasks.json里的编译器是gcc而不是g这样最稳妥。5.2 段错误大概率是空指针或越界二叉树代码里段错误Segmentation fault可以说是标配报错我当年第一次跑建树代码就中招了。常见的原因有三个第一malloc后没有检查返回值就直接使用。内存分配失败会返回NULL这时候访问T-data就是非法访问。虽然大多数情况下内存不会不足但养成检查的习惯总没坏处。第二递归函数里少写了“空树返回”的判断。比如你在求深度的时候只判断了T-lchild是否为空但没先判断T本身是否为空那么当T是NULL时访问T-lchild就崩了。记住任何递归操作的第一步都应该是“如果T为空返回什么”。第三scanf的输入类型和变量不匹配。比如你定义了char ch但格式化字符串里写了%d这样读进来的数据是错的后续树的结构也就乱了访问时可能因为节点数据异常导致各种诡异问题。建议使用scanf( %c, ch)前面的空格专门用来吃掉空白字符。5.3 理解递归别只看代码手绘一棵树比盯屏幕更有用最后想多聊一点关于递归学习方法的事。很多初学者看递归代码大脑CPU直接过载因为代码只有几行但执行过程一层套一层根本想象不过来。我的建议是找一棵深度不超过4的树用纸笔画下每个递归函数调用的过程特别关注“函数什么时候从哪一层返回”和“返回值被谁接收”这两个问题。以中序序列为例你在纸上标出每个节点的访问时机就会惊喜地发现中序遍历的结果就是把二叉树“投影”到一条水平直线上从左到右排列的结果。这个直观印象建立起来之后后序、先序也就不再是死记硬背了。如果对递归实在不敏感可以先从非递归版本入手用栈模拟递归过程。虽然代码更长但执行流程更显式容易理解。等你用栈写出了中序遍历再把代码改回递归版会觉得递归“原来就这么回事”——这个方法我推荐给了不少人反馈都还不错。6. 二叉树的下一步线索化、AVL与非递归遍历的引子基础的二叉树操作到这里已经齐了但如果你的目标是考研、竞赛或者实际项目开发光有递归遍历是不够的。这里我简单说三个高频的拓展方向每个都足够再写一篇长文这里先给你一个整体认知。6.1 线索二叉树在一章后会怎么用到线索二叉树的产生是因为对一棵有n个节点的二叉链表n1个空指针域没有充分利用。线索化之后空指针被改造成指向某种遍历顺序下的前驱或后继这让遍历不再依赖递归和栈。核心是给每个节点加两个标志位ltag为0表示lchild指向左孩子ltag为1表示lchild指向前驱rtag同理。初学阶段你可能觉得线索化是“纯为了做题”但它在实际场景里非常有用尤其是需要频繁遍历的场景。比如文本编辑器的撤销历史或者某些游戏AI的决策树遍历线索化之后能省掉显式维护栈的开销。6.2 为什么别人总提AVL树热词里有“嵌入式 二叉树之avl树”说明不少嵌入式方向的从业者也要跟AVL打交道。AVL树是二叉排序树的一种自平衡版本它保证了每个节点的左右子树高度差不超过1。这个性质让查找操作的复杂度稳定在O(log n)不会像普通二叉排序树那样退化成链表。理解AVL树的关键在于掌握四种旋转LL、RR、LR、RL。这四种情况本质上是“最小不平衡子树的形态不同”旋转的目的就是恢复平衡同时保持二叉排序树的性质。我当时学AVL的一个窍门是不要在抽象层面想旋转而是把节点A、B、C三个具体的数值代进去跟着旋转步骤画一遍很快就找到感觉了。6.3 非递归遍历栈和队列的实战机会二叉树的非递归遍历本质上是用你自己的栈模拟系统调用栈。先说先序遍历的非递归写法从根出发不断向左走边走向访问边把右孩子压栈左路走到头后弹出栈顶元素再继续这个过程。中序遍历则是先一路向左压栈左路为空时弹出访问再转向右子树。我个人的顺序建议是先尝试用栈写中序遍历因为中序遍历的非递归逻辑最直观和递归版本的对应关系最清楚。写对了之后先序遍历只需要在中序遍历基础上调整访问时机。后序遍历最麻烦因为需要区分“从左子树返回”和“从右子树返回”很多写法要么增加一个lastVisited变量要么用两个栈来倒腾。非递归版本之后我会单独写一篇这里先埋个伏笔。经历这些学习过程我个人最大的感受是二叉树不像链表那样能靠纯粹的变量思考搞定它逼着你建立一种“递归视角”让函数自己调用自己去解决结构相同的子问题。等到你对递归熟练到像呼吸一样自然后面图、排序、分治算法、动态规划的学习都会省力很多。如果你现在还在为建树时的#号纠结、为递归栈帧想不通头疼这很正常——每一个学数据结构C语言版的人都是从这段路走过来的。找几道题在纸上多画几遍代码多敲几遍这个坎很快就能迈过去。