Clever Geek Handbook

Definition of a complete binary tree

I came across two resources and they seem to talk about the main definition in two ways.

Source 1 (and one of my professors) says:

All sheets are at the same level, and all non-sheet nodes have two child nodes.

Source 2 (and 95% of the internet) says:

A complete binary tree (sometimes called a regular or flat binary tree) is a tree in which each node in the tree has 0 or 2 children.

Now after Source 2

,enter image description here

becomes a binary tree, but doesn't match Source 1

because the leaves are not flush.

Thus, they usually consider trees such as

enter image description here

how Full Binary Tree

.

I may sound stupid, but I'm confused as to what to believe. Any help is appreciated. Thanks in advance.

+3


source to share


2 answers


There are three basic concepts: (1) Complete Binary Tree (2) Complete Binary Tree and (3) Perfect Binary Tree. As you said, a complete binary tree is a tree in which all nodes are of degree 2 or 0. However, a complete binary tree is one in which all but possible levels are filled, the last level is full. In addition, an ideal binary tree is a complete binary tree such that all levels are at the same depth. See wikipedia page for details



My intuition for the term complete is that for a fixed number of nodes, a complete binary tree is created by filling each level completely , except perhaps the last one, since the number of nodes cannot be 2 ^ n - 1.

+4


source


I think the problem is, what is the purpose of the definition? Usually the reason for defining a complete binary tree in the way that appears on Wikipedia is to present and prove the complete double tree theorem :

The total number of nodes N in a complete binary tree with i internal nodes is 2 i + 1.



(There are several equivalent formulations of this theorem in terms of the number of interior nodes, the number of leaf nodes, and the total number of nodes.) The proof of this theorem does not require all leaf nodes to be of the same level.

What one of your professors describes what I would call a perfect binary tree or, equivalently, a complete complete binary tree.

+3


source






More articles:


All Articles