企业官网建设流程全解析

1. 树存储结构的核心难题：非线性关系如何用线性内存表达

1.1 从"树的定义"到"树的落地"，中间还隔着一个存储问题

很多人在初学数据结构时，对树的理解停留在递归定义上——树是 n 个节点的有限集合，有且仅有一个根节点，其余节点被分成 m 个互不相交的子树。这个概念本身不难，难的是当你真正要动手把一棵树存进计算机时，问题立刻变得具体起来：节点之间的父子关系到底用什么方式保存？为什么不能像数组、链表那样直接了当地存取？

先说线性表。数组也好，链表也罢，线性结构的本质是每个元素都只有唯一的前驱和唯一的后继。在内存里，我要么用连续下标表达这种顺序，要么用指针把前后两个节点串起来。因为关系是"一对一"的，存储代价和查询路径都非常明确。

但树不一样。树是"一对多"的结构：一个父节点可能带三个孩子，另一个可能带十个孩子，也可能一个孩子都没有（叶子节点）。这种不确定的分支数量，决定了我们不能简单地给每个节点预留固定数量的指针，也不能指望用一串线性下标就完整表达出层次关系。

所以，树的存储结构设计，本质上是在回答三个问题：

1. 节点本身的数据（data）放在哪里；
2. 父子关系用什么机制表示；
3. 当我们需要找某个节点的父节点、孩子节点、兄弟节点时，这个机制能做到多快。

有意思的是，经典教材里给出的三种标准存储方案——双亲表示法、孩子表示法、孩子兄弟表示法——并不是互相替代的关系，而是对应了三种不同的查询偏好。理解了这一点，你才能真正在项目里选对存储方式，而不是单纯为了应付考试背定义。

1.2 树的存储需求拆解：把"找爹""找孩子""找兄弟"当成三种业务诉求

既然树存储的核心是表达关系，那我们先把"关系"拆开看。站在某个节点 X 的角度，它关心的关系无非三类：往上走找父节点、往下走找孩子节点、平着走找兄弟节点。

实际操作中用哪种存储方案，往往取决于业务里哪种查询最常发生。

比如，你在做一个组织架构系统，员工向上汇报的链路过几天就要查一次，这时候"找爹快"就比"找孩子快"重要；如果你在做文件系统那样的目录树，用户基本都是从上往下展开目录，那"找孩子快"才是第一优先级；如果你要写一个通用的树形组件，希望既能遍历子树又能在某些场景把树当二叉树处理，那就需要一种更灵活的表达方式。

这三类需求分别催生了三种经典存储方法。我把它们的底层逻辑、代码实现和实际应用逐个拆开讲，最后做一个横向对比，并补充一些面试和考试里常见的推导结论。

2. 双亲表示法：用"记下手牌"的方式存储，找爹快但找孩子慢

2.1 双亲表示法的核心原理与数据结构定义

双亲表示法的思路非常直白：既然每个节点有且只有一个父节点（根节点没有），那我用一个顺序表（数组）存放所有节点，然后给每个节点增加一个 int 类型的 parent 字段，用来记录它的父节点在数组中的下标。根节点的 parent 置为 -1，表示它没有爸爸。

用 C 语言描述大概长这样：

#define MAX_TREE_SIZE 100 // 树中的每个节点 typedef struct { char data; // 节点的数据域，实际项目中可能是完整对象或记录 int parent; // 父节点在数组中的下标，根节点为 -1 } PTNode; // 整棵树 typedef struct { PTNode nodes[MAX_TREE_SIZE]; // 存放所有节点 int n; // 当前节点个数 } PTree;

这种结构说白了就是一个扩充了"父指针"的数组。每个节点不再孤立存在，而是通过 parent 字段和它的父节点建立了一条关联。

举一个最简单的例子。假设我们要存一棵这样的树：

A / | \ B C D / \ | E F G

用双亲表示法存到数组里，大概是这个效果：

下标: 0 1 2 3 4 5 6 data: A B C D E F G parent: -1 0 0 0 1 1 3

根节点 A 的下标是 0，它的 parent 是 -1；B、C、D 都在下标 1、2、3 的位置，它们的 parent 都指向 0，表示它们的爸爸是 A；E、F 的 parent 都是 1，指向 B；G 的 parent 是 3，指向 D。

