CHAP. 10] BINARY TREES 239
10.4Representing Binary Trees in Memory
LetTbe a binary tree. This section discusses two ways of representingTin memory. The first and usual
way is called thelinked representationofTand is analogous to the way linked lists are represented in memory.
The second way, which uses a single array, is called thesequential representationofT. The main requirement of
any representation ofTis that one should have direct access to the rootRofTand, given any nodeNofT, one
should have direct access to the children ofN.
Linked Representation of Binary Trees
Consider a binary treeT. Unless otherwise stated or implied,Twill be maintained in memory by means of
a linked representation which uses three parallel arrays, INFO, LEFT, and RIGHT, and a pointer variable ROOT
as follows. First of all, each nodeNofTwill correspond to a locationKsuch that:
(1) INFO[K] contains the data at the nodeN.
(2) LEFT[K] contains the location of the left child of nodeN.
(3) RIGHT[K] contains the location of the right child of nodeN.Furthermore, ROOT will contain the location of the rootRofT. If any subtree is empty, then the corresponding
pointer will contain the null value; if the treeTitself is empty, then ROOT will contain the null value.
Remark 1: Most of our examples will show a single item of information at each nodeNof a binary treeT.In
actual practice, an entire record may be stored at the nodeN. In other words, INFO may actually be a linear array
of records or a collection of parallel arrays.
Remark 2: Any invalid address may be chosen for the null pointer denoted by NULL. In actual practice, 0 or
a negative number is used for NULL.
EXAMPLE 10.2 Consider the binary treeTin Fig. 10-1(a). The linked representation ofTappears in Fig. 10-5
where we have written the linear arrays vertical rather than horizontal for notational convenience. Note that
ROOT=5 points to INFO[ 5 ]=AsinceAis the root ofT.Also, note that LEFT[ 5 ]= 10 pointsto INFO[ 10 ]=B
sinceBis the left child ofA, and RIGHT[ 5 ]=2 points to INFO[ 2 ]=CsinceCis the right child ofA. And so
on. The choice of 18 elements for the arrays is arbitrary.
Fig. 10-5Sequential Representation of Binary Trees
SupposeTis a binary tree that is complete or nearly complete. Then there is an efficient way of maintaining
Tin memory called thesequential representationofT. This representation uses only a single linear array TREE
together with a pointer variable END as follows:
(1) The rootRofTis stored in TREE[1].
(2) If a nodeNoccupies TREE[K], then its left child is stored in TREE[2*K] and its right child is stored
in TREE[2*K+1].
(3) END contains the location of the last node ofT.