Page 213 - DCAP407_DATA_STRUCTURE

Data Structure

Advantages of Linked List Representation
1. The insertion and deletion operations can be done easily without moving the
other nodes.

2. The memory representation of linked list provides dynamic memory
representation. Large number of nodes can be created.
Disadvantages of Linked List Representation
1. Linked list representation does not allow direct access to the nodes in the
binary tree and requires special algorithms for accessing the nodes.

Sequential Representation
The sequential or linear representation of the tree is a static representation, in which a block of memory
for an array is allocated before storing the actual tree in the memory. The size of the tree is restricted
according to the memory allocation.
In the linear representation, nodes are stored sequentially, one level after another. The level of the nodes
starts with zero level containing the root node. In the memory allocation, root node is stored as the first
element in the array.
The following principle is practiced for allocating node of a tree in the array.
(Assume that indexing of array starts from 1)
1. The root node is present at location 1.
2. For any node with index i, 1< i ≤ n (for any value of n)
(a) PARENT (i) = [i/2]

For the node when i = 1, there is no parent
(b) LCHILD (i) = 2 * i
If 2 * i > n, then i has no left child
(c) RCHILD (i) = 2 * i + 1, then i has no right child

In the figure 11.10, the arithmetic expression is logically structured in the form of
a tree. Consider the following arithmetic expression represented in the tree
structure. Memory must be allocated for each node present in the tree. The
algebraic expression (T1 + T2) – T3 * (T4+T5) is represented in the tree as shown
in figure 11.10. While evaluating the expression, the left sub-tree is computed
first, then the right sub-tree and then finally the root.

206 LOVELY PROFESSIONAL UNIVERSITY