非完全二叉树顺序存储

二叉树是一种重要的数据结构，它可以用来表示树形结构的数据。根据定义，二叉树最多有两个子节点，分别称为左子节点和右子节点。如果一个二叉树的所有叶子节点都集中在二叉树的最后一层或倒数第二层，并且每个非终端节点都有两个子节点，则该二叉树称为完全二叉树。

在计算机科学中，完全二叉树是一种可用于实现堆数据结构、哈夫曼编码和字典树等算法的重要数据结构。在二叉树的存储方面，顺序存储是一种常用的存储方式。使用数组来存储完全二叉树可以保证树的结构不受任何影响，并且可以在数组中进行快速的随机访问。然而，在非完全二叉树的情况下，该方法并不是最佳选择。

非完全二叉树是一种在二叉树的最后一层或倒数第二层之外的位置没有被填满的二叉树。例如，下图所示的二叉树就是一个非完全二叉树。

```

4

/ \

1 2

/ \ /

5 6 7

```

那么，在非完全二叉树的情况下，如何使用数组来存储该二叉树呢？考虑到数组是一种连续的数据结构，我们可以把二叉树的所有节点都存储在一个一维数组中。为了方便起见，我们可以给每个节点一个编号，类似于下图所示的方式：

```

1

/ \

2 3

/ \ /

4 5 6

```

在上图所示的二叉树中，我们可以给每个节点按照层次遍历的顺序分配一个编号。根节点的编号是1，它的左子节点的编号是2，右子节点的编号是3。同样地，节点2的左子节点是4，右子节点是5，节点3的左子节点是6。这样一来，我们就可以把整个二叉树存储在一个连续的数组中。

由于非完全二叉树的节点是不完全填满的，所以我们需要使用一个特殊的符号来表示空节点。在大多数情况下，我们可以使用null或0来表示空节点。因此，上图所示的二叉树就可以用如下的数组来表示：

```

1, 2, 3, 4, 5, 6, null

```

在这个数组中，元素的索引从0开始，因此，元素1的左子节点的索引是1，右子节点的索引是2，左子节点的左子节点的索引是3，右子节点的右子节点的索引是6。元素4和5表示的是节点2的左右子节点，它们的左右子节点都是空节点。元素6表示的是节点3的左子节点。

与完全二叉树的情况不同，非完全二叉树的存储方式并不能保证所有的节点都能被顺序访问。在实现二叉树遍历算法时，我们需要特别注意判断空节点，并且需要采用递归或栈等数据结构来实现遍历。这种方法的优点是存储空间比链式存储小，同时趋近于数组的顺序存储带来的快速访问特性，缺点是增删节点时需要实现复杂。

综上所述，非完全二叉树顺序存储是一种在非完全二叉树情况下的数组存储方式。在该方式中，我们把所有的节点存储在一个一维数组中，并使用特殊符号表示空节点。这种存储方式具有空间占用小，且趋近于数组顺序存储带来的快速访问特性的优点，但增删节点时，可能需要进行复杂的操作。