完全二叉树和平衡二叉树的区别

Question

平衡二叉树和完全二叉树有什么区别？
是否可以说每个完全二叉树都是平衡树？
反过来呢？

- sheidaei

Answer 1

平衡二叉树是指每个节点的两个子树深度差不超过1的二叉树。

完全二叉树是指除了最后一层之外的所有层都被完全填满，并且最后一层上的所有叶子节点都靠左排列的二叉树。

以下是一个平衡二叉树，但不是完全二叉树。每个完全二叉树都是平衡二叉树，但反之不一定成立。

        1
     1     1
   1   1     1
 1 

正如其名，在一棵完全二叉树中，层级差别总不会超过1，因此它总是平衡的。

- sheidaei

---

请注意，“平衡二叉树”没有标准定义，而且有多种变体：https://cs.stackexchange.com/questions/3515/two-definitions-of-balanced-binary-trees 和 https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees 上显示的示例。 - huyz

Answer 2

由于进一步涉及到完美、平衡、完整和充分的问题 - 这里提供一个澄清这些问题的答案。假设有一个二叉树：

1. 平衡：每个节点的左子树和右子树的高度差不超过1。

2. 满：除了叶子节点外，所有节点都有0或2个子节点。

3. 完全：

   • 除了最后一层之前的所有节点必须有2个子节点。
   • 最后一层的所有节点尽可能向左。

总结：

• 完全树：必须是平衡的；可以是满的
• 满树：可以是平衡的；可以是完全的
• 平衡树：可以是完全的；可以是满的

例子：

---

• 满且平衡 - 所有节点都有0或2个子节点， 第3层 - 第2层 ≤ 1，（不完全 - 最后一层的节点没有尽可能向左）

         1             --- LEVEL 0
       /    \
      1      1         --- LEVEL 1
     /\      /\
    1  1    1  1       --- LEVEL 2
    -  /\   -  -
      1  1             --- LEVEL 3
  x x -  - 
  

• 完整、平衡和完全 - 所有节点都有0或2个子节点，3-2 <= 1，最后一层的节点尽可能靠左：

       1             --- LEVEL 0
     /    \
    1      1         --- LEVEL 1
   /\      /\
  1  1    1  1       --- LEVEL 2
 /\  -    -  -
1  1                 --- LEVEL 3
-  - 

• 完整的 - 所有节点都有0或2个孩子(不平衡的 - 3 - 1 > 1, 不完整的 - 第1层有一个没有孩子的节点):

        1              --- LEVEL 0
       / \
      1   1            --- LEVEL 1
     / \  -
    1   1              --- LEVEL 2
   / \  - x x
  1   1                --- LEVEL 3
  -   -
  

• 完整平衡 - 最后一层节点尽可能靠左，3 - 3 <= 1（非满树 - 存在一个拥有1个子节点的第二层节点）：

         1             --- LEVEL 0
       /    \
      1      1         --- LEVEL 1
     /\      /\
    1  1    1  1       --- LEVEL 2
   /\  /\  /\  /x
  1 1 1  11 1 1        --- LEVEL 3
  - - -  -- - -
  

• 平衡 - 3 - 3 <= 1，（非满 - 存在一个具有1个子节点的第2级节点，不完全 - 最后一层的节点未尽可能地靠左）

         1             --- LEVEL 0
       /   \
      1     1          --- LEVEL 1
     /\     /\
    1  1   1  1        --- LEVEL 2
   /\ /\  /x  /\
  1 11  11   1  1      --- LEVEL 3
  - --  -- x -  -
  

---

4. 完美二叉树: 所有内部节点都有两个子节点，所有叶子节点深度相同。

以上示例都不是完美二叉树。

- devdev_dev

Answer 3

平衡树：平衡树是一种二叉树，其中每个节点左子树高度和右子树高度的差值最多为k，其中k是平衡因子。如果这个平衡因子为0，则该树将被称为完全平衡树。

示例：
                        8
                    6         1
                3          9     1

这棵树是平衡树，平衡因子为1，因为每个节点子树的高度差都是0或1。 完全二叉树：如果除了叶子节点外，每个级别都被完全填充，则称为完全二叉树。并且任何新插入的叶节点将从左到右进行，这意味着左侧级别的叶子将首先被完全填充。

示例：                  8
                            6          1
                        3     5     4     1

现在这棵树是完全二叉树，如果要进行新的插入，则应该在左侧的叶子节点下进行，例如此示例中的3。一旦3填满了左右子节点，那么5将成为新插入的下一个叶子节点。

- Pooja

---

这是一个完美二叉树的描述，而不是完全二叉树。完全二叉树是一种二叉树，其所有层级（除了最后一层）都完全填充，并且最后一层的所有叶子节点都在左侧。 - ramusus

Answer 4

当一个高度为h的二叉树的所有叶子节点都在第h层，并且每个父节点恰好有两个子节点时，该树被称为满二叉树

当除了最后一层外的所有层都包含尽可能多的节点，并且最后一层上的节点从左到右填充时，该树被称为完全二叉树（不是满二叉树，但是完全）

当二叉树中每个节点都有两个子树，且这些子树的高度完全相同时，该树被称为完全平衡二叉树

完全平衡二叉树是满二叉树

如果一个节点的子树之间的差异不超过1，则该节点的子树被称为高度平衡或简称平衡

- hpl002

---

只有当一棵树是满的时候，它才完全平衡。 - fmnijk

完全平衡的树不一定是满树。规则是：平衡二叉树可以是完全且满的、完全但不满的、或者不完全也不满的。不平衡的树永远不会是完全的；它们可以是满的或者不完全也不满的。 - user7247147