|
|
|
|
extended binary tree
|
(Data Structure)
|
|
|
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.
|
"extended binary tree" is owned by aoh45. [ full author list (2) | owner history (1) ]
|
|
(view preamble)
Cross-references: leaf, children, represent, circles, nodes, tree, null subtree, complete binary tree, binary tree, transformation
There are 5 references to this entry.
This is version 5 of extended binary tree, born on 2002-03-07, modified 2005-05-08.
Object id is 2766, canonical name is ExtendedBinaryTree.
Accessed 9100 times total.
Classification:
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
