二叉树的存储方式

#二叉树 #数据结构

目录

• 1. 总结
• 2. 链式存储 - 对象
• 3. 顺序存储 - 数组
  • 3.1. 完美二叉树的数组表示
  • 3.2. 数组可唯一的表示二叉树
  • 3.3. 完全二叉树：数组没有空位
  • 3.4. 是否省内存
  • 3.5. 优劣势分析

1. 总结

两种存储方式

• 链式存储
• 数组存储

2. 链式存储 - 对象

3. 顺序存储 - 数组

3.1. 完美二叉树的数组表示

3.2. 数组可唯一的表示二叉树

3.3. 完全二叉树：数组没有空位

3.4. 是否省内存

完全二叉树用数组来存储是最省内存的方式

非完全二叉树则会浪费空间，如下图：

3.5. 优劣势分析

二叉树的数组表示主要有以下优点

• 数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快
• 不需要存储指针，比较节省空间
• 允许随机访问节点 然而，数组表示也存在一些局限性
• 数组存储需要连续内存空间，因此不适合存储数据量过大的树。
• 增删节点需要通过数组插入与删除操作实现，效率较低。
• 当二叉树中存在大量 None 时，数组中包含的节点数据比重较低，空间利用率较低