extended binary tree
An extended binary tree is a transformation of any binary tree into a complete binary tree. This transformation consists of replacing every null subtree of the original tree with “special nodes.” The nodes from the original tree are then internal nodes, while the “special nodes” are external nodes.
For instance, consider the following binary tree.
The following tree is its extended binary tree. Empty circles represent internal nodes, and filled circles represent external nodes.
Every internal node in the extended tree has exactly two children, and every external node is a leaf. The result is a complete binary tree.
|Title||extended binary tree|
|Date of creation||2013-03-22 12:31:36|
|Last modified on||2013-03-22 12:31:36|
|Last modified by||aoh45 (5079)|
|Entry type||Data Structure|