5.4.1 普通树的存储结构

双亲表示法为每个结点保存双亲下标，找双亲 $O(1)$，找所有孩子需扫描。孩子表示法为每结点保存孩子链表，找孩子方便。孩子兄弟表示法用 firstChild/nextSibling 两指针，把任意度树转成二叉形态。

手工推演

A 的孩子 B、C、D，B 的孩子 E。孩子兄弟表示中 A.firstChild=B，B.nextSibling=C，C.nextSibling=D，B.firstChild=E。这里右指针表示下一个兄弟，不是原树右孩子。

结构与代码

typedef struct TNode{int data;struct TNode*firstChild,*nextSibling;}TNode;

该表示每结点固定两个指针，适合度不确定的树，并可复用二叉树遍历框架。

错解反馈

把双亲数组下标当结点值；孩子链忘记保存结点本身；在孩子兄弟表示中把兄弟关系误当父子关系。

迁移练习

为部门树“公司→研发、销售；研发→前端、后端”写出所有 firstChild/nextSibling 指针。验收要求从表示还原原树。