二叉树完全二叉树满二叉树

二叉树是一种常见的数据结构，在计算机科学中有着广泛的应用。其中，二叉树又分为完全二叉树和满二叉树。本文将从多个角度对这三种二叉树进行探讨。

一、定义及特点

1. 二叉树：每个结点最多有两个子节点的树结构。

2. 完全二叉树：除了最后一层之外，其余每一层都必须填满，并且最后一层从左到右依次填充。

3. 满二叉树：每一层都必须填满。

二、性质

1. 完全二叉树

1.1 当前节点的左子节点的下标为2n，右子节点的下标为2n + 1。

1.2 当前节点的父节点下标为n/2（n为当前节点的下标）。

1.3 深度为k-1（k为层数）的节点数最多为2^(k-1)，最少为1。

2. 满二叉树

2.1 n层满二叉树的节点总数为2^n - 1。

2.2 深度为k-1（k为层数）的节点数为2^(k-1)。

三、常见应用

1. 完全二叉树

1.1 优先级队列：采用数组实现时，因为完全二叉树的性质，可以轻松找到父节点、左子节点和右子节点。

1.2 堆排序：先将数组构成一个大（小）根堆，然后每次取出堆顶元素进行排序。

2. 满二叉树

2.1 数据结构的实现：满二叉树的结构是简单、完美的，因此程序员喜欢使用数组来实现二叉树，特别是对于完美二叉树来说。

四、对比分析

1. 完全二叉树和满二叉树的深度都一样；满二叉树的节点总数最多，而完全二叉树的节点总数最少。

2. 对于存储结构而言，采用数组实现二叉树时，满二叉树最节省空间，但完全二叉树更好理解。