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 |
| Canonical name | ExtendedBinaryTree |
| Date of creation | 2013-03-22 12:31:36 |
| Last modified on | 2013-03-22 12:31:36 |
| Owner | aoh45 (5079) |
| Last modified by | aoh45 (5079) |
| Numerical id | 8 |
| Author | aoh45 (5079) |
| Entry type | Data Structure |
| Classification | msc 05C05 |
| Related topic | BinaryTree |
| Related topic | CompleteBinaryTree |
| Related topic | ExternalPathLength |
| Related topic | WeightedPathLength |
| Related topic | MinimumWeightedPathLength |
| Defines | external node |
| Defines | internal node |