二叉树与完全二叉树

二叉树是一种重要的数据结构，它是由n个结点组成的有限集合，结点可能为空，也可能非空，每个结点至多只有两个子结点。而完全二叉树是一种特殊的二叉树，除了最后一层，其余层的结点都是满的，最后一层的结点都靠左排列。在这篇文章中，我们将从多个角度来分析二叉树与完全二叉树的不同之处。

1. 结构

二叉树是一棵树，它与其他树的最大不同在于每个结点至多只有两个子结点。如果左子树非空，则左子树上所有结点的值都小于该结点的值；如果右子树非空，则右子树上所有结点的值都大于该结点的值。

完全二叉树的特点就是它的所有非叶子结点都有两个子结点，并且最后一层的结点都靠左排列。如果对于一棵具有n个结点的完全二叉树，它的结点编号按层次由上至下，由左至右依次排列，则对于第i个结点，它的左子结点的编号是2i，右子结点的编号是2i+1，其父结点的编号是i/2（向下取整）。

2. 查找效率

由于二叉树的结构可以保证每个结点的子结点最多只有两个，因此查找效率相比于普通的链表结构有很大的提高。在一棵二叉树中查找一个元素的时间复杂度与树的高度有关，最坏情况下为O(n)。而完全二叉树的查找效率更高，因为每个结点都有两个子结点，而且最后一层上结点的数目非常少，所以完全二叉树的深度大约是以2为底n的对数。因此它的查找时间复杂度是O(log n)。

3. 插入和删除

在二叉树中插入一个结点的过程需要先查找到插入位置，然后将新结点插入到该位置。在删除某个结点时，需要将该结点的子树转移，并确定其位置。因此，对于一个有n个结点的二叉树，插入一个结点或者删除一个结点的时间复杂度为O(n)。

对于完全二叉树来说，插入一个结点通常是插入到最后一层作为一个新的叶子结点。因为最后一层的叶子结点是顺序排列的，所以可以通过二分查找的方法很快找到要插入的位置。而删除一个结点时，通常是删除最后一层的最后一个结点，然后将该结点和它的父结点交换的位置，最后逐级向上调整即可。因此，在完全二叉树中插入和删除一个结点的时间复杂度同样是O(log n)。

4. 存储方式

对于一棵有n个结点的二叉树，最简单的存储方式是使用数组，将树的结构存储在一个一维数组中。通过指针和数组下标之间的关系，可以在该数组中实现二叉树的操作。对于一棵完全二叉树，因为它的结点分布是固定的，所以最简单的存储方式也是采用数组存储。通过这种方式，可以很方便地确定一个结点的子结点和父结点的位置，而且还可以有效地减少存储空间。