5.4.1 树的存储结构
原书定位
印刷页P171起,对应PDF第183页。下文为目视整理的知识提要;完整内容见原书对照。
| 表示法 | 内容 | 适合操作 |
|---|---|---|
| 双亲表示法 | 每结点记录双亲在数组中的下标 | 找双亲快,找全部孩子需扫描 |
| 孩子表示法 | 每结点对应一条孩子链表 | 找孩子方便,找双亲需扫描 |
| 孩子兄弟表示法 | firstchild 指首孩子,nextsibling 指右兄弟 | 用两个指针表示任意度的树 |
双亲表示法中数组下标标识结点,关系由额外双亲域表示;不要混同二叉树按完全位置编号的顺序存储。孩子兄弟表示可再增双亲指针加速向上查找。

图5.20 树的双亲表示法,原书P171。

图5.21 孩子表示法与孩子兄弟表示法,原书P172。
对应练习
关联知识
原书对照
展开原书对照截图

