Heap Shape, SubTrees
Heap Shape
A tree has "heap shape" if all levels are completely filled except
perhaps for the bottom level which is filled from the left up to some point.
Trees that come from arrays as described in the previous section are heap
shaped.
The tree from the previous page has heap shape:
Sub Trees
Let n be a node of a tree. The "subtree based at n" consists of node n, its
children, the children of the children and so on, on down. A subtree is a tree
that is inside another tree. Below are three subtrees from the tree above.
Subtrees based at nodes whose data are 21, 12, and 10.
If a tree has heap shape, then so do its subtrees. The "left subtree" of
a tree is the subtree corresponding to the left child of the root. And the
"right subtree" of a tree is the subtree corresponding to the right child of the
root. The left and right subtrees of the tree above are the subtrees based
at the nodes containing 21 and 12 respectively.
Notice that the subtree based at the node containing 10 has a left subtree, but
no right subtree since it does not have a right child.