完全二叉树的构造
完全二叉树构造算法
完全二叉树是一种具有特殊结构的二叉树，它除了最后一层的节点，其它层的节点都是满的，并且最后一层上的节点都靠左。由于它的特殊结构，完全二叉树的构建算法也与其他二叉树的构建算法不同。本文将从多个角度来分析完全二叉树的构造算法。
链式存储
在链式存储方式中，一个完全二叉树是通过节点之间的指针来表示的。我们可以为每个节点添加左子节点和右子节点指针，然后将它们用链表相连接，就可以构建完全二叉树。
数组存储
另一种存储完全二叉树的方式是使用数组。对于完全二叉树，我们可以用数组来存储它，从而避免使用指针和多余的内存。
定义：
对于完全二叉树 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. 队列构建方法：
另一种构建完全二叉树的方法是使用队列。由于完全二叉树的特殊性质，我们可以使用队列来完成它的构建。具体而言，我们首先将根节点加入队列，然后使用循环不断从队列中取出节点，并为其添加左右子节点，直到队列为空为止。
