两种把二叉树装进程序里的办法：用指针连起来的链式存储，和利用下标关系的数组式存储。
回忆一下之前学过的两种基础结构：数组是一段连续的空间，靠下标直接定位；链表靠指针把节点一个个串起来，每个节点多存一个"指向下一个节点"的指针。但二叉树是"一对多"的结构——一个节点最多要连着两个子节点，普通数组和普通链表都没法直接照搬，需要专门设计存储方式。
常见的做法有两种：链式存储——每个节点额外存两个指针，分别指向左子节点和右子节点，思路上是链表的自然延伸；数组式存储——只利用下标之间的数学关系，不需要额外的指针空间，但只对"完全二叉树"（11.1 节讲过的性质）好用。下面分别来看。
链式存储是最通用、平时写代码最常见的写法：每个节点是一个结构体，除了存自己的值，再存两个指针 left、right，分别指向左子节点和右子节点——如果某个子节点不存在，对应指针就是 nullptr。
| 1 | struct TreeNode |
| 2 | { |
| 3 | int val; // 节点自己存的值 |
| 4 | TreeNode* left; // 指向左子节点，没有就是 nullptr |
| 5 | TreeNode* right; // 指向右子节点，没有就是 nullptr |
| 6 | TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} // 构造函数：新节点默认没有子节点 |
| 7 | }; |
手动搭建 11.1 节那棵示例树（根节点 1，左子节点 2、右子节点 3，2 的子节点是 4、5，3 的左子节点是 6），代码就是把每个指针手动接上：
| 1 | TreeNode* root = new TreeNode(1); // 先建根节点 |
| 2 | root->left = new TreeNode(2); // 1 的左子节点是 2 |
| 3 | root->right = new TreeNode(3); // 1 的右子节点是 3 |
| 4 | root->left->left = new TreeNode(4); // 2 的左子节点是 4 |
| 5 | root->left->right = new TreeNode(5); // 2 的右子节点是 5 |
| 6 | root->right->left = new TreeNode(6); // 3 的左子节点是 6，右子节点留空（nullptr） |
node->left == nullptr && node->right == nullptr，就说明它没有任何子节点，是叶子节点——这个判断在后面写遍历、写递归终止条件时会反复用到。如果一棵二叉树恰好是完全二叉树（11.1 节讲过：除最后一层外都填满，最后一层从左到右紧凑排列），就可以不用指针，只靠下标之间的数学关系把整棵树存进一个普通数组里——把树按"从上到下、同一层从左到右"的顺序编号，编号就是数组下标。
1,2,3,4,5,6，正好对应下标 0~5。橙色箭头是下标 0（节点 1）指向它两个子节点的下标；蓝色箭头是下标 1（节点 2）指向它两个子节点的下标——子节点的下标，永远等于"父节点下标 × 2"再加 1 或加 2。i，那么：2*i + 1 右子节点下标 = 2*i + 2 父节点下标 = (i - 1) / 2（整数除法）1，左子节点下标应该是 2*1+1=3（节点 4 ✓），右子节点下标是 2*1+2=4（节点 5 ✓）。
2*i+2，越往下跳得越远——中间全是没有节点、却必须留出来的空位。这样一棵树最坏情况下可能需要开到几十甚至上百的数组长度，才能存下 5 个节点。这也是为什么数组式存储只适合完全二叉树（比如以后要学的"堆"就是完全二叉树，非常适合用数组存），普通二叉树通常还是用链式存储。两种存储方式各有取舍，实际做题时按下面的表格来判断：
| 对比项 | 链式存储 | 数组式存储 |
|---|---|---|
| 适用范围 | 任意二叉树 | 只适合完全二叉树 |
| 额外空间 | 每个节点多存 2 个指针 | 不需要额外指针，但可能有空位浪费 |
| 找父/子节点 | 靠指针，O(1) | 靠下标计算，O(1)，甚至更快 |
| 动态增删节点 | 灵活，new/delete 即可 | 不方便，插入可能要整体挪动 |
| 常见场景 | 普通二叉树、二叉搜索树（11.4 节） | 堆、线段树这类结构天然完全的场景 |
把本节内容汇总成几条最容易踩坑的规则：
new TreeNode 出来的 left、right 是未初始化的"野指针"，直接判断 if (node->left == nullptr) 或访问它都可能出错。务必像上面代码那样写一个构造函数，把 left、right 显式设成 nullptr。左=2i+1，右=2i+2）。如果数组下标习惯从 1 开始存（下标 0 空着不用），公式会变成左=2i，右=2i+1，父=i/2——两套公式不要混用，混用会导致找错父子节点。