完全二叉树与非完全二叉树的区别

二叉树是计算机科学中最基础的数据结构之一，它的应用范围非常广泛。二叉树按照结构可以分为完全二叉树与非完全二叉树。明确这两者的区别对二叉树的应用有着重要意义，本文将从多个角度来分析完全二叉树与非完全二叉树的区别。

一、定义

完全二叉树：当一棵二叉树最后一层空缺节点时，其余部分是一棵完全二叉树。

非完全二叉树：除了完全二叉树以外的二叉树都可以称为非完全二叉树，也称为一般二叉树。

二、特点

完全二叉树有以下特性：

1. 每个节点的度数要么为2，要么为0；

2. 叶节点只能在最下层出现，最后一层的叶节点要么集中在左边，要么集中在右边，不能左右交错；

3. 非叶节点的度数为2，且它的左子树和右子树必定存在；

4. 深度为k的完全二叉树含有2^k -1个节点，其中有2^(k-1)个叶节点。

非完全二叉树没有以上限制条件，可以有任意节点的度数、可以存在度数为1的节点，叶节点的层数也是任意的。

三、构建方式

完全二叉树的构建方式相对容易，可以按照层次顺序从上到下、从左到右依次插入节点。如果在构建过程中遇到没有左子节点（或右子节点），那么该节点一定位于最下面一层，它之后的节点都应该是子节点为空的节点。

非完全二叉树的构建方式相对较为复杂，可以通过手动插入节点或其他算法来完成。插入节点的位置可以是任意的，那么就需要自行控制其节点的度数。

四、存储效率

完全二叉树的存储效率是相对较高的，可以将其存储在数组中，节省空间。由于完全二叉树规律很简洁，以数组形式存储时，可以通过下标计算出某个节点父亲节点、左右子节点的位置，因此省去了存储指针类型的操作，降低了存储和访问的时间复杂度。

非完全二叉树在数组中的存储方式相对复杂。因为非完全二叉树不具备规律性，因此需要开辟额外的空间来存储和访问子节点，增加了时间和空间消耗。

五、搜索效率

完全二叉树的搜索效率相对较高，可以利用完全二叉树的规律来进行有针对性的搜索。在完全二叉树的搜索中，可以通过二分法进行快速查找，效率比较高。

非完全二叉树的搜索效率相对较低，在进行搜索的时候需要遍历整个树，时间复杂度较高。

六、适用场景

完全二叉树的应用非常广泛，它可以用于堆、哈夫曼编码等算法的实现。同时还可以用于较快的搜索以及时间和空间开销相对较小的存储。

非完全二叉树的应用依旧非常广泛，但由于它相对无规律、搜索效率较低且空间浪费较大，因此在使用时还需要针对具体场景来做出考虑。

综上所述，完全二叉树与非完全二叉树之间存在比较大的差别，它们在定义、特点、构建方式、存储效率、搜索效率和适用场景等方面都有所不同。在使用二叉树的时候，需要根据实际需求来选择适合的类型。