Page 234 - DCAP407_DATA_STRUCTURE

Unit 12: Binary Tree Traversals and Operations

In this program,
1. First, the header file stdio.h is included using include keyword.
(a) The variable node is defined as a structure. It has an integer variable data and pointers to its
left and right sub-trees, root is declared as a variable of type node. The variables p and q are
declared as pointers to node.
2. Then, the make() function is defined. It returns a pointer to the structure node and accepts an
integer variable y as a parameter. It executes the following steps:
(a) It declares newnode as pointer to the structure node and assigns memory to it.
(b) It assigns the integer y to the data variable of the newnode.
(c) It sets the right and left sub-tree pointers of the newnode to NULL.
3. Then, the left() sub-tree function is defined. It accepts as parameters r which is a pointer to the
structure node and an integer variable x. It executes the following steps:
(a) It checks if the left pointer of r is empty. If it is not empty, then it calls the make function
passing x as a parameter.
4. Then, the right() sub-tree function is defined. It accepts as parameters r which is a pointer to the
structure node and an integer variable x.
(a) It checks if the right pointer of r is empty. If it is not empty, then it calls the make function
passing x as a parameter.
5. Then, the inorder() function is defined. It accepts as parameters r which is a pointer to the
structure node.
(a) It checks if r is non-empty. If it is non-empty, it then traverses the left sub-tree, prints the data
and then traverses the right sub-tree.
6. Then, the preorder() function is defined. It accepts as parameters r which is a pointer to the
structure node.
(a) It checks if r is non-empty. If it is non-empty, it prints the data, traverses the left sub-tree, and
then traverses the right sub-tree.
7. Then, the postorder() function is defined. It accepts as parameters r which is a pointer to the
structure node.
(a) It checks if r is non-empty. If it is non-empty, it then traverses the left sub-tree, then the right
sub-tree and then prints the data.
8. In the main() function,
(a) The variables no, choice are declared as integer variables.
(b) The value for the root node is accepted and added to the tree by calling the make() function.
(c) The value of root is then assigned to variable p and q.
(d) The program execution enters a while loop in which the following steps are performed:
(i) First, it accepts another integer no.
(ii) Then, the while loop is exited if no is equal to -1.

(iii) Then, the following steps are repeatedly performed if the no. entered is not equal to
variable data of p and q is not equal to NULL.
I. First, p is assigned the value of q.
II. If the number is lesser than the data of p, q is assigned the address of the left sub-tree
else q is assigned the address of the right sub-tree

LOVELY PROFESSIONAL UNIVERSITY 227