Page 212 - DCAP407_DATA_STRUCTURE

Unit 11: Introduction to Binary Trees

The linked form of representation is an easier way of identifying, storing and retrieving information in
the memory. It represents the logical structure of the data involved.

If there are n nodes in the binary tree, then the number of null links in the linked
representation is n+1.

Let us now discuss the algorithm for implementing the linked representation of a binary tree.
Algorithm Binary_Tree (node1, info)
Input – info is the content of the node with pointer node1
Output – A binary tree with two sub-trees of the node1
Data Structure - Linked list structure of binary tree
Steps

1. If (node1 ≠ Null) then// If tree is not empty
(a) node1.data = info // Store data of node at node1
(b) node1 has left sub-tree (Give option = Y/N)?
(c) If (option =Y) then
(i) llink = GETNODE(node)// Allocate memory to the left child
(ii) node1.LC = llink // Assign it to left link

(iii) Binary_Tree (llink, NEWL)// Build left sub-tree with next information as NEWL
(d) Else
(i) llink = Null
(ii) node1.LC = Null // Assign for empty left sub-tree
(iii) Binary_Tree (llink, Null)// Empty sub-tree
(e) EndIf
(f) Node1 has right sub-tree (Give option = Y/N)?
(g) If (option = Y) then

(i) rlink = GETNODE(node1) // Allocate memory to right child
(ii) node1.RC = rlink // Assign it to right link
(iii) Binary_Tree (rlink, NEWR) // build right sub-tree with next item as NEWR
(h) Else
(i) rlink = Null

(ii) node1.RC = Null // Assign for an empty right sub-tree
(iii) Binary_Tree (rlink, Null)
(i) EndIf
2. EndIf
3. Stop

LOVELY PROFESSIONAL UNIVERSITY 205