【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没有右兄弟

思考

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

参考资料

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

药企,独角兽,苏州。团队长期招人,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn