Page 235 - DCAP407_DATA_STRUCTURE

Data Structure

(iv) If no is less than data of variable p the function left() is called passing p and no as the
parameters, else the function right () is called.
(e) A while loop is used to obtain the choice of traversal.

(i) If 1 is entered, inorder traversal is selected and the inorder function is executed.
(ii) If 2 is entered, preorder traversal is selected and preorder function is executed.
(iii) If 3 is selected, preorder traversal is selected and postorder function is executed.
(iv) If 4 is entered, the while loop is exited.
(v) If wrong digit is entered, an error message is printed on the screen.
(f) The getch() prompts the user to enter a key to exit the program.

Consider the algebraic expression (A +(B-C)) / ((D-E) * (F+G-H))
Construct a binary tree with the above expression and traverse the tree in inorder,
preorder, and postorder manner by applying the tree traversal algorithms.

12.5 Binary Tree Operations
The binary tree operations are required to perform certain functions on a binary tree. The binary tree
can be structured logically and implemented using the binary tree operations. The major operations on
a binary tree are:
1. Insertion
2. Deletion
3. Searching
12.5.1 Insertion

The insertion operation deals with inserting a new node at any position in the binary tree. Before
inserting the node, it is important to identify the location of insertion. Hence, searching operation must
be performed before performing insertion operation. Search and insertion operation are inter-related.
If an element T1 is given, and the task is to search and insert the element, then the operation is
performed as follows:
1. If element T1 < element of root node, then select left branch node and place the element T1 at the
left side of the node.
2. If element T1 > element of root node then place the element in the right branch of root node.
This process continues until all the nodes are visited in the tree.
Insertion is a two-step process. The first step deals with searching the node in a binary tree and the next
step deals with inserting the node and providing a link for the new node. Insertion operation can be
done on a sequential representation as well as linked representation of binary tree. Let us now discuss
the insertion operation on sequential representation of binary tree.
In the insertion operation, the key element is identified and a new node is inserted with its data
element.
The algorithm for insertion operation is as follows:
Input – KEY is the node in the binary tree to identify the location of inserting a new node.
Output – Newly inserted node with data as INFO.
Data structure – Array A stores binary tree.

228 LOVELY PROFESSIONAL UNIVERSITY