extended binary treeExtendedBinaryTree2002-03-07 12:42:472005-05-08 07:49:20Data Structureexternal nodeinternal node\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}An \emph{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 \emph{internal nodes}, while the ``special nodes'' are \emph{external nodes}.
For instance, consider the following binary tree.
\begin{center}
\includegraphics{tree1}
\end{center}
The following tree is its extended binary tree. Empty circles represent internal nodes, and filled circles represent external nodes.
\begin{center}
\includegraphics{tree2}
\end{center}
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.