【5.3】二叉树的存储结构

一、二叉树的链式存储结构

二叉树的各结点随机地存储在内存空间中，结点之间的 逻辑关系用指针来链接。

二叉链表：

• 指针 left 和 right，分别指向结点的左孩子和右孩子

三叉链表：

• 指针 left 和 right，分别指向结点的左孩子和右孩子
• 增加一个父指针

• 指向父母的指针parent, “向上”能力

BinaryTreeNode类中增加两个私有数据成员

递归框架寻找父结点——注意返回

思考

• 该算法是什么框架?
• 该算法是什么序遍历?
• 可以怎样改进?
• 可以用非递归吗?
• 可以用BFS吗?
• 怎样从这个算法出发，寻找兄弟结点

非递归框架找父结点

二、空间开销分析

• 存储密度 α (≤1) 表示数据结构存储的效率

• 结构性开销γ=1-α

根据满二叉树定理:一半的指针是空的

• 每个结点存两个指针、一个数据域
• 总空间 (2p + d)n
• 结构性开销:2pn
• 如果 p = d, 则结构性开销 2p/ (2p + d ) = 2/3

• C++ 可以用两种方法来实现不同的分支与叶结点:
• 用union联合类型定义
• 使用C++的子类来分别实现分支结点与叶结点，并采用虚函数isLeaf来区别分支结点与叶结点
• 早期节省内存资源
• 利用结点指针的一个空闲位(一个bit)来标记结点所属的类型
• 利用指向叶的指针或者叶中的指针域来存储该叶结点的值

三、完全二叉树的顺序存储结构

• 顺序方法存储二叉树
• 把结点按一定的顺序存储到一片连续的存储单元
• 使结点在序列中的位置反映出相应的结构信息
• 存储结构上是线性的

• 逻辑结构上它仍然是二叉树形结构

完全二叉树的下标公式

• 从结点的编号就可以推知其父母、孩子、兄弟的编号
• 当 2i+1<n 时，结点 i 的左孩子是结点 2i+1， 否则结点i没有左孩子
• 当 2i+2<n 时，结点 i 的右孩子是结点 2i+2，否则结点i没有右孩子
• 当 0<i<n 时，结点 i 的父亲是结点 [(i-1)/2]
• 当 i 为偶数且 0<i<n 时，结点 i 的左兄弟是结点 i-1，否则结点 i 没有左兄弟
• 当 i 为奇数且 i+1<n 时，结点i的右兄弟是结点 i+1，否则结点i没有右兄弟

思考

• 用三叉链的存储形式修改二叉树的 相应算法。特别注意插入和删除结 点，维护父指针信息。
• 完全三叉树的下标公式?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