结构体和二叉树，这两个词放在一起，几乎是每个学编程的人都要翻越的两座山。结构体是你自己定义的数据“盒子”，二叉树则是建立在盒子之上的经典结构；但很多人在学二叉树时，报错报得怀疑人生，根子往往不在“树”本身，而是结构体没玩明白。这篇文章我想把这两件事串起来讲：从结构体变量的定义、初始化，到二叉树节点的设计、遍历、深度计算、搜索树，再到那些“为什么总是报运行时错误”的排查经验，最后聊一点线索二叉树和结构体封装的扩展玩法。不管你是刚学C语言、正在和指针搏斗，还是为了准备面试想系统过一遍二叉树，这篇都能当一份实战笔记来用。
1. 结构体：二叉树的地基，也是初学者的第一道坎
1.1 结构体变量的定义：类型和变量别搞混
很多人第一次接触结构体，书上是这么写的：
struct Student { char name[64]; int age; double score; };然后后面紧跟一句：struct Student stu;。不少人在这一步就懵了：我明明已经定义了一个Student，为什么用的时候还要在前面加struct？
这里的关键是理解“你定义的是一个_类型_，而不是一个_变量_”。struct Student相当于造了一个新类型，和int、double平起平坐。所以定义变量时写struct Student stu;，逻辑上和int a;是一样的。C语言里这个“struct关键字”还不能省，除非用typedef给它起个短名：
typedef struct Student { char name[64]; int age; double score; } Student;有了这个typedef，后面写Student stu;就顺眼多了。我见过有人把typedef struct的语法拆开来看，觉得是个黑魔法，其实它就是把“struct Student的声明”和“起别名”合并成一步。它不影响内存布局，只是让你少敲几个字符，顺便让代码更像“面向对象”的样子。
到了二叉树这个场景，节点类型十有八九长这样：
typedef struct BiTNode { int data; struct BiTNode *left; struct BiTNode *right; } BiTNode, *BiTree;注意这里面有个看似“循环”的操作：结构体里面又用到了struct BiTNode本身。这在C语言中是合法的，因为left和right是指针，指针变量里存的是一个地址，地址的大小是固定的（64位机器上就是8字节），编译器不需要知道“完整的节点长什么样”就能算出指针字段的大小。如果结构体里直接嵌一个BiTNode的实例，那才是不允许的，那就是无限嵌套、无法计算大小了。
1.2 结构体初始化：三个常用姿势与坑
结构体变量如果定义在函数内部，不初始化是真的会“踩雷”。局部变量在栈上，里面存放的是随机的旧数据，如果你的结构体里有指针成员，那个指针可能指向任何地方。所以初始化从来不是“可选项”，而是“必做题”。
第一种姿势，最省事：{0}。
BiTNode node = {0};这个写法把所有字节都清零，指针变成NULL，数字变成0。C语言里这种“通用清零”特别实用，尤其适合在调试阶段避免野指针。
第二种姿势，C99标准支持的指定初始化，虽然不常用，但维护大结构体时很爽：
struct Student stu = { .name = "Tom", .age = 18, .score = 90.5 };因为不用记着成员的顺序，以后在结构体中间插入一个新字段，初始化代码也不会错位。不过一般教材里不怎么讲这个，工地上老代码也少用，但我觉得值得知道。
第三种姿势，是用memset清零。早期教科书经常写memset(&node, 0, sizeof(node))，在C里确实可以。需要提醒的是：在C++里，如果你的结构体里有std::string、std::vector这种非平凡类型，memset会把对象内部状态完全破坏，导致崩溃。所以“g++下同样代码会崩”不一定是代码错了，而是初始化姿势选错了。C语言场景下问题不大，但养成按字段手动初始化的习惯，长远看更安全。
1.3 文本读写结构体：fscanf里的经典翻车点
热词里有一条“fscanf结构体”，这确实是文件操作里和结构体关系最密切的坑。很多初学者以为可以像fread那样把文件内容一次性塞进结构体，于是写出这种代码：
Student stu; FILE *fp = fopen("student.txt", "r"); fscanf(fp, "%s %d %lf", stu.name, &stu.age, &stu.score);这个例子本身没问题，但有几个点必须说透。
第一，stu.name是数组名，名字本身就表示数组首地址，所以不能再加&。第二，stu.age和stu.score是普通变量，必须写&stu.age、&stu.score。我见过太多人统一加&或者统一不加，然后读出一堆乱码。第三，%s有一个溢出风险，如果文件里的名字超出name的长度，会直接写穿栈。安全写法是在格式串里限制宽度：%63s。
还有一个更隐蔽的问题：fscanf只能处理文本格式，它靠格式串把字符转成对应类型。你不能指着整个结构体说“给我读”，因为结构体在内存里的布局有对齐填充，文本文件里没有这些概念。反过来，用fread读二进制文件时，结构体内部的字节对齐又会导致文件里记录的长度和实际sizeof(Student)对不上。如果非要跨平台存二进制结构体，就要考虑#pragma pack(1)这种“压缩对齐”的手段。实操中我建议：文本文件用fscanf/fprintf按字段处理，别贪快直接fread整个结构体。
2. 写二叉树之前，先把节点这个积木设计好
2.1 节点定义：左右孩子指针方案
二叉树本质上是一棵有“两个孩子”的树。每个节点除了保存自己的数据，还需要知道左孩子和右孩子在哪里，于是就有了最经典的结构体：
typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;看到这段代码，有人会问：为什么不用两个普通的int来存孩子编号？如果你把树存在一个数组里，当然可以用数组下标来表示左孩子是谁、右孩子是谁：
int tree[MAXN]; int leftChild[MAXN]; int rightChild[MAXN];这种方式叫“结构数组法”或“静态二叉树”，在算法竞赛里很常用，尤其存完全二叉树时特别舒服：数组下标i的左孩子就是2*i+1，右孩子是2*i+2。它的优点是内存连续、访问快、不用处理指针，缺点是一棵稀疏的树会浪费大量数组空间。
而用结构体指针方案，孩子节点在堆上独立分配，树长什么样完全由指针来组织。这种方式更贴近“真正的树”，也是绝大多数教材、面试题和工程代码用的方案。它最大的好处是“用一个指针变量就能挂起一整棵子树”，比如递归参数直接传root->left，修改和遍历都极其自然。
两种方案没有绝对对错，我用过的一个铁律是：如果是写完整程序、要在不同函数之间传递复杂树结构，用指针结构体；如果只是刷题、已知最大规模、写堆或完全二叉树，用数组下标。
2.2 结构体指针与递归类型的本质
“结构体里面包含指向自身类型的指针”，这个设计在第一次见到时容易让人起鸡皮疙瘩。你可能会想：这不是递归定义吗？它怎么能编译过？
关键在于C语言编译器的处理顺序：当你在结构体内部写struct TreeNode *left时，编译器只需要为left分配一个指针变量。指针本质就是“内存地址的编号”，无论它指向的类型是什么，地址所占的字节数都是固定的。在你所在的机器上，sizeof(struct TreeNode *)是8字节还是4字节，取决于操作系统位数，但这个大小和TreeNode的完整定义无关。所以编译器在“还没完全看到TreeNode全貌”的情况下，就已经有能力为指针成员分配空间了。
这个特性是整个链式数据结构的基石，不光是二叉树，链表也是同样的道理。只要结构体里保存的是“指向自身类型的指针”，它就能表示任意长的链条或树形连接。我经常用一句话给朋友类比：“你是人，你口袋里的笔记本上写着别人的电话号码，电话号背后又是另一个人的信息，但你不用把所有人都装进口袋，存下他们的号码就够了。”指针就是那个电话号码。
2.3 另一条路：用数组存“树”
虽然指针方案是主流，但我想专门说一说数组方案，因为它在很多地方比指针方案更“稳”。
比如堆排序用的完全二叉树，用数组存的时候，节点的父子关系天然由下标决定：
// 根节点下标为0 int left = parent * 2 + 1; int right = parent * 2 + 2; int parent = (child - 1) / 2;这种写法不需要任何指针，也永远不会出现空指针解引用的问题。搜索二叉树如果用数组方式实现，需要为每个节点额外标记左右孩子是否存在，否则无法区分“值为0”和“空位”。我在竞赛里见过有人用：
int val[MAXN]; int lc[MAXN], rc[MAXN];每次新建节点：
int newNode(int v) { val[++tot] = v; lc[tot] = rc[tot] = 0; return tot; }这里0代表空节点，是不是有点像用数组下标代替指针？确实，它和指针方案在逻辑上是同构的。区别只在于：数组方案里“指针”是下标，天然自带容错；指针方案里“指针”是地址，野指针会让你直接崩溃。
所以我的建议是：如果你一开始用指针写二叉树总出运行时错误，先试着用数组方案把逻辑理通。逻辑通了，再换回指针方案，你会更清楚指针到底在干什么。
3. 二叉树核心玩法：遍历、深度与搜索树
3.1 前中后序：记住递归三句话
二叉树的递归遍历是最基础、也是面试最爱考的动作。其实代码就那么三句话，关键是搞清楚顺序。
前序（先根）：先访问根，再访问左子树，最后访问右子树。
void preorder(TreeNode *root) { if (root == NULL) return; printf("%d ", root->val); // 访问根 preorder(root->left); // 左 preorder(root->right); // 右 }中序：先左，再根，最后右。
void inorder(TreeNode *root) { if (root == NULL) return; inorder(root->left); printf("%d ", root->val); inorder(root->right); }后序：先左，再右，最后根。
void postorder(TreeNode *root) { if (root == NULL) return; postorder(root->left); postorder(root->right); printf("%d ", root->val); }我不用“递归三行代码”来记忆，而是记“访问根的位置”：根在左右子树之间访问就是中序，根在最前面就是前序，根在最后面就是后序。这个标准特别好用，做题时不用去背。
那这三种遍历各自有什么用？前序序列适合用来“重建树”，因为根最先出现；中序遍历二叉搜索树的结果是升序序列，这是判断一棵树是不是搜索树的常用手段；后序遍历因为“先搞定孩子再处理根”，天然适合写释放内存：先释放子节点，再释放根节点。
3.2 层序遍历：队列的典型应用
层序遍历就是一层一层从上往下扫。它没法用简单递归天然表达，因为你要保证“先处理第一层所有节点，再处理第二层”。想实现这个顺序，就用队列：
#include <stdio.h> #include <stdlib.h> void levelOrder(TreeNode *root) { if (root == NULL) return; TreeNode *queue[10000]; int head = 0, tail = 0; queue[tail++] = root; while (head < tail) { TreeNode *cur = queue[head++]; printf("%d ", cur->val); if (cur->left) queue[tail++] = cur->left; if (cur->right) queue[tail++] = cur->right; } }队列操作的灵魂是“队头出队、队尾入队”。每次从队列里弹出一个节点，就把它的两个孩子放进队尾。因为队列是先进先出，所以同一层的节点一定比下一层节点更早被弹出，这样天然形成层序。
这里有个细节：上面用“数组模拟队列”代替了链表队列，在刷题场景下特别常见，因为不用自己写malloc/free，也不会因为动态分配导致麻烦。真正写工程时，如果队列长度不确定，该用std::queue或链表队列就用。
3.3 二叉树深度：最大最小深度不一样的坑
最大深度应该人人都写过，递归解法简洁得像是送分题：
int maxDepth(TreeNode *root) { if (root == NULL) return 0; int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; }这里有一个值得解释的“为什么”：空树深度是0，某个节点自己的深度，等于它两颗子树深度的较大值再加1。加上这个1，是加上当前节点这一层。递归的返回值在每一层都带着“子树的信息”向上传递，最终在根节点拿到整棵树的高度。
最小深度的坑就比较多了。最经典的错误是：直接照抄最大深度，把max换成min：
int minDepth(TreeNode *root) { if (root == NULL) return 0; return (minDepth(root->left) < minDepth(root->right) ? minDepth(root->left) : minDepth(root->right)) + 1; }这个写法在“一个节点只有单边子树”时会出错。比如一棵树根节点只有右子树，真实的最小深度应该是2（根加右孩子），可上面代码会拿左子树的深度0去和右子树的深度比，算出来1。原因在于：空子树不应该被当成“深度0的候选路径”，因为图里压根没有一个节点在你认为的地方。正确写法：
int minDepth(TreeNode *root) { if (root == NULL) return 0; if (root->left == NULL) return minDepth(root->right) + 1; if (root->right == NULL) return minDepth(root->left) + 1; int l = minDepth(root->left); int r = minDepth(root->right); return (l < r ? l : r) + 1; }先处理“左右孩子缺失”的特殊情况，再做常规递归。这个坑我在实际写算法题时踩过，后来养成了一个习惯：涉及二叉树递归时，边界条件先写全，不要只盯着空节点一个边界。
3.4 搜索二叉树：让查找变快的结构
搜索二叉树，也叫二叉排序树、二叉搜索树，英文缩写BST，是二叉树里最有实际应用价值的一类。它的定义很简单：对于每个节点，左子树里所有值都小于它，右子树里所有值都大于它，且左右子树也都是搜索二叉树。
因为满足这个性质，查找一个值就能利用“比大小”跳过半边子树，不需要遍历所有节点。查找代码可以写成迭代：
TreeNode *searchBST(TreeNode *root, int target) { while (root != NULL && root->val != target) { if (target < root->val) { root = root->left; } else { root = root->right; } } return root; }插入也很有意思。递归插入时，很多人第一次会写错“根指针怎么更新”，因为修改链表的时候只要处理一个next，而修改树时可能要处理左右两边。我推荐一个不容易出错的写法：递归函数返回“插入完成后这棵子树的根”，然后让父节点接收返回值：
TreeNode *insertBST(TreeNode *root, int key) { if (root == NULL) { TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode)); node->val = key; node->left = node->right = NULL; return node; } if (key < root->val) { root->left = insertBST(root->left, key); } else if (key > root->val) { root->right = insertBST(root->right, key); } return root; }这么写的好处是，你不需要去考虑“父节点怎么改自己的指针”，递归函数自己把结果带回来了。删除节点比插入复杂，分三种情况：没有孩子就删；只有一个孩子就让孩子顶上来；有两个孩子就找右子树里最小的节点（或者左子树里最大的节点）替换，然后删除那个被替换的节点。这部分建议画图理解，别死记代码。
搜索树还有个特别实用的应用：中序遍历就是从小到大输出。想验证一棵树是不是合法的BST，把中序遍历的结果存下来，检查是否严格递增即可。也可以用“递归带上下界”的方式，遍历时传min和max，保证每个节点都落在合法区间。
4. 为什么二叉树程序总是报运行时错误：排错实录
4.1 三大经典运行时错误
热词里有“写二叉树程序时为什么总是报运行时错误”，这几乎是我见过最多人问的问题。二叉树程序报错，通常是这三种情况。
第一种是空指针解引用。现象是程序跑着跑着就“Segmentation fault”。原因往往是：你创建了节点，但结构体里的left和right没有初始化，它们是不确定值，然后你去用root->left->val，自然就炸了。
第二种是忘了分配内存。很多初学者会写出下面这种代码：
TreeNode *node; node->val = 5;node只是个指针变量，它没有指向任何有效内存。给不存在的内存写值，崩溃是必然的。正确做法是：
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode)); if (node == NULL) { // 处理分配失败 } node->val = 5; node->left = node->right = NULL;第三种是递归边界缺失，导致无限递归。比如求深度时，如果只写了if (root == NULL) return 1;，那空树的深度也会被当成1，更麻烦的是某些情况下递归没法收敛，栈越用越深，最终栈溢出，窗口弹出访问冲突。
我在排查时发现一个特别隐蔽的变体：递归遍历时，某个节点的指针被前面的代码改成野值。比如你在插入BST时，如果插入函数里malloc之后忘了把左右孩子初始化，再往下递归就会出问题。
4.2 排查套路：从gdb到画递归栈
遇到二叉树崩溃，别急着改代码。我自己的排查顺序是这样的。
第一步，先缩小范围。用最简单的小数据，比如一棵只有三个节点的树，如果一个节点的树都能让程序崩，问题基本出现在“创建/初始化”而不是“遍历”。如果小数据没问题、大数据崩，优先考虑是不是递归深度太大导致栈溢出。
第二步，加打印或者用调试器。打印很容易：“在每个递归函数入口打印当前节点值和地址，再看最后打印到哪一行消失”。消失前最后一个被打印的节点，往往就是出问题的位置。用gdb则更直接，崩掉之后输入bt查看调用栈，你能看到是从哪一行掉进去的：
gdb ./a.out run bt调用栈会显示一串递归帧，比如preorder -> preorder -> preorder ...，最后那一帧里的代码行号，就是你崩溃的位置。如果你看到连续几千行相同函数，基本可以确定是递归边界或指针问题。
第三步，检查初始化。这个习惯我强调多少遍都不为过：所有新malloc出来的节点，立刻初始化指针成员为NULL。我甚至会在调试阶段用memset(node, 0, sizeof(TreeNode))，先把所有成员清零，再赋数据值。
第四步，画递归栈。面对复杂递归，别只在脑子里演，拿纸画一棵小树，把每一次递归调用当成一笔，看看哪个分支是无限循环的。很多递归问题画一遍就通了。
内存泄漏也是一个经典问题。C语言里用完树要释放，释放必须用后序遍历：
void freeTree(TreeNode *root) { if (root == NULL) return; freeTree(root->left); freeTree(root->right); free(root); }这样保证“孩子先被释放，再释放自己”。如果你用前序释放，还没释放左子树就把根节点free了，后面访问root->left必然崩。检查内存泄漏可以用valgrind --leak-check=full ./a.out，看到“definitely lost”就是有节点没释放。
5. 进阶：线索二叉树与结构体设计的更多玩法
5.1 线索二叉树：利用空指针加速遍历
二叉树结构体里每个节点有两个指针，但叶子节点的左右指针通常是空的。明明是空闲的8字节，却什么都没干，线索二叉树就是打这个空指针的主意：用这些空指针，指向“遍历时的前驱或后继节点”，这样就省掉了一部分递归或栈的开销。
线索二叉树的结构体需要加两个标志：
typedef struct ThreadNode { int data; struct ThreadNode *left; struct ThreadNode *right; int ltag; int rtag; } ThreadNode;规则是：如果ltag == 0，left仍然指向左孩子；如果ltag == 1，left就指向前序/中序/后序遍历下的前驱节点。右指针同理，rtag == 1时right指向后继。
中序线索化是考试和面试最常讲的，因为它能把中序遍历变成“线性推进”。这种改造不是必须的，但它让人更理解指针的复用：一个指针字段，既可以当连接线，又可以当信息存储。这和结构体里放多个语义不同的字段是同一个思路。
现代工程里更常用的其实是Morris遍历，它不修改树的结构，而是把叶子节点的空间拿来临时记录后继，遍历完再还原指针。它的代价是不再“纯粹”，算法复杂度虽然为O(n)，但要理解的细节更多。我建议先看懂线索二叉树的逻辑，再去看Morris遍历，会顺畅很多。
5.2 结构体封装与链表语法的延伸
热词里还出现了“c++结构体链表基本语法”，这里值得多说一句。C++的struct和C语言的结构体不完全一样：在C++里，struct本质上就是一个所有成员默认公开的“类”，可以有构造函数、成员函数。也就是说，你完全可以在结构体里写一个初始化函数：
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };这么一来，创建新节点就变成了一行：
TreeNode *node = new TreeNode(5);new替你做了三件事：分配内存、调用构造函数、初始化指针。相比纯C的方案：
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode)); node->val = 5; node->left = NULL; node->right = NULL;显然C++的写法更省心。C语言虽然也能通过封装createNode函数达到类似效果：
TreeNode *createNode(int val) { TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode)); if (node != NULL) { node->val = val; node->left = NULL; node->right = NULL; } return node; }这个函数的核心价值在于：所有节点创建的初始化逻辑都被集中在一处，不会每次在代码里漏掉某个字段。
至于链表，它的结构体和二叉树几乎长得一样，只是把left/right换成了next：
typedef struct ListNode { int val; struct ListNode *next; } ListNode;理解了二叉树节点，链表就是它的特例。反过来，掌握了链表的next指针操作，再学二叉树的left/right就会平滑许多。我觉得这两者的关系是：链表是“只有一条路的树”，二叉树是“有两条路的链表”。如果链表你还不熟，先别急着啃二叉树，把next指针的“指向”“移动”“插入”“删除”拆明白，再回来写树，手感会好很多。
最后再分享一个我做二叉树练习时的习惯：准备一个统一的辅助函数，专门负责打印节点信息；再做一个小工具函数，手动构造一个固定形状的树，比如“根-左-右”三节点和“根-左链”这种极端形状。调试时只用固定形状，排除随机数据干扰。等逻辑通了，再用随机插入生成大样本测试。这样一轮下来，结构体怎么初始化、指针怎么连、递归怎么走，都会清晰非常多。
