完全二叉树 满二叉树

完全二叉树是一种特殊的二叉树，除了最后一层外，其他层的节点都必须是满的，并且最后一层的节点从左到右连续排列，不能有间隔。换句话说，完全二叉树是一棵二叉树，除了最后一层可能不满外，其他层都是满的。

满二叉树是一种特殊的完全二叉树，它的每一层都是满的，即每一层的节点数都达到了最大值。换句话说，满二叉树是一棵二叉树，每个节点要么是叶子节点，要么是有两个子节点的非叶子节点。

因此，可以说满二叉树是完全二叉树的一种特殊情况。

相关问题

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

真二叉树、完全二叉树和满二叉树是树的不同类型，它们具有不同的定义和性质。

1. 真二叉树（Proper Binary Tree）：每个节点要么没有子节点，要么有两个子节点。换句话说，每个节点的度数要么为0，要么为2。真二叉树没有节点的度数为1的情况。

2. 完全二叉树（Complete Binary Tree）：对于一棵二叉树，如果除了最后一层外，其他层的节点都是满的，并且最后一层的节点都靠左对齐，那么这棵二叉树就是完全二叉树。

3. 满二叉树（Full Binary Tree）：对于一棵二叉树，如果每个节点的度数要么为0，要么为2，那么这棵二叉树就是满二叉树。换句话说，满二叉树中的每个节点要么没有子节点，要么有两个子节点。

举个例子来说明这三种二叉树的概念：

        A
      /   \
     B     C
    / \   /
   D   E F

在上面的例子中，这棵二叉树既不是真二叉树，也不是完全二叉树，但是它是满二叉树。

完全二叉树与满二叉树

完全二叉树和满二叉树都是二叉树的特殊形态，它们具有独特的性质。

1. 完全二叉树：在完全二叉树中，除了最后一层（如果有的话），所有层次都是完全填满的，且每一层的节点都尽可能地靠左排列。如果最后一层不满，那么所有的叶子节点都会集中在最左边。例如，所有节点都有0或2个子节点，除了最后一个可能的非空层次。

2. 满二叉树：满二叉树是指每一个节点都有0个、1个或2个子节点，并且所有的叶子节点都在同一层，也就是说，除了根节点外，所有节点都被完全填满。换言之，它是一个完全二叉树，且每个非叶子节点都有两个子节点。

这两种特殊的二叉树在算法设计中有着广泛应用，比如哈夫曼树、堆等数据结构的实现就利用了它们的性质。它们的主要区别在于，完全二叉树的最后一层可以不完全填满，而满二叉树则是每一层都被填满的。