上一页我们把树画成了带箭头的图：圆圈是结点，线是父子关系。但内存里没有纸和笔，只有一格一格连续的单元。问题来了：怎么把这张图塞进这些格子里？

上一页我们把树搬进了内存，但每个结点该记些什么？想想公司的人事系统：员工表里有一栏「直属上司」，填的是上司的工号。树里每个结点只要记下父亲的位置，整棵树就稳了。

上排是原树，下排是内存中的数组：每格存 data 和 parent（父亲的下标），根记 -1。

在父亲表示法里，找父亲和找孩子是两件成本完全不同的事。

用 C 结构体数组落地父亲表示法：定义、初始化、找父结点一次看全。

核心只有一行字段 parent：存父亲下标。找父亲就是读数组元素的一个字段，O(1)；-1 兼作根的标记和越界哨兵。

父亲表示法倒着放：每人都记「我爹是谁」。但找孩子时只能全表扫一遍，很慢。换个方向想——让每个结点自己记住孩子，找孩子不就快了吗？这就是孩子表示法的出发点。

左边是存所有结点的顺序表，右边每个结点拖出一条单链表，专门串它的孩子。

两种表示法都能存树，但一个查父快、一个查子快——混淆点在于：到底快在哪一步、代价是什么。

刚才对比过：找父亲快靠 parent 列，找孩子快靠孩子链表，各赢一半。那能不能把两张表拼在一起？可以——给每个结点同时挂上父亲下标和第一条孩子边。

带孩子链表和 parent 域的结构定义，以及找父亲、找孩子两个操作的真实实现。

parent 域存下标实现 O(1) 找父亲；children 列表沿链表找孩子。add 时同时维护两处，双向信息各付一次代价。

前面父亲表示法好找爹却难找孩子，孩子表示法正好反过来。能不能只用一种固定结构，两个方向都够用？只需给每个结点记两件事：第一个孩子是谁，下一个兄弟是谁。

每个结点只有两个指针：fc 指向第一个孩子，nb 指向下一个兄弟。顺着箭头就能还原整棵树。

任意一般树只需三步，就能规整成左孩子右兄弟的二叉树。

用 C 语言定义长子-兄弟结点，并在转换后的二叉树上先序遍历。

结构体只有两个指针：左指长子、右指兄弟；遍历函数递归地走这两条链，转换后的二叉树完全复用二叉树遍历逻辑。

五种表示法学完容易混：都是存树，凭什么分五种？比一比找父、找子、空间三笔账就清楚了。

某个应用需要频繁地找指定结点的所有孩子，哪种表示法访问路径最直接、最高效？

• ✓没有万能表示法，选型取决于操作频率
• ✓找父亲用父亲法，遍历孩子用孩子法
• ✓长子+兄弟用二叉结构统一一般树
• ✓空间换时间：多存指针换来双向可达
• ✓先把操作需求列清，再定结构

三个问题没有唯一答案：先自己想十分钟，再看参考答案，