这是一个完整的二叉树吗？

Question

如果这是一个完整的二叉树,为什么以下不是？

Answer 1

见维基百科:

二叉树的类型

• 完美的二叉树是完整的二叉树,其中所有叶子处于相同的深度或相同的水平.(这也模糊地称为完整的二叉树.)
• 完整的二叉树是一个二叉树,其中除了可能是最后一个级别之外的每个级别都被完全填充,并且所有节点都尽可能地离开.

所以涉及到含糊不清.根据complete = perfect定义,这两个并不完整.但是第二个定义是第一个,因为除了底层之外它是完美的,而底层的所有叶子都在树的最左边.

作为旁注,维基百科引用了NIST,NIST页面在完美的二叉树下表明了这一点:

This kind of tree is called "complete" by some authors ([CLR90, page 95], Leighton) and "full" by others (Budd page 331, Carrano & Prichard page 429, Ege, [HS83, page 225], and Sahni page 461).

对于那些谁不承认,CLR是Corman,Leiserson,Rivest,谁的作者Introduction to Algorithms.

然后,第二个定义用于KDE的"计算机编程艺术"(参见Wolfram Mathworld的完整二叉树),这是算法领域中少数几本比CLR更重要的书籍之一.