Is this a Complete Binary Tree?

If this is a Complete Binary Tree, why the following is not?

开发者_如何转开发

---

See Wikipedia:

Types of binary trees

• A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level. (This is ambiguously also called a complete binary tree.)
• A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

So there is ambiguity involved. With the complete = perfect definition, these two are not complete. But with the second definition, the first is, since except for the bottom level it is perfect, and all the leaves at the bottom level are in the far left of the tree.

As a side note, wikipedia referenced NIST, and the NIST page indicates this under the perfect binary tree:

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).

For those who does not recognize, CLR is Corman, Leiserson, Rivest, who are the authors of Introduction to Algorithms.

Then again, the second definition is used in KDE's The Art of Computer Programming (See Complete Binary Tree at Wolfram Mathworld), which is one of the few books in the area of algorithms that carries more weight than CLR.

---

for reference see this http://www.youtube.com/watch?v=tORLeHHtazM

data structures by Dr. naveen garg. Both of them are not complete binary tree.Because a complete binary tree is a binary tree that has (2^i) nodes at level i.