简述二叉树的存储方式？

八股文_数据结构面试题 0 133

二叉树的存储方式主要有两种：链式存储和顺序存储。

链式存储：在链式存储方式中，每个节点存储数据和指向左右子节点的指针。每个节点通常有三个部分：
- 数据部分（存储节点的值）
- 左子节点指针（指向左子节点）
- 右子节点指针（指向右子节点）
链式存储的优点是动态分配内存，灵活性高，适合于节点数不确定、结构不固定的二叉树。缺点是需要额外的指针空间，浪费内存。
顺序存储：顺序存储方式通过数组来表示二叉树。树的节点按层次顺序存储在数组中，节点的索引与树的结构之间存在映射关系。对于一个节点在数组中的索引 ( i )：
- 左子节点索引为 ( 2i + 1 )
- 右子节点索引为 ( 2i + 2 )
- 父节点索引为 ( \lfloor (i-1)/2 \rfloor )
顺序存储的优点是内存访问顺序紧凑，空间开销较小。缺点是数组的大小固定，二叉树的大小如果不断变化会导致空间浪费。

在链式存储方式中，二叉树的每个节点都是一个对象，包含三个部分：
– 数据部分：保存节点的值。
– 左子节点指针：指向该节点的左子节点，如果没有左子节点，则指向空（NULL）。
– 右子节点指针：指向该节点的右子节点，如果没有右子节点，则指向空（NULL）。

链式存储方式具有很大的灵活性。因为每个节点可以动态分配内存，树的结构可以随着节点的增减而动态变化，不会浪费空间。然而，由于每个节点需要存储两个指针，因此会增加内存开销。

应用场景：链式存储适用于节点数不确定、结构不固定的情况，特别是在插入和删除频繁的情况下，如树结构的动态变化。

顺序存储方式通过数组来存储二叉树。对于一颗高度为 ( h ) 的二叉树，数组的长度最多为 ( 2^h – 1 )（完全二叉树的节点数）。节点的排列是按照层序进行的，即从上到下，从左到右。

父子关系映射：
- 节点 ( i ) 的左子节点索引为 ( 2i + 1 )
- 节点 ( i ) 的右子节点索引为 ( 2i + 2 )
- 节点 ( i ) 的父节点索引为 ( \lfloor (i-1)/2 \rfloor )

顺序存储的优点是内存访问顺序紧凑，空间开销小，且数组可以利用缓存，提高存取效率。缺点是数组大小必须预先确定，且树的节点数目变化时可能导致浪费空间或无法扩展。

应用场景：顺序存储适合于节点数确定且固定的二叉树，如完全二叉树、二叉堆等数据结构。

总结

二叉树的存储方式有链式存储和顺序存储两种。链式存储通过指针来表示树的结构，具有较大的灵活性，适合于结构动态变化的情况；顺序存储通过数组来表示树的结构，内存访问紧凑，适合节点数固定的情况。两者各有优缺点，选择存储方式通常依赖于应用场景的需求。