如果这是一棵完全二叉树，为什么下面这棵不是呢？
2个回答
5
请参见维基百科：二叉树的类型
- 完美二叉树是一棵满二叉树，其中所有叶子位于同一深度或同一级别。(这也可以称为完全二叉树，但含义不明确。)
- 完全二叉树是一棵二叉树，在除了可能是最后一层的每个层中，节点都被完全填充，并且所有节点尽可能地靠左。
因此，存在歧义。使用 complete = perfect 的定义，这两者都不完全。但是使用第二个定义，第一个是完全的，因为除了底部层外，它是完美的，底部层的所有叶子都在树的最左边。
附带说一下，维基百科引用了 NIST，NIST 页面 在完美二叉树下指出：
某些作者将这种树称为“完整”([CLR90, page 95], Leighton)，而其他人则称之为“满”(Budd page 331, Carrano & Prichard page 429, Ege, [HS83, page 225], and Sahni page 461)。
对于那些不认识的人，CLR 是指 Corman、Leiserson、Rivest，他们是《算法导论》的作者。
然后，KDE 的《计算机编程艺术》(请参见 Wolfram Mathworld 上的完全二叉树)使用第二个定义，这是少数几本在算法领域具有更大影响力的书之一，比 CLR 更重要。
- zw324
5
在第一张图片中，所有的叶子不在同一水平线上。 - user366312
@JMSA：是的，请看第二个定义。 - zw324
那么第二个是什么类型的树？ - user366312
@JMSA 两者都可以被称为“完备的”；事实上，正如我刚刚补充的那样，《算法导论》使用了第一个定义作为“完备的”。但是你所使用的来源可能使用了第二个定义。你能告诉我你参考的是哪本书/网站吗？我很想去查看一下。 - zw324
0
参考此链接http://www.youtube.com/watch?v=tORLeHHtazM。
由Dr. Naveen Garg讲解的数据结构。它们都不是完全二叉树，因为完全二叉树是一种在第i层上拥有(2^i)个节点的二叉树。
- user1657017
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接