完全二叉树和几乎完全二叉树的区别

Question

完全树是每一层都被完全填充的树，而几乎完全树是一棵树，如果最后一层没有完全填充，那么所有节点都尽可能地离开。我的困惑在于以下二叉树示例：

            O
          /   \
         O      O
       /  \    / \
      O    O  O   O
     / \
    O   O

根据定义它应该是一棵不完全二叉树，但它是一棵完全 二叉树。如果有人可以详细说明这个完整的二叉树如何，为什么不是不完整的二叉树？

Answer 1

你的例子是一个完整的二叉树：一个完整​​的二叉树可以有一个不完整的最后一层，只要它的所有叶子都被推到左边。

一个完美的二叉树是完全二叉树中，最后一级是满的。

一个几乎完全二叉树是一个完整的，但并不完美二叉树。所以你的例子也差不多完成了。

术语令人困惑，但几乎完整的二叉树也是完整的。

Answer 2

不确定这些术语中的一些来自哪里......我学到的二叉树的技术术语是严格二元的、完整的和几乎完整的。

严格二叉树是每个节点要么有两个孩子要么是叶子（没有孩子）的二叉树。

完全二叉树是严格的二叉树，其中每个叶子都处于相同的“最大”级别。

几乎完全二叉树不一定是严格二叉树（尽管它们可以是），并且不是完全二叉树。如果树的最大层级为 d，则包含从根到层 d-1 的所有节点的子树是完整树。另外，如果一个节点在第 d 层有一个右后代，那么它的左子树是一个完整的树，它的叶子都在第 d 层（树的所有“底部”节点都“尽可能向左”）。

从我所学到的，接受的答案是不正确的，说“几乎完整的二叉树也是完整的”。他们不是。如果您删除树最低级别的每个叶子，则几乎完整的二叉树将是完整的。