一、树与二叉树：从现实到代码的映射
说实话，我刚学数据结构那会儿，对树这种结构挺不以为然的。链表、数组多直观啊，树这玩意儿弯弯绕绕的，到底有什么用？直到我在一个项目里需要处理文件系统的目录结构——好家伙，这不就是一棵活生生的树吗？
树结构在嵌入式里其实很常见。比如你解析一个JSON配置文件，或者管理一个菜单系统，甚至做哈夫曼编码压缩数据，背后都是树。今天我们就从最基础的说起。
1.1 树的定义
树是一种非线性的数据结构。它由节点和边组成，有一个根节点，其他节点往下分叉。每个节点可以有多个子节点，但只有一个父节点（根节点除外）。
我习惯用家谱来理解树：
- 根节点：老祖宗，没有父节点
- 叶子节点：没有子节点的节点，相当于家族里的末代
- 子树：任何一个节点往下看，都是一棵小树
- 深度：从根到某个节点的层数
- 高度：从某个节点到最远叶子节点的距离
关键点：树是递归定义的。一棵树的每个子树本身也是一棵树。这个递归特性，直接决定了后面遍历算法的写法。
1.2 二叉树——最常用的树
二叉树就是每个节点最多有两个子节点，分别叫左孩子和右孩子。你想想看，这多好处理？两个分支，代码写起来特别顺手。
我在项目中用得最多的就是二叉树。为什么？因为它的结构简单，内存开销可控，而且很多复杂结构（比如堆、二叉搜索树、表达式树）都是基于它。
二叉树的五种基本形态：
- 空树
- 只有根节点
- 只有左子树
- 只有右子树
- 左右子树都有
嗯，这里要注意：空树也是树。很多递归算法的终止条件就是判断节点是否为NULL。
1.3 二叉树的遍历
遍历说白了就是按某种顺序把树里的每个节点都访问一遍。二叉树的遍历有四种经典方式，我一个个说。
1.3.1 前序遍历（Pre-order）
顺序：根 → 左 → 右
先访问当前节点，再递归遍历左子树，最后递归遍历右子树。
void preorder(TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->val); // 访问根
preorder(root->left); // 遍历左
preorder(root->right); // 遍历右
}我记得有一次调试一个菜单系统，需要把整个菜单树打印出来。前序遍历正好合适——先打印当前菜单项，再进入子菜单。这就是前序的典型应用。
1.3.2 中序遍历（In-order）
顺序：左 → 根 → 右
先遍历左子树，再访问根节点，最后遍历右子树。
void inorder(TreeNode* root) {
if (root == NULL) return;
inorder(root->left); // 遍历左
printf("%d ", root->val); // 访问根
inorder(root->right); // 遍历右
}中序遍历对二叉搜索树特别有用。你想想看，如果一棵二叉搜索树用中序遍历，得到的结果就是有序的。我在做数据排序时经常用这个特性。
1.3.3 后序遍历（Post-order）
顺序：左 → 右 → 根
先遍历左右子树，最后访问根节点。
void postorder(TreeNode* root) {
if (root == NULL) return;
postorder(root->left); // 遍历左
postorder(root->right); // 遍历右
printf("%d ", root->val); // 访问根
}后序遍历常用于释放树的内存。你总不能先把根节点释放了，再去找子节点吧？那会出大问题。我曾经就犯过这个错——先free了根节点，然后程序就崩了。正确的做法是先释放子节点，最后释放根节点，这就是后序遍历的思路。
1.3.4 层序遍历（Level-order）
层序遍历是按层级从上到下、从左到右依次访问。它需要借助队列来实现。
void levelorder(TreeNode* root) {
if (root == NULL) return;
Queue* q = createQueue();
enqueue(q, root);
while (!isEmpty(q)) {
TreeNode* node = dequeue(q);
printf("%d ", node->val);
if (node->left) enqueue(q, node->left);
if (node->right) enqueue(q, node->right);
}
}层序遍历在嵌入式里有个很实用的场景——打印树形结构。比如你要在串口上输出一个目录树，层序遍历配合缩进，效果特别好。
小技巧：如果你记不住三种深度优先遍历的顺序，记住一个口诀——「前根、中根、后根」，看根的位置在哪，就是哪种遍历。
1.4 二叉搜索树（BST）
二叉搜索树是二叉树的一种特殊形式。它的规则很简单：
- 左子树所有节点的值 小于 根节点的值
- 右子树所有节点的值 大于 根节点的值
- 左右子树也分别是二叉搜索树
说白了，BST就是一棵「有序」的二叉树。查找一个元素的时间复杂度是O(log n)，前提是树是平衡的。
BST的查找
TreeNode* searchBST(TreeNode* root, int target) {
if (root == NULL || root->val == target)
return root;
if (target < root->val)
return searchBST(root->left, target);
else
return searchBST(root->right, target);
}这个代码很简洁，对吧？每次比较都能排除一半的节点。我在做嵌入式配置表查找时，就经常用BST来加速。
BST的插入
TreeNode* insertBST(TreeNode* root, int val) {
if (root == NULL) {
return createNode(val);
}
if (val < root->val)
root->left = insertBST(root->left, val);
else if (val > root->val)
root->right = insertBST(root->right, val);
return root;
}注意：BST的插入和查找都依赖比较。如果插入的数据是递增或递减的，BST会退化成链表，时间复杂度变成O(n)。我曾经在一个项目中就踩过这个坑——数据是按时间顺序插入的，结果树变成了一根斜线，查找效率还不如数组。后来我改用平衡树（AVL或红黑树）才解决问题。
1.5 知识体系总览
下面这张图把本章的核心内容串起来了。你可以看到树的基本概念、二叉树的四种遍历方式，以及二叉搜索树的增删查操作。建议你对照着图，把代码自己敲一遍。
1.6 小结
树和二叉树是嵌入式开发中绕不开的数据结构。我个人觉得，理解树的关键在于两点：一是递归思想，二是遍历顺序。递归搞明白了，树的代码写起来就像呼吸一样自然。
二叉搜索树则是在二叉树的基础上加了有序性。它让查找变得高效，但也带来了平衡性的问题。这个我们后面会专门讲。
最后送你一句话：代码是写给人看的，顺便能在机器上跑。树的代码尤其如此——结构清晰、逻辑递归，读起来就是一种享受。
课后练习：
- 用非递归方式实现前序、中序、后序遍历（提示：用栈）
- 实现一个函数，判断一棵二叉树是否是二叉搜索树
- 写一个层序遍历，按层级输出节点，每层换行
公众号:蓝海资料掘金营，微信deep3321