extended binary tree

An extended binary treeMathworldPlanetmath is a transformation of any binary treeMathworldPlanetmath into a complete binary treeMathworldPlanetmathPlanetmath. This transformation consists of replacing every null subtree of the original tree with “special nodes.” The nodes from the original tree are then internal nodesPlanetmathPlanetmath, 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