二叉树的两种存储实现：链式与连续编号

同一棵逻辑上的二叉树可以用两种截然不同的物理方式存进存储器：链式存储让每个节点各自占一小块空间，内含数据和指向左右孩子的两个指针，靠一个根指针作为入口，逐层跳转访问，这种方式对任意形状的树都适用，不浪费空间；连续存储则把整棵树按层压进一整块连续的存储单元——根放在位置 1，位置 n 的节点的两个孩子固定放在位置 2n 和 2n+1，靠简单的算术就能算出任意节点的双亲和兄弟位置，访问效率极高，但如果树的形状稀疏而不平衡（某些分支远比其他分支深），大量位置会空置浪费。发散：这再次印证了[[数据结构本质是对线性存储器的抽象模拟]]的核心命题——同一个逻辑抽象（二叉树）完全可以对应多种物理实现，选择哪种实现不取决于”树是什么”，而取决于树的形状特征（是否接近平衡）和使用模式（是否需要频繁按位置公式直接定位双亲/兄弟）。