Page 215 - DCAP407_DATA_STRUCTURE

Data Structure

(i) Binary_Tree (0, Null) // Empty sub-tree
(e) EndIf
(f) node2 has right sub-tree (Give option = Y/N)?
(g) If (option = Y) // If node2 has right sub-tree

(i) Binary_Tree (2*node2+1, NEWR) // Then it is at 2*node2+1 with
next item as NEWR
(h) Else
(i) Binary_tree (0, Null) //Empty sub-tree
(i) EndIf

2. EndIf
3. Stop

Advantages of Sequential Representation of Binary Trees
1. The nodes in the binary tree can be accessed by calculating the index of
every node. It is efficient and quick.

2. The data is stored without using pointers and the information can be traced
easily with the index associated with each node.
Disadvantages of Sequential Representation of Binary trees
1. It is effective only for a full binary tree. Most of the other type of trees may
be empty in an array.

Did you know? Considering the memory requirement for a tree, linked representation uses more
memory than sequential representation for allocating memory to binary tree. Linked
representation uses extra memory to maintain pointers.

Create a binary tree for the algebraic expression ((T1* T2 + T3) + (T4 – T5) * T6) and
represent the binary tree in array representation.

11.3 Overview of Threaded Binary Trees

In a binary tree with n nodes, there exists n+1 NULL links and 2n number of total links. However, a
large value of n, n+1 NULL and 2n number of links results in more space wastage. Hence, the solution
is to change the node structure for leaf nodes so that the nodes only consist of data field. But, this
solution provides complex algorithms. Hence, the only solution is to consider the fixed node structure
and use the NULL links to simplify some of the operations. This solution provides the concept of
threaded binary trees.
In the threaded binary tree, the NULL links are replaced by pointers known as threads. These threads
point to other nodes of a tree. When the tree is traversed in inorder, and if the left child of a node p in a
binary tree is NULL, then it will be replaced with a thread. The thread will point to the node which
appears just before the node p. Similarly, if the right child of node p is NULL, then it will be replaced
with a thread. The thread will then point to a node that appears just after the node p after the inorder
traversal of a tree. Such threads are known as inorder threads.

208 LOVELY PROFESSIONAL UNIVERSITY