5.4.1 树的存储结构

教材导航 · 第5章

原书定位

印刷页P171起,对应PDF第183页。下文为目视整理的知识提要;完整内容见原书对照。

表示法内容适合操作
双亲表示法每结点记录双亲在数组中的下标找双亲快,找全部孩子需扫描
孩子表示法每结点对应一条孩子链表找孩子方便,找双亲需扫描
孩子兄弟表示法firstchild 指首孩子,nextsibling 指右兄弟用两个指针表示任意度的树

双亲表示法中数组下标标识结点,关系由额外双亲域表示;不要混同二叉树按完全位置编号的顺序存储。孩子兄弟表示可再增双亲指针加速向上查找。

图5.20 树的双亲表示法

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

图5.21 孩子表示法与孩子兄弟表示法

图5.21 孩子表示法与孩子兄弟表示法,原书P172。

对应练习

5.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P171,PDF第183页

原书对照,原书P172,PDF第184页