Difference between full and almost complete binary tree
A full tree is a tree in which each level is completely filled and a Nearly complete tree is a tree in which, if the last level is not completely filled, all nodes are as far as possible. my confusion about the following binary tree example:
O
/ \
O O
/ \ / \
O O O O
/ \
O O
By definition, it must be an incomplete binary tree , but it is a complete binary tree . if someone can figure out how is this complete binary tree and why not incomplete binary tree?
source to share
Your example is a complete binary tree: a complete binary tree may have an incomplete final level if all leaves in it are shifted to the left.
A perfect binary tree is a complete binary tree with the last level filled in.
A nearly complete fractional tree is a complete but not perfect binary tree. So your example is almost complete as well.
The terminology is confusing, but the complete full binary tree is complete as well.
source to share
Not sure where some of these terms come from ... the technical terminology for binary trees that I have learned is strictly binary , complete and almost complete .
Strictly binary trees are binary trees where each node has two children or is a leaf (has no children).
Completed binary trees are strictly binary trees where each leaf is at the same maximum level.
Nearly complete binary trees are not necessarily strictly binary (although they may be) and are not terminated . If the tree has a maximum level d, then the subtree containing all the nodes from root to level d-1 is a complete tree. Also, if a node has a right child at level d, then its left subtree is a complete tree with leaves at level d (all the "bottom" nodes of the tree are "as far away" as possible).
From what I've been taught, the accepted answer would be wrong, saying that "an almost complete binary tree is also complete". They are not. A nearly complete binary tree would be complete if you deleted every leaf at the bottom of the tree.
source to share
Actually, the confusion arises from reading from different books. The explanation of the complete binary tree (i.e. every level except perhaps the last one) is completely filled, and all the nodes are as far away as possible) is contained in some books, which are called an almost complete binary tree, and the FBT explanation takes as an explanation CBT and explanations strictly BT accepts as FBT. They have no explanation for a strictly binary tree, or if possible they have no explanation for FBT.
source to share
You confuse things. Where did you get these definitions?
definitions:
a binary tree T is complete if each node is either a leaf or has exactly two child nodes.
and
a binary tree T with n levels is complete if all levels except possibly the last are completely filled, and the last level has all of its nodes on the left.
Your interpretation of the "full tree" appears to be called " full and complete tree
Source: http://courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T03a.BinaryTreeTheorems.pdf
source to share