完全二叉树的构造

完全二叉树构造算法

完全二叉树是一种具有特殊结构的二叉树，它除了最后一层的节点，其它层的节点都是满的，并且最后一层上的节点都靠左。由于它的特殊结构，完全二叉树的构建算法也与其他二叉树的构建算法不同。本文将从多个角度来分析完全二叉树的构造算法。

链式存储

在链式存储方式中，一个完全二叉树是通过节点之间的指针来表示的。我们可以为每个节点添加左子节点和右子节点指针，然后将它们用链表相连接，就可以构建完全二叉树。

数组存储

另一种存储完全二叉树的方式是使用数组。对于完全二叉树，我们可以用数组来存储它，从而避免使用指针和多余的内存。

定义：

对于完全二叉树 T，如果将其根节点放在数组下标为 1 的位置，那么对于任意节点 i（1<= i <=n），都有以下特定性质:

1) 如果 i=1，那么节点 i 为根节点

2) 如果 i > 1，则其父节点为 i/2

3) 如果 2i <= n，那么其左子树根节点为 i * 2

4) 如果 2i + 1 <= n，那么其右子树根节点为 i * 2 + 1

现在我们可以通过数组来表示完全二叉树了，假如二叉树高度为 h，那么数组长度应该为 2^h - 1。

完全二叉树的构建方法

完全二叉树的构建方法有很多，这里主要介绍以下两种：

1. 递归构建方法：

对于一棵深度为 k，节点数为 n 的完全二叉树，除了最后一层的节点外，其它层上的节点数全部为 2^k-1 个，最后一层最多只有 2^(k-1) 个节点，可能少于这个数量。

在这个情况下，可以通过递归的方式来构建完全二叉树：

递归构建子树时，递归参数为当前节点的在数组中的位置 i 和子树的深度 k，构建子树的方式为，先构建其左子树，然后构建右子树。

递归的终止条件是当前节点的位置 i 大于树的节点数 n；如果等于节点数或者小于等于最后一层的节点数时，那么返回一个空节点，并停止递归。

2. 队列构建方法：

另一种构建完全二叉树的方法是使用队列。由于完全二叉树的特殊性质，我们可以使用队列来完成它的构建。具体而言，我们首先将根节点加入队列，然后使用循环不断从队列中取出节点，并为其添加左右子节点，直到队列为空为止。