logo标签列表

完全二叉树和近似完全二叉树（ACBT）的区别

data-structurestree
10

完全二叉树是一棵每层都完全填满的二叉树，而近似完全二叉树是一棵如果最后一层没有完全填满，则所有节点尽可能地靠左的二叉树。我的疑惑在于以下二叉树的例子：

            O
          /   \
         O      O
       /  \    / \
      O    O  O   O
     / \
    O   O
根据定义它应该是一个不完全的二叉树，但它是一个完全的二叉树。为什么它是一个完全的二叉树而不是一个不完全的二叉树？
根据定义，完全二叉树必须满足以下两个条件： 1. 除了最后一层以外，其它层的节点数都要达到最大值； 2. 所有叶子节点都必须集中在最后一层或倒数第二层上，并且最后一层上的叶子节点必须尽可能地靠左排列。
因此，即使这颗树缺少了一些节点，只要它是满足完全二叉树的两个条件，它也可以被称为完全二叉树。
8个回答
11

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

完美二叉树是一棵具有满最后一层的完全二叉树。

近似完全二叉树是一棵完全但不完美的二叉树。因此，你的例子也是近似完全的。

术语有些混淆，但近似完全二叉树也是完全二叉树。

2
那么什么是几乎完全二叉树？ - Bramsh
完全二叉树和几乎完全二叉树有什么区别？ - Bramsh
@Bramsh 如果它几乎完成了，那么最后一级就不是满的。 - chiastic-security
这不是和完全二叉树一样吗？因为在完全二叉树中，最后一层也不一定是满的，就像我的例子一样。 - Bramsh
2
@Bramsh 如果它是完整的，那么最后一层可能是满的，也可能不是满的。如果它几乎完整，则最后一层不是满的。您的示例符合两个定义。让人困惑的是，一个几乎完整的二叉树是完整的。 - chiastic-security
显示剩余2条评论
7
我不确定这些术语是从哪里来的...我学过的二叉树的技术术语有严格二叉树，完全二叉树和几乎完全二叉树。 严格二叉树是指每个节点要么有两个子节点，要么是叶子节点（没有子节点）的二叉树。 完全二叉树是指每个叶子节点在同一“最大”层上的严格二叉树。 几乎完全二叉树不一定是严格二叉树（虽然它们可以是），也不是完全二叉树。如果树的最大层数为d，则包含从根到第d-1层所有节点的子树是完全二叉树。此外，如果一个节点在第d层有右后代，则其左子树是一个完全二叉树，其叶子都在第d层（树的所有“底部”节点都“尽可能靠左”）。
根据我所学的知识，接受的答案在说“几乎完全二叉树也是完全二叉树”时是错误的。它们不是。如果你删除树的最低层的每个叶子节点，则几乎完全二叉树将变成完全二叉树。
一个几乎完整的树也是一个完全二叉树。 - Kirill Ch
3

实际上，由于阅读不同的书籍而导致了混淆。一些书籍中将完全二叉树（CBT）（即每个除了最后一层，都是完全填充的，且所有节点尽可能靠左）的解释称为几乎完全二叉树，而FBT的解释则作为CBT的解释，而对于严格二叉树的解释则作为FBT。

他们没有给出严格二叉树的解释，或者可能他们没有对FBT进行解释。

1
你把事情搞混了。你从哪里得到这些定义的？
定义：
二叉树T是完全的，如果除了可能最后一层之外，所有层都是完全填充的，并且最后一层的所有节点都在左边。
以及
如果每个节点要么是叶子节点，要么恰好拥有两个子节点，则二叉树T为满二叉树。
你对“完整树”的解释似乎是指所谓的“满&完全二叉树”。
来源：McQuain的《数据结构与算法》中的Full and Complete Binary Trees
一个几乎完整的树是否可以根据我的定义被视为完整树？ - Bramsh
1
是的，“几乎完全树”是“完全树”的一个特殊情况。 - Erti-Chris Eelmaa
0
ACBT是一种树，其中每个具有右子节点的节点也具有左子节点。拥有左子节点并不一定要求节点具有右子节点。
你有相关的参考资料吗？ACBT是一个SIA吗？ - Peter Mortensen
好的，OP已经离开了："上次出现已经超过3年了"。 - Peter Mortensen
0

我们已经知道了完全二叉树和满二叉树的定义，但在某些情况下以下句子可能会令人困惑：

  • 该层是满的
  • 该层被完全填充了
  • 该层中的节点是满的
  • 该层中的节点被完全填充了
  • 该层是完整的

这种情况的后果导致了两个ACBT的定义：

定义1：ACBT是CBT，但不是FBT。
定义2：ACBT是CBT，但不是PBT。

我认为定义2是正确的。

  • ACBT：几乎完全二叉树
  • CBT：完全二叉树
  • FBT：满二叉树
  • PBT：完美二叉树
0

我喜欢以下的定义。

完全二叉树：

在一个完全二叉树中，除了最后一层可能没有填满节点外，其他所有层都填满了。而且，需要注意的是所有的节点都应该从左侧开始填充。

几乎完全二叉树：

几乎完全二叉树是一种特殊的二叉树，插入操作是按层次和从左至右的顺序进行的，最后一层并不总是填满。

因此，几乎完全二叉树也是完全二叉树。与完全二叉树的区别在于几乎完全二叉树的最后一层并不总是填满。

来源：完全二叉树 vs 几乎完全二叉树

1
Baeldung 上的文章似乎得到了非常精细的编辑。 - Peter Mortensen
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接