5.2.2 二叉树的存储结构

教材导航 · 第5章

原书定位

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

顺序存储按完全二叉树位置放入数组。根在下标 1 时可直接使用编号公式;根在下标 0 时双亲为 ⌊(i−1)/2⌋\lfloor(i-1)/2\rfloor,孩子为 2i+1,2i+22i+1,2i+2。一般二叉树需预留空位置,高 hh 的最坏情形需要 2h−12^h-1 个位置。

二叉链表结点含数据域、左右孩子指针,可另增双亲指针形成三叉链表。nn 个结点共有 2n2n 个孩子指针,其中 n−1n-1 个对应树边,因此空孩子指针有 n+1n+1 个;增加双亲指针后还多出根的一个空双亲指针。

图5.4 二叉树顺序存储结构

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

图5.6 二叉链表存储结构

图5.6 二叉链表存储结构,原书P133。

对应练习

5.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P132,PDF第144页

原书对照,原书P133,PDF第145页