这种存储方式的优点和缺点都非常鲜明。优点在于：找任何一个节点的父节点，时间是 O(1)，拿到下标直接查数组就行；缺点是：找某个节点的孩子节点，你得把整个数组从头到尾扫一遍，看看哪些节点的 parent 字段等于当前节点下标，时间复杂度是 O(n)。

所以我经常说，双亲表示法是一个"记手牌"式的结构——每个节点都牢牢记住自己的上一家是谁，但你要是想知道自己手下有哪几个小弟，就得翻遍全桌所有人的手牌挨个对。

2.2 双亲表示法的常用操作与适用场景

先看两个最基本的操作。

找父节点：

int FindParent(PTree *tree, int i) { if (i < 0 || i >= tree->n) return -1; // 下标越界检查 return tree->nodes[i].parent; // 直接返回 parent 值，时间复杂度 O(1) }

找孩子节点：

void PrintChildren(PTree *tree, int i) { for (int j = 0; j < tree->n; j++) { if (tree->nodes[j].parent == i) { printf("%c ", tree->nodes[j].data); } } printf("\n"); }

找孩子要遍历全数组，这是双亲表示法最大的性能瓶颈。如果你在业务中经常要做"展开某个节点下的所有子节点"这种操作，直接用它就不太合适。

但双亲表示法有个隐藏优势：空间利用率高、内存布局紧凑，而且因为它是纯顺序结构，不存在链式结构常见的指针存储开销和碎片问题。对于一棵固定不变、只做少量查询的树来说非常合适。

它的典型应用场景有两个：

第一，并查集家族结构。并查集的核心操作就是 find（找根）和 union（合并），只需要往上看父亲，根本不需要顾及孩子。很多实现甚至可以直接用数组 parent[] 表示森林，这和双亲表示法本质上是同一套思想。

第二，一些静态的家谱或汇报链查询。比如查某个职位的上级、查某条审批链路的上游节点，这种只需要不断往 parent 方向走的应用，用双亲表示法既简单又高效。

这里给一个特别建议：如果在实际项目中选用了双亲表示法，但偶尔也要查孩子，可以在节点结构里加一个 firstChild 字段，指向第一个孩子的位置，再把孩子节点通过额外的 child 链表串起来。这就变成了"双亲+孩子"的混合结构，能够在两个方向上都获得不错的查询性能，代价只是每个节点多花几个字节的存储空间。类似做法在很多商业系统的树形结构中都能看到，属于非常实用的改良技巧。

2.3 双亲表示法的隐患：节点删除和顺序漂移

使用双亲表示法时，有一个容易被忽略的坑——数组顺序漂移。

由于所有节点堆在一个连续数组里，一旦某个中间节点被删除，后续节点的下标就会整体前移，那些原本记录在 parent 字段里的下标全部要更新。如果树本身是静态的还好，一旦涉及频繁增删节点，双亲表示法就会变得非常难受，更新成本从单点操作变成全表维护。

我之前给一个做流程引擎的同事排查性能问题，发现他的流程节点树就是用双亲数组存的。每次删除一个流程节点，程序就遍历一遍全树修正 parent 下标，数据量小的时候看不出问题，节点一多延迟立刻飙升。

解决方案其实也简单：要么选择删除标记，被删除的节点不在物理上移除，只是在逻辑上标记为无效；要么干脆在频繁增删的场景换用链式结构。这里也提醒一句，做架构选型时，不仅要看查询场景，还要看数据是否经常发生变动，否则很容易掉进"静态结构动态使用"的坑里。

3. 孩子表示法：把"孩子清单"挂在节点身上，适合从上往下遍历

3.1 孩子表示法的设计思路与双结构组合

既然双亲表示法不适合找孩子，那反过来，把每个节点的孩子列表直接挂在它自己身上不就行了？这就是孩子表示法的核心思路。

具体实现上通常采用"顺序存储 + 链式存储"的混合结构：所有节点本体放在一个数组里，每个数组元素除了存节点数据，还挂一个单链表头指针，这个链表专门存储该节点的所有孩子节点的下标。

C 语言定义如下：

#define MAX_TREE_SIZE 100 // 孩子链表节点 typedef struct CNode { int child; // 孩子节点在 nodes 数组中的下标 struct CNode *next; // 指向下一个孩子节点 } CNode; // 树节点本体 typedef struct { char data; CNode *firstChild; // 指向该节点的孩子链表头 } CTBox; // 整棵树 typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n; // 节点总数 int root; // 根节点所在下标，方便外部直接定位根 } CTree;

还是用上面那棵树举例：

A / | \ B C D / \ | E F G

对应的孩子表示法结构大致是这样：

• nodes[0] 存 A，它的 firstChild 指向一个链表，链表里依次有 B、C、D 的下标 1、2、3；
• nodes[1] 存 B，它的 firstChild 指向一个链表，链表里是 E、F 的下标 4、5；
• nodes[2] 存 C，它是叶子节点，firstChild 为 NULL；
• nodes[3] 存 D，它的 firstChild 指向一个链表，链表里是 G 的下标 6。

这样的结构找工作孩子非常直接：从 firstChild 开始沿链表往下走即可，找 N 个孩子的时间复杂度 O(N)。但如果反过来，想找某个节点的父亲，就比较麻烦了，你得把所有节点的孩子链表全部扫一遍，才能确定谁的孩子列表里包含当前节点下标，时间复杂度是 O(n)。

3.2 孩子表示法的改进版本：带双亲的孩子链表

在实际工程里，纯孩子表示法的"找爹难"问题经常让人觉得鸡肋——项目里多少都有往上回查的需求。好在这个问题极度容易改进：在每个数组节点里再塞一个 parent 字段，不就有了吗？

改进后的结构类似于：

typedef struct { char data; int parent; // 指向父节点，便于向上查询 CNode *firstChild; // 孩子链表头 } CTBox;

这样就变成了"既知道爹在哪，也知道孩子在哪"的完整结构。代价是多一个 int 字段的空间（通常 4 字节），换来的是两个方向的 O(1) 和 O(degree) 查询能力，这个性价比很高。

实际上很多开源的目录树组件、菜单控件在用类似结构时，就是这么设计的。一个数组保存所有节点，节点里保存父节点下标，同时每个节点维护一个子节点列表。这样无论是从根往下遍历菜单层级，还是从任意子节点回查上级菜单，都能快速完成。

3.3 孩子表示法的应用：文件系统目录树的存储逻辑

孩子表示法最形象的例子是文件系统目录结构。

操作系统的目录树本质上是一棵多叉树：根目录下有多个子目录，每个子目录下又可能挂文件和其他子目录。当我们用资源管理器展开一个文件夹时，系统需要在极短时间内列出该文件夹下的所有直接子项；当我们访问某个深层文件时，系统也需要知道它的完整路径，即沿父目录从根一路查下来。

这个业务场景里，两种方向的查询都很频繁，所以真实文件系统的目录节点通常不是简单采用课本里的某一种基础表示法，而是使用"带双亲的孩子链表"作为核心，再配合哈希索引加速名字查找。

再从另一个角度看：孩子表示法中，每个节点的孩子链表长度正好等于该节点的度（孩子个数）。对于一棵度数分布非常不均匀的树，比如一个根节点有上千个直接孩子、大量叶子节点却没有任何孩子，用孩子链表并不会浪费太多空间——因为叶子节点的 firstChild 直接置空，不需要为空孩子能力单独分配存储。这也是它比"定长指针数组"更实用的原因之一。如果贪图下标寻址快，给每个节点都分配固定 MaxDegree 个孩子指针槽位，遇到稀疏树时浪费惊人的内存，我给初学者一个具体的例子：如果树的度为 10，而实际 80% 的节点是叶子，即使实际使用率只有 20% 左右的指针槽位，也会白白占用接近 80% 的空间。

3.4 孩子表示法的遍历算法与易错点

用孩子表示法做树的遍历，最自然的写法是递归。先访问根节点，再逐个访问它的孩子链表，对每个孩子下标递归处理。伪代码如下：

void TraverseByChildren(CTree *tree, int rootIndex) { if (rootIndex == -1) return; printf("%c ", tree->nodes[rootIndex].data); CNode *p = tree->nodes[rootIndex].firstChild; while (p != NULL) { TraverseByChildren(tree, p->child); p = p->next; } }

要注意的一个易错点是：孩子链表中存的是下标而非指针，所以在递归或循环访问时，永远要用下标去 nodes 数组里取节点数据，不要直接拿链表节点当树节点操作。很多初写者会犯搞混 CNode 和 CTBox 的错误，把 CNode.child 误当成一个指向子节点的指针来解引用，编译不会立刻报错，运行时就暴露了非法访问问题。

如果你要为树节点增加"当前节点的兄弟"信息，孩子表示法并不擅长直接表达兄弟关系。兄弟关系隐藏在父节点的孩子链表顺序里，想找某一对相邻兄弟需要先定位到父节点的孩子链表，再遍历链表找相邻位置。这个操作频率一旦高起来，就会暴露出孩子表示法的结构性不足，此时就要考虑下一种——孩子兄弟表示法。

4. 孩子兄弟表示法：把任意多叉树"压扁"成二叉树的万能方案

4.1 孩子兄弟表示法的定义与核心思想

孩子兄弟表示法确实值得单独一章来聊，因为它是三种方法中最灵活、最"通用"的一种。

它的设计非常巧妙：与其费劲去存储每个节点的所有孩子，不如换个思路——每个节点只保留两个指针，一个指向自己的第一个孩子（长子），另一个指向自己的下一个兄弟。别的孩子不直接挂在当前节点下，而是通过"长子"链条一层层访问。

用 C 语言定义：

typedef struct CSNode { char data; struct CSNode *firstChild; // 指向第一个孩子，相当于二叉树的左指针 struct CSNode *nextSibling; // 指向下一个兄弟，相当于二叉树的右指针 } CSNode, *CSTree;

看到这个结构你可能立刻会想到一种熟悉的数据结构——二叉树。没错，孩子兄弟表示法本质上就是把一棵任意多叉树"压扁"成一棵二叉树，遍历方式、递归写法都可以完全套用二叉树的经典算法。

刚才那棵树用孩子兄弟表示法画出来，结构上就变了一个形态。A 的 firstChild 指向 B，B 的 nextSibling 指向 C，C 的 nextSibling 指向 D；B 的 firstChild 指向 E，E 的 nextSibling 指向 F；D 的 firstChild 指向 G。在物理存储上，它不再是一棵多叉树的样子，而是一棵每个节点最多只有两个指针的二叉树形态。

那么问题来了：为什么要把树变形成二叉树？因为二叉树有一套非常成熟的算法体系——先序、中序、后序、层次遍历，求深度、求叶子数、线索化、平衡化——这些算法可以直接复用，不需要为多叉树单独开发一套。

4.2 为什么"左孩子右兄弟"能表示整棵树

很多初学朋友都会卡在一个问题上：原来一个节点可能有 5 个孩子，现在只给我两个指针，怎么可能装得下？

关键就在于"分步引用"。每个节点只负责记录两件事：我的长子是谁，我的下一个兄弟是谁。至于我的其他孩子，它们不需要直接挂在我这里，它们挂在我长子的"兄弟链"上。

类比一下就好理解了：你现在是班主任，手底下有 10 个学生。你不需要在花名册上把 10 个学生全部直接挂在自己名下，你只需要知道第一排第一个同学是谁，然后让这个同学告诉你他旁边的同学是谁，旁边那位再告诉你下一位是谁。从第一个同学出发，沿着"同桌链"一路问下去，10 个学生全都能找到。孩子兄弟表示法里的 nextSibling 链，干的就是这个"同桌链"的活儿。

所以在孩子兄弟表示法中：

• 一个节点的所有孩子，都从 firstChild 指针出发，沿着 nextSibling 链找到；
• 一个节点的兄弟关系，通过 nextSibling 链表达；
• 根节点比较特殊，它没有兄弟，所以根节点的 nextSibling 通常为空。

这种存储方式在表达普通树的同时，还顺便解决了"同一棵树不同观察视角"的问题：当你用二叉树的方式去遍历它时，实际上已经是在用二叉树统一的算法体系处理多叉树了。

4.3 基于孩子兄弟表示法的遍历与求深度算法

先看一个最典型的操作：计算树的高度。

用孩子兄弟表示法求树高，需要把它理解成二叉树的形态来计算。高度公式为：

int TreeHeight(CSTree root) { if (root == NULL) return 0; int childHeight = TreeHeight(root->firstChild); // 沿长子分支深入 int siblingHeight = TreeHeight(root->nextSibling); // 沿兄弟分支深入 // 树的高度由最长"孩子分支"决定，兄弟分支不计入当前树高 return (childHeight + 1 > siblingHeight) ? (childHeight + 1) : siblingHeight; }

这个递归逻辑有点反直觉，需要重点解释一下：左边 firstChild 分支表示进入子树内部，所以高度需要加 1；右边 nextSibling 分支表示同一层级的兄弟节点，它不增加当前节点所在树的高度，但它本身可能是一棵子树的根，所以也要递归计算。

再比如统计叶子节点数。在原树中，叶子节点就是没有孩子的节点；在孩子兄弟表示法里，等价于"firstChild 为空"的节点：

int CountLeaves(CSTree root) { if (root == NULL) return 0; if (root->firstChild == NULL) return 1 + CountLeaves(root->nextSibling); return CountLeaves(root->firstChild) + CountLeaves(root->nextSibling); }

我第一次学这部分的感受是：代码本身不难，难在想明白"为什么同样是两个指针，含义却和二叉树完全不同"。二叉树里两个指针都表示"下一代"（左孩子、右孩子），但孩子兄弟表示法里只有 firstChild 才表示真正的"下一代"，nextSibling 表示的是"平辈"。只要在画递归调用树的时候时不时提醒自己这一点，思路就不容易乱。

4.4 普通树、森林与二叉树的转换关系

孩子兄弟表示法不仅仅是存储方案，它还提供了普通树与二叉树之间互相转换的桥梁。

树转二叉树的规则很简单：在所有兄弟之间加一条水平连线（相当于建立 nextSibling 关系），只保留每个节点与其长子的连线（其他孩子连线断开），然后以根节点为轴旋转 45 度。得到的二叉树，左指针就是 firstChild，右指针就是 nextSibling。

森林转二叉树的规则稍有区别：先把森林里每棵树都转成二叉树，然后以第一棵树的根为整体根，把第二棵树的根当作第一棵树根的右兄弟连接，第三棵树的根接在第二棵树根的右侧，依次类推。最后得到的二叉树，根节点的右指针链上串着的，就是森林里的其他树根。

这套转换有什么用呢？最重要的价值是算法复用。比如一个 CSP（关键路径）、霍夫曼树之类的问题，本质是二叉树算法；而一个目录树、菜单树、解析树，本质是多叉树。有了转换规则，你可以把多叉树用孩子兄弟表示法存起来，再借用二叉树成熟的前中后序遍历、线索化、平衡化手段来处理它。

很多高级树形结构，比如字典树和部分 B 树的逻辑退化版本，也会借鉴"长子+兄弟"的思想来压缩存储空间，只不过换成了更细粒度的节点编码。理解孩子兄弟表示法，可以帮助你理解这一类压缩结构的来历。

4.5 孩子兄弟表示法的局限与应对方法

虽然孩子兄弟表示法灵活，但它也有自己的短板。

最典型的问题：查找父节点很麻烦。因为指针方向是单向的，只有"往下"和"往右"的链，没有"往上"的链。如果要找某个节点的父节点，从当前节点出发没法直接完成，只能从根节点开始重新遍历，在遍历过程中记录递归路径，才能反推出父节点是谁。

解决方式通常有三种：

第一种，额外维护一个哈希表，记录每个节点的父节点信息。空间换时间，查询 O(1) 内完成，适合只读稳定的树。

第二种，在每个节点里增加一个 parent 指针，让结构从"二叉链表"变为"三叉链表"。代价是多出额外空间，好处是向上、向下、横向三种查询都变得很好操作。

第三种，干脆把树的遍历结果缓存下来，每次需要找父节点时先做一次先序遍历并把每个节点的父节点写成数组，这适合某些需要频繁查找但树本身不大变动的场景，比如编译原理里语法分析树的多次检查。

我在实际工程里最常用的是"第三种+第一种"的组合：树规模本来就不大（几百个节点），先序遍历一次把父节点映射算出来，后续所有向上查找都直接查哈希表。这样代码简单，也不需要对节点结构做大改动。

5. 三种表示法的横向对比：查询、遍历、空间与业务场景的选择依据

5.1 核心能力对照表

到底选哪一种，不能靠背，得看业务。我整理了三种表示法的横向对比，尽量覆盖实际选型时最关心的一组维度：

单独看一个维度没有意义，关键是组合起来看。比如：你的树是一次建好、后面基本只查"父节点"的树，双亲表示法就是最优解；你的树需要频繁展开子节点、遍历子树内容，孩子表示法更合适；你的树结构复杂多变，又要做各种遍历和算法操作，孩子兄弟表示法基本不会出错。

5.2 从业务场景反推选型

我这里总结几类典型的业务场景，方便各位直接对照参考：

静态权限树 / 审批链。每个节点只需要记录上级是谁，链路往上回查频次很高，孩子查询频率很低。这种场景选双亲表示法最省内存、代码最简单。

动态菜单树 / 目录树。用户经常要展开某一层看子节点，也偶尔需要从子菜单回跳上级菜单。这种推荐"带双亲的孩子表示法"，既有孩子链表又能向上回查。

通用树形业务组件 / 任意多叉树处理。比如后台管理系统里的树形数据控件、流程引擎的流程树展示，这种组件往往既要遍历树、又要转换数据格式、还可能要做搜索过滤。这种场景首选孩子兄弟表示法，因为它可以复用二叉树的所有递归和遍历算法，后续如果要加线索化、平衡化也有现成经验。

并查集 / 连通分量判断。这个本质上就是"一维父亲树"，用双亲表示法的退化变形——单纯一个 parent 数组——就足够了。不要为了用高级结构而强行引入链式存储。

5.3 空间复杂度的一个具体计算实例

我经常在带新人时做这样一个计算练习。假设一棵树有 n 个节点，我们要比较三种表示法的内存开销（暂不考虑数据域本身）。

• 双亲表示法：每个节点存一个 int 下标，总开销 n × 4 字节；
• 孩子表示法：每个节点一个孩子链表头指针 4 字节，每条孩子链上的链表节点存储孩子下标 + 指针，大约 8 字节，树共有 n-1 条边（每个非根节点都有一条边从父指向子），所以孩子链表节点总数也是 n-1，总开销大概是 n × 4 + (n-1) × 8；
• 孩子兄弟表示法：每个节点两个指针 8 字节，总开销 n × 8。

从这个计算里可以看出：双亲表示法在纯空间上最省；孩子表示法因为多了一层链表节点指针开销，通常最大；孩子兄弟表示法居中。但如果把"找兄弟"的便捷性和算法复用性折算进来，孩子兄弟表示法的实际综合成本并不高。

这其实是一个很好的思维训练：数据结构不是越复杂越好，而是越匹配需求越好。很多团队做技术方案评估时只盯着查询性能，忽略了数据是静态还是动态、是否需要频繁增删、是否依赖算法库，导致存储方案选型失误，后续重构成本很高。

6. 树存储结构中那些容易算错的高频问题：空指针数量与下标公式

6.1 孩子兄弟表示法的空指针数为什么是 n+1

面试里有一个高频推导题：一棵有 n 个节点的树，用孩子兄弟表示法存储，空指针域有多少个？

这个题目考察的其实是对树基本性质的理解。

树有 n 个节点，那么它的边的总数一定是 n-1——因为除了根节点以外，每个节点都恰好有一条从父节点指向自己的边。孩子兄弟表示法中，每条边对应一个非空指针域。每个节点有两个指针域（firstChild 和 nextSibling），所以总的指针域数量是 2n。

空指针域的数量 = 总指针域数量 - 非空指针域数量 = 2n - (n-1) = n + 1。

这个结论可以直接背，但如果能从头推导一遍，就不容易忘记，而且在面试时可以展示出你对"树的边数恒等于节点数减一"这个基础性质的掌握程度。

同类题目还有：用 n 个节点构造二叉树，空指针域有多少个？二叉树的每个节点有两个指针，n 个节点总共 2n 个指针，边数（即非空指针）是 n-1，所以空指针数也是 2n-(n-1)=n+1。这个结论跟"孩子兄弟表示法"得到的结果一致，因为它们本来就共享同一套"二叉链表"存储逻辑。

6.2 顺序存储的边界：完全二叉树谁能用，为什么一般树不能用

除了三种链式/半链式结构，树还有一种特殊存储叫顺序存储，但它只适用于完全二叉树或满二叉树。

完全二叉树的顺序存储规律非常优美：如果用数组从下标 0 开始存，那么对下标为 i 的节点，它的左孩子下标是 2i+1，右孩子下标是 2i+2，父节点下标是 (i-1)/2（整数除法）。

这个公式能成立的前提是：完全二叉树的每一层节点都按从左到右的顺序紧密排列，没有空位。正因为没有空洞，我们才能在数学上精确推算出任意节点的孩子和父节点位置。

但普通树或者一般的二叉树，如果也用数组顺序存储，问题就出现了。假设某个节点只有左孩子没有右孩子，如果强迫每个节点都占两个孩子的下标位置，数组里就会产生大量空洞；如果某个中间层节点缺失，后续所有下标推算都会错位。所以顺序存储只适合那些"结构紧密"的树。

这里顺带提一个常见错题：有人会把"完全二叉树"和"满二叉树"搞混。满二叉树是每一层的节点都填满；完全二叉树是除了最后一层外都填满，且最后一层的节点从左到右连续排列，中间不能有空格。两者的顺序存储下标公式是一样的，但满二叉树是一种特殊的完全二叉树。

6.3 已知双亲数组还原树结构时的易错操作

笔试或上机题中有一个很常见的题型：给出一棵树的 parent 数组，让你还原树结构或输出某种遍历序列。

这种题的核心操作是"按下标建指针连接"。假设输入是：

int parent[] = {-1, 0, 0, 0, 1, 1, 3};

先创建 n 个树节点，然后遍历 parent 数组：对于 i 从 1 到 n-1，将 nodes[i] 连接到 nodes[parent[i]] 的孩子链上。tricky 的地方在于，有些考题要求按孩子下标从小到大排列，有些要求按输入顺序排列。连接的时候要注意保持孩子在兄弟链中的相对顺序，否则最终遍历出来的序列会和题目预期不一致。

另一个易错点是：根节点不一定在下标 0。有些题目特意把根节点放在数组中间位置，parent 为 -1 的下标才是根。不要看到数组第一个元素就默认它是根。

还有一个进阶变体：给出树的双亲数组，要求判断某个节点是否为叶子节点。正确做法是检查该节点是否出现在其他节点的 parent 字段中。如果没有任何节点的 parent 等于该节点下标，那它就是叶子；否则它至少有一个孩子，就不是叶子。不少新手会直接看该节点自身的 parent 是否为 -1，这其实是在判断它是否为根节点，和是否为叶子完全是两回事。这两个判断千万不要混淆。

6.4 遍历序列与存储结构的关系

最后一个高频考点是：树的先序、后序、层次遍历结果，和转换成二叉树之后的遍历结果有什么关系？

用孩子兄弟表示法转换后，树转成二叉树有一个很重要的结论：

• 树的先序遍历 = 转换后二叉树的先序遍历；
• 树的后序遍历 = 转换后二叉树的中序遍历。

这个结论很多人只记忆结果，不理解原理。形象来看：树的先序遍历是先访问根，再逐个访问子树；转换后的二叉树先序遍历是先访问根，再访问左子树（长子）、再访问右子树（兄弟），本质上步骤一致。而树的后序遍历是先遍历子树再访问根，转换二叉树的中序遍历恰好是先遍历左子树（长子链）、再访问根、再遍历右子树（兄弟链），经过推算也能精确对应上。

这类结论在选择题里出现频率很高，做一次手工推演就能彻底记住。比如用上面那棵 A/B/C/D/E/F/G 的树，手工转成二叉树后，分别跑一次先序遍历和中序遍历，再把树的先序和后序遍历结果拿出来对比，一眼就能验证。

7. 从存储结构到代码落地：我自己的选型经验与建议

聊了这么多理论，最后分享一点实际开发中的体会。

我做了多年的后端开发和算法教学，见过的树形数据结构应用不计其数。我最大的感受是：选择树的存储结构，核心不是"哪个更高级"，而是"哪种查询最频繁"。

如果业务里 90% 的操作都是"给我某个节点的父节点"，那直接上双亲表示法，别犹豫。如果业务里 90% 的操作是"展开某节点看孩子"，那孩子表示法加上 parent 字段永远不会错。如果业务需要兼容多种树操作，或者你打算用二叉树的那套算法库来处理多叉树，那就选孩子兄弟表示法。

反过来说，我也见过不少"为了用高级结构而用高级结构"的例子：本来只是做一个两层静态菜单，非要引入复杂的二叉链表转换，结果代码繁琐不说，调试还费劲。数据结构的选型服务于业务，而不是业务去迁就结构，这个顺序不能反。

最后留一个实用的小技巧：每当你在代码里定义一种树的存储结构，我都会建议你顺手写一个PrintTree函数，打印出每个节点的下标、数据、父节点下标和孩子列表。这看起来有点多余，但真到了树结构复杂、递归层数深的时候，有一个可以直观打印内部状态的工具函数，排查问题的速度能提升数倍。很多线上诡异的树操作 bug，靠的往往不是高深的调试技巧，而是一张清晰打印出来的树形结构图。