Generic trees are usually shown in a schematic form with the subtrees indicated by triangles. The firgure below shows such a representation. The details of the subtrees are hidden in the "triangles'"
Proof: Each edge connects a node to its parent. Every node except the root has a parent.
One could imagine representing a general node as a struct:
struct general_node
{
Element_Type element;
general_node * child1;
general_node * child2;
general_node * child3;
general_node * child4;
.
.
.
};
An obvious problem with this representation is that the number of
children would have to be large enough to cover all the expected cases.
This would usually mean wasting a lot of pointers.
A better representation is the ``firstchild, nextsibling'' representation.
struct general_node
{
Element_Type element;
general_node *first_child;
general_node *next_sibling;
};
The figure below shows the "firstchild, nextsibling" representation of the
rooted tree shown above.. The downwardpointing edges are the "first-child" edges. The
horizontal edges are the "next-sibling" edges.
Here's the definition of a Tree Node for binary trees. It keeps pointers
to its left and right children.
// forward declaration
template <class Etype> class Binary_Search_Tree;
template <class Etype>
class Tree_Node
{
protected:
Etype Element;
Tree_Node *Left;
Tree_Node *Right;
Tree_Node( Etype E = 0, Tree_Node *L = NULL, Tree_Node *R = NULL )
: Element( E ), Left( L ), Right( R ) { }
friend class Binary_Search_Tree<Etype>;
};
Binary Search Tree is made a friend of Tree Node.
The constructor takes an element and two pointers as arguments (with
default values for all). The constructor can be called in any of the following ways:
1. Tree_Node();
in this case Element will be 0, and both Left and Right children will
be NULL.
2. Tree_Node(elementvalue);
in this case, Element will have the value elementvalue, Left and
Right will be NULL.
3. Tree_Node(elementvalue, nodeptr1);
in this case, Element will have the value elementvalue, Left will
have the value nodeptr1 and Right will be NULL. < BR>
4. Tree_Node(elementvalue, nodeptr1, nodeptr2);
in this case, Element will have the value elementvalue, Left will
have the value nodeptr1 and Right will have the value nodeptr2.
Theorem 32.1 If a binary tree (BT) of height h has t leaves, then h >= lg t
Proof: If h >= lg t, then equivalently t <= 2 h . We prove the latter by induction on h.
Base: h = 0 (single node). Therefore, t = 1 = 20
IH: Assume true for every BT with height less than h
Let T be a BT of height h > 0 and with t leaf nodes. We consider two
possible cases:
Case 1: Root of T has only one child. Without loss of generality, let it be
the left child. Then the left subtree has height h - 1 and it has all
the leaf nodes of T. By IH, t <= 2 h - 1 < 2h
Case 2: Root has two children. Let t1 and t2 be the number of leaf nodes
and h 1 and h 2 the heights
of the two subtrees, respectively. Since the leaf nodes of T are partitioned between the two subtrees,
t = t1 + t2.
By IH, t1 <= 2h1 and t 2 <= 2 h 2 . Also, h1 <= h - 1 and h 2 <= h - 1
Therefore,
t <= 2h1 + 2h2
t <= 2h - 1 + 2h - 1
t <= 2h
Theorem 32.2 A full binary tree (FBT) of height h has 2h leaf nodes.
Proof: By induction on h
Base: A FBT of height 0 has 1 node (the root).
IH: Assume all full binary trees of height h, 0 < h <= H have 2 h leaf nodes.
For a FBT, T, of height H, create a new FBT T' by adding exactly two
children to each leaf of T . The height of T' is H + 1 and T' has twice the
nuber of leaf nodes as T , namely 2 X 2H = 2 H+1.
Theorem 32.3 The number of nodes in a full binary tree of height h is 2 h+1 - 1
Proof: The number of nodes is the sum of the number of nodes on each
level, l. Since there are 2l nodes at each level, the total number of nodes is
Theorem 32.4 If n is the number of nodes in a complete binary tree (CBT)
of height h, then 2h <= n < 2h+1
Proof: A CBT of height h has at least one and as many as 2h nodes at
level h (the final level is not empty, and may be full). In any event, level
h - 1, (h > 0) ,must be full by definition of a CBT. The number of nodes in a
FBT of height h - 1 is 2(h - 1) + 1 - 1. (By Theorem 32.3 above)
A CBT of height h has at least one more node than a FBT of height h - 1.
Therefore, the number of nodes n in a CBT is bounded by