Database Reference
In-Depth Information
The maximum number of nodes of a tree may be determined as follows:
•
Number of nodes at the i
th
level is 2
i
•
Maximum number of nodes = ∑ [0..k] of 2
i
Observe that this is a geometric series of first term 1 and common ration 2 (review
your discreet mathematics). The sum is therefore 2
k
- 1. So for a binary tree of height k,
Example 1:
In the example above (Figure
A1-3
), maximum nodes = 2
3
- 1 = 7.
A1.2.2 Representation of Binary Trees
Binary trees may be represented by arrays or preferably linked lists. Figure
A1-4a
illustrates a tabular representation of a binary tree while Figure
A1-4b
illustrates the
graphic representation.
Figure A1-4a.
Tabular Representation of a Binary Tree
