二叉树的存储方式

#二叉树 #数据结构

两种存储方式

• 链式存储
• 数组存储

目录

• 1. 链式存储 - 对象
• 2. 顺序存储 - 数组
  • 2.1. 完美二叉树的数组表示
  • 2.2. 数组可唯一的表示二叉树
  • 2.3. 完全二叉树：数组没有空位
  • 2.4. 是否省内存
  • 2.5. 优劣势分析

1. 链式存储 - 对象

2. 顺序存储 - 数组

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

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

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

2.4. 是否省内存

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

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

2.5. 优劣势分析

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

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