完全二叉树跟满二叉树的区别

完全二叉树和满二叉树都是在二叉树这种数据结构中属于比较特殊的几种。虽然它们都是二叉树，但是它们的特点却是不同的。在本篇文章中，将会详细介绍完全二叉树和满二叉树的区别以及它们的特点和应用。

一、 完全二叉树的定义和特点

完全二叉树是指除最后一层之外，其它层的节点个数都已经达到最大，而且最后一层的所有节点都必须靠左排列的二叉树。它的特点是：

1. 所有的叶子节点都集中在树的最下层或者是次下层；

2. 最后一层的所有叶子节点都靠左排列；

3. 任意节点的左右子树的高度差不超过1；

4. 它可以用数组来表示。

二、 满二叉树的定义和特点

满二叉树是说如果一棵具有n个节点的深度为h的二叉树，当且仅当其每一个节点都与深度为h的满二叉树中编号为1至n的节点一一对应时，称该二叉树为一棵满二叉树。它的特点是：

1. 除叶子节点外，每个节点都有左右两个子节点；

2. 所有叶子节点都处于同一层；

3. 节点总数为2的深度次方数减1。

三、 完全二叉树和满二叉树的区别

1. 完全二叉树的叶子节点不一定全部在同一层上，而满二叉树的每个非叶子节点都有两个子节点，叶子节点全部在同一层；

2. 完全二叉树的深度与节点数量并不是一定对应的，而满二叉树的深度和节点数量有固定的对应关系；

3. 完全二叉树可以由数组来表示，而满二叉树无法用数组来表示。

四、 完全二叉树和满二叉树的应用

完全二叉树和满二叉树的应用都十分广泛。下面分别介绍它们的应用：

1. 完全二叉树

完全二叉树的应用十分广泛，它可以用于堆的实现。大根堆和小根堆的创建都可以通过完全二叉树实现。除此之外，它还可以用于Huffman编码树，追踪赛程的构建、矩阵重建等等。

2. 满二叉树

如果你需要在满二叉树上进行基于线段树的数据存储和查询等操作，那么满二叉树是你的不二之选。除此之外，它还可以被用来生成最小生成树。