二叉树的存储

二叉树可以使用不同的存储方式，其中两种主要的方式是链式存储和顺序存储。下面分别介绍这两种存储方式：

1. 链式存储（Linked Representation）：

   在链式存储中，每个结点都由一个结构体或类表示，结构体/类中包含数据以及指向左子结点和右子结点的指针。通过这种方式，可以轻松表示任意形状的二叉树。

   struct TreeNode {
       int data;
       TreeNode* left;
       TreeNode* right;
   };

   这是一种更常见的二叉树存储方式，因为它可以有效地表示各种形状的二叉树，包括不完全二叉树。

2. 顺序存储（Array Representation）：

   顺序存储使用数组来表示二叉树。通常，二叉树的结点按照层次顺序依次存储在数组中。具体来说，如果一个结点的索引是i，则其左子结点的索引是2i，右子结点的索引是2i+1。这种方式对于完全二叉树（每层结点都填满，除了最后一层可能不满）非常有效。

   以下是一个简单的示例，展示了如何使用数组表示一个完全二叉树：

3. 索引: 1  2  3  4  5  6  7
   数值: 1  2  3  4  5  6  7

   在数组表示中，根结点通常位于索引1处，左子结点位于索引2处，右子结点位于索引3处，以此类推。这种方式对于完全二叉树来说可以更加紧凑地存储，但不适用于不完全二叉树。

无论是链式存储还是顺序存储，都有其适用的场景。链式存储适用于各种形状的二叉树，而顺序存储适用于完全二叉树或者需要在有限空间内高效存储的情况。