完全二叉树与几乎完全二叉树(ACBT)的区别

Question

完全树是一棵树，每个层次都被完全填充，an 几乎完全树是一棵树，如果最后一层没有完全填充，那么所有节点都尽可能地保持在最左边。我的困惑出现在以下二叉树示例中：

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

根据定义，它应该是一个不完全的二叉树，但它是一个完整的二叉树。这怎么是一个完整的二叉树，为什么它不是一个不完整的二叉树？

Answer 1

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

一个完美的二叉树是一个完整的二叉树，其中的最后一个层次是满的。

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

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

Answer 2

事实上，混乱是由于阅读不同的书籍。完整二叉树( CBT )的解释(可能是最后一层除外)在一些书中被称为几乎完全二叉树，而对FBT的解释则被看作是对CBT的解释，而对严格二叉树的解释则是FBT。

他们对严格的二叉树没有任何解释，也可能没有对FBT的解释。

Answer 3

你把事情搞糊涂了。你从哪里得到这些定义的？

定义：

二叉树T是完全，如果每个节点要么是叶，要么正好拥有两个子节点。

和

具有n级的二叉树T是完全，如果除了最后一层可能是完全满的，并且最后一级的所有节点都位于左侧，则所有级别都是完全满的。

您对“完整树”的解释似乎是所谓的“完整&完整树”。

资料来源:数据结构和算法中的完全二叉树 ( McQuain )