完全二叉树的性质

完全二叉树是一种特殊的二叉树，它具有很多独特的性质。在本文中，我们将从多个角度来分析完全二叉树的性质。

1. 完全二叉树的定义

我们首先需要明确完全二叉树的定义。完全二叉树是一棵二叉树，其中所有非叶子节点的度数都为2，除了可能最后一层之外，其它层的节点数都是满的，最后一层的节点都靠左排列。

下图展示了一个完全二叉树的例子：


2. 完全二叉树的性质

2.1 节点数和深度的关系

一棵完全二叉树的深度为h，节点数为n，则有以下结论：

- 当i属于[1, h-1]时，第i层上的节点数都是2^(i-1)个。

- 当i=h时，第h层上的节点数在1~2^h-1之间。

- 当n属于[2^h-1, 2^(h+1)-1]时，一棵深度为h的二叉树，当且仅当其节点编号为1~n时，才是一棵完全二叉树。

比如在上面的例子中，深度为3，节点数为7。

2.2 完全二叉树的存储

完全二叉树可以用数组来存储，其存储方式如下：

- 如果一个节点的下标是i，则它的左子节点的下标是2i，右子节点的下标是2i+1，父节点的下标是i/2（向下取整）。

- 从根节点开始，从上到下、从左到右依次存储每个节点。

比如在上面的例子中，我们可以用如下数组来存储这棵完全二叉树：

```

[1, 2, 3, 4, 5, 6, 7]

```

2.3 完全二叉树的遍历

对于完全二叉树，由于每一层的节点都是从左到右依次排列，因此其遍历顺序与普通二叉树略有不同。有以下三种遍历方式：

- 前序遍历：先访问根节点，再访问左子树，最后访问右子树。

- 中序遍历：先访问左子树，再访问根节点，最后访问右子树。

- 后序遍历：先访问左子树，再访问右子树，最后访问根节点。

其中，前序遍历的结果为1->2->4->5->3->6->7，中序遍历的结果为4->2->5->1->6->3->7，后序遍历的结果为4->5->2->6->7->3->1。

3. 总结

在本文中，我们从完全二叉树的定义、节点数和深度的关系、存储方式、遍历等多个角度，介绍了完全二叉树的性质。完全二叉树是一种特殊的二叉树，其具有很多独特的性质，包括节点数和深度的关系、存储方式、遍历等方面，我们可以根据这些性质来更加灵活地操作和分析完全二叉树。