1. A left pointer field,
2. An information field
3. A right pointer field
(called here the leftptr, info, and rightptr fields). This is the most common representation. The left and right pointer fields link records of the tree, just as the link and sublist fields of lists link their records. In effect, the pointer fields specify a node's left and right subtrees, just as the sublist field of a list specifies its sublist. The leftptr and rightptr fields of a node point to the record that represents, respectively, the root of the node's left and right subtree. The info field contains the information stored at the node. A variable referred to as the name of the tree points to the record representing the root of the tree, and a null pointer in the name denotes the null tree.
We can store each record of a binary tree using an array of records as shown in Figure 7.10, just as was done for the records of lists. The binary tree fred, for example, has its root stored in position 5 of the array, while the root of t is in position 2. the left successor of fred's root is stored in position 8, and its right successor in position 0. A minus one is used as the null pointer.
Figure 7.10 Linked Representation for Binary Trees with Records Stored in an Array
The definitions for the records and the array declaration are as follows.
typedef struct
{
whatever info;
int leftptr;
int rightptr;
}binarytreenode;
typedef int binarytreepointer;
# define MAX 50
typedef binarytreenode recordsarray[MAX];
recordsarray records;
Instead of using an array and array indices, we may store the records of the tree in dynamic memory and use pointers. The record declarations then become
typedef struct treenode
{
whatever info;
struct treenode *leftptr;
struct treenode *rightptr;
}binarytreenode,*binarytreepointer;
Such linked representations require storage proportional to the number of nodes of the binary tree represented, no matter what the shape of the binary tree. Contrast this with the sequential representation of binary trees. If a linked representation uses three elements per record, whereas a sequential representation uses one element per record, then for complete binary trees three times as much storage is used in a linked representation as in a sequential one. If the binary tree is not complete, then the sequential representation may require storage proportional to 2d - 1, where d is the depth of the binary tree. This could result in significant amounts of wasted space; there may not even be enough storage. Consequently, the sequential representation is more practical only when dealing with complete or nonsparse binary trees.
Using the linked representation, it is obviously possible to insert or delete records, once we know where to do so, by making changes in only a few pointer fields.
The following program illustrates the binary tree implementation with records stored in dynamic memory. It is a program that could be used to test all the functions of Section 7.3 (although they have been renamed). The names are self-explanatory. The input consists of
An integer to indicate whether the binary tree being created is null,
A sequence of data for each record
A value for the info field of a new node
The sequence is assumed to be in the order in which the records are accessed in a preorder traversal of the binary tree being input. For example, if the input corresponded to the right subtree of Figure 7.9 and the new value replacing the first terminal node were 50, then the input would be as follows. (Program output and prompts are not shown.)
Typical Input
1 indicates nonnull binary tree
3 data for the root;
11 both its subtrees are nonnull
6 data for the next record in preorder;
11 both its subtrees are nonnull1
12 data for the next record in preorder;
00 both its subtrees are null1
13 data for the next record in preorder;
00 both its subtrees are null
7 data for the next record in preorder;
00 both its subtrees are null
50 the new value
The Program
Reads the data for nodes of a binary tree, creates
the tree and prints how many terminal nodes it
has and its depth, reads the value for the new node,
replaces the first terminal node in preorder access
by the new node, and then prints all the final binary
tree's nodes, its terminal count, and its depth.
#include <stdio.h>
typedef struct treerecord
{
int info;
struct treerecord *leftptr;
struct treerecord *rightptr;
}binarytreerecord,*binarytreepointer;
#define NULL 0
binarytreepointer left(p)
/* Returns a copy of the left
pointer of the node p points to.
*/
binarytreepointer p;
{
return(p->leftptr);
}
binarytreepointer right(p)
/* Returns a copy of the right
pointer of the node p points to.
*/
binarytreepointer p;
{
return(p->rightptr);
}
binarytreepointer setnull()
/* Returns a null pointer */
{
return(NULL);
}
binarytreepointer avail()
/* Returns a pointer to storage
allocated for a new node.
*/
{
return(malloc(sizeof(binarytreerecord)));
}
setinfo(p,pvalue)
/* Copies the contents of value
into the record p points to.
*/
binarytreepointer p;
int *pvalue;
{
p->info = *pvalue;
}
setleft(p,q)
/* Copies q into the left pointer
of the record p points to.
*/
binarytreepointer p,q;
{
p->leftptr = q;
}
setright(p,q)
/* Copies q into the right pointer
of the record p points to.
*/
binarytreepointer p,q;
{
p->rightptr = q;
}
printnode(pl,ptr)
/* Prints the info field of the
record ptr points to.
*/
binarytreepointer *pl,ptr;
{
printf("\n %d",ptr->info);
}
main()
/* Reads the data for nodes of a binary tree, creates
the tree and prints how many terminal nodes it
has and its depth, reads the value for the new node,
replaces the first terminal node in preorder access
by the new node, and then prints all the final
binary tree's nodes, its terminal count, and its
depth.
*/
{
int n,value;
binarytreepointer t,setnull(),avail();
printf("\n enter binarytree 0 for null tree 1\
otherwise \n");
scanf("%d",&n);
if (n == 0)
t = setnull();
else
{
t = avail();
createtree(&t);
}
printtree(&t);
terminalcount(&t);
printf("\n The depth is %d",depth(t));
printf("\n enter value ");
scanf("%d",&value);
replacefirstterminal(&t,value);
printtree(&t);
terminalcount(&t);
printf("\n The depth is %d",depth(t));
}
createtree(ptree)
/* Read the data and create the binary tree tree. */
binarytreepointer *ptree;
{
binarytreepointer l,r,setnull(),left(),right();
if (*ptree != setnull())
{
createnode(ptree);
l = left(*ptree);
createtree(&l);
r = right(*ptree);
createtree(&r);
}
}
createnode(pptr)
/* Reads the data, and fills in the fields
of the node pointed to by ptr.
*/
binarytreepointer *pptr;
{
int leftlink,rightlink,value;
binarytreepointer setnull(),avail();
printf("\n enter info \n");
scanf("%d",&value);
setinfo(*pptr,&value);
printf("\n enter enter left & right ptrs \n");
scanf("%d %d",&leftlink,&rightlink);
if (leftlink == 0)
setleft(*pptr,setnull());
else
setleft(*pptr,avail());
if (rightlink == 0)
setright(*pptr,setnull();
else
setright(*pptr,avail());
}
#define LIMIT 50
typedef binarytreepointer whatever;
typedef struct
{
whatever stackarray[LIMIT];
int top;
}stack;
#define TRUE 1
#define FALSE 0
setstack(ps)
/* Sets the stack s to empty. */
stack *ps;
{
(*ps).top = -1;
}
empty(ps)
/* Returns true only if stack s is empty.*/
stack *ps;
{
return((*ps).top == -1);
}
push(value,ps)
/* Inserts value at the top of stack s. */
whatever value;
stack *ps;
{
if ((*ps).top == (LIMIT - 1))
overflow(ps);
else
{
(*ps).top = (*ps).top + 1;
(*ps).stackarray[(*ps).top] = value;
}
}
pop(ps,pvalue)
/* Removes the top entry of stack s
and copies its contents into value.
*/
stack *ps;
whatever *pvalue;
{
if (empty(ps))
underflow(ps);
else
{
*pvalue = (*ps).stackarray[(*ps).top];
(*ps).top = (*ps).top - 1;
}
}
whatever item(ps)
/* Returns a copy of the top entry on stack s. */
stack *ps;
{
return((*ps).stackarray[(*ps).top]);
}
last(ps)
/* Returns true only if stack s
contains no non null pointers.
*/
stack *ps;
{
int i,temp;
binarytreepointer null,setnull();
null = setnull();
temp = TRUE;
for (i=0;i<=(*ps).top;i++)
if ((*ps).stackarray[i] != null)
temp = FALSE;
return(temp);
}
overflow(ps)
/* Prints a message if the stack overflows. */
stack *ps;
{
printf("\n stack overflow ");
}
underflow(ps)
/* Prints a message if the stack underflows. */
stack *ps;
{
printf("\n stack underflow ");
}
printtree(ptree)
/* Prints the info field values of all
nodes of the binary tree tree.
*/
binarytreepointer *ptree;
{
binarytreepointer null,p,q,rightpointer;
binarytreepointer setnull(),left(),right(),item();
stack s1;
null = setnull();
setstack(&s1);
p = *ptree;
while ((p != null) || !empty(&s1))
if (p != null)
{
printnode(ptree,p);
if (left(p) != null)
{
push(p,&s1);
p = left(p);
}
else
{
push(p,&s1);
p = right(p);
}
}
else
{
do
{
pop(&s1,&q);
if (!empty(&s1))
rightpointer = right(item(&s1));
else
rightpointer = null;
}while(!empty(&s1) &&
(q == rightpointer));
if (q != rightpointer)
p = rightpointer;
}
}
terminalcount(ptree)
/* Prints the number of terminal nodes
in the binary tree tree.
*/
binarytreepointer *ptree;
{
binarytreepointer p,null,setnull(),left(),right();
stack s2;
null = setnull();
setstack(&s2);
p = *ptree;
while ((p != null) || !empty(&s2))
if (p != null)
{
updatetncount(ptree,p,&s2);
push(right(p),&s2);
p = left(p);
}
else
pop(&s2,&p);
}
updatetncount(pt,p,ps)
/* Prints the number of terminal nodes in
binary tree tree when p points to the last
node in a preorder traverse of tree which
saves right pointers on stack s.
*/
binarytreepointer *pt,p;
stack *ps;
{
binarytreepointer null,setnull(),left(),right();
static int tncount;
null = setnull();
if (p == *pt)
tncount = O;
if ((left(p) == null) && (right(p) == null))
{
tncount++;
if (last(ps))
printf("\n The number of terminal nodes\
is %d",tncount);
}
}
replacefirstterminal(ptree,value)
/* Replaces the first terminal node, encountered
in a preorder traversal of binary tree tree, by a
new node with its info field set to the contents
of value.
*/
binarytreepointer *ptree;
int value;
{
binarytreepointer null,p,q,rightpointer;
binarytreepointer setnull(),left(),right(),item();
stack s3;
null = setnull();
setstack(&s3);
p = *ptree;
while ((p != null) | | !empty(&s3))
if (p != null)
{
replacenode(ptree,p,null,&s$,value);
if (left (p) != null)
{
push(p,&s3);
p = left(p);
}
else
{
push(p,&s3);
p = right(p);
}
}
else
{
do
{
pop(&s3,&q);
if (!empty(&s3))
rightpointer = right(item(&s3));
else
rightpointer = null;
}while (!empty(&s3) &&
(q == rightpointer));
if (q != rightpointer)
p = right pointer;
}
}
replacenode(ptree,p,null,ps,value)
/* If p points to the first terminal node, encountered
in a preorder traversal of binary tree tree that
saves the path to the root on stack s, then
replaces that node by a new node whose info field is
set to the contents of value.
*/
binarytreepointer *ptree,p,null;
stack *ps;
int value;
{
binarytreepointer q,ptr,avail(),left(),right();
if ((left(p) == null) && (right(p) == null))
{
ptr = avail();
setinfo(ptr,&value);
setleft(ptr,null);
setright(ptr,null);
if (p != *ptree)
{
q = item(ps);
if (left(q) == p)
setleft(q,ptr);
else
setright(q,ptr);
}
else
*ptree = ptr;
setstack(ps);
}
}
depth(tree)
/* Returns the depth of the binary tree tree. */
binarytreepointer tree;
{
binarytreepointer setnull(),left(),right();
if (tree == setnull())
return(0);
else
return(1 + max(depth(left(tree)),
depth(right(tree))));
}
max(i,j)
/* Returns the maximum of i and j. */
int i,j;
{
if (i >= j)
return(i);
else
return(j);
}