5.2.2 二叉树的存储结构
原书定位
印刷页P132起,对应PDF第144页。下文为目视整理的知识提要;完整内容见原书对照。
顺序存储按完全二叉树位置放入数组。根在下标 1 时可直接使用编号公式;根在下标 0 时双亲为 ,孩子为 。一般二叉树需预留空位置,高 的最坏情形需要 个位置。
二叉链表结点含数据域、左右孩子指针,可另增双亲指针形成三叉链表。 个结点共有 个孩子指针,其中 个对应树边,因此空孩子指针有 个;增加双亲指针后还多出根的一个空双亲指针。

图5.4 二叉树顺序存储结构,原书P132。

图5.6 二叉链表存储结构,原书P133。
对应练习
关联知识
- 1.1.2 数据结构三要素
- 2.2 线性表的顺序表示
- 2.3 线性表的链式表示
- 3.4.2 数组的存储结构
- 3.4.3 特殊矩阵的压缩存储
- 5.2 二叉树的概念
- 6.2 图的存储及基本操作
- 6.2.1 邻接矩阵法
原书对照
展开原书对照截图

