Write a Function to insert elements in a binary tree following:
1. Insert as Root, If Tree is NULL
2. Insert Left node & Then Right Node in Each Level
3. Once, level is full of nodes, proceed to next level.
Implementation:
Output:
Enter the number of nodes excluding root node:14
Enter data[0]:2
Enter data[1]:3
Enter data[2]:4
Enter data[3]:5
Enter data[4]:6
Enter data[5]:7
Enter data[6]:8
Enter data[7]:9
Enter data[8]:10
Enter data[9]:11
Enter data[10]:12
Enter data[11]:13
Enter data[12]:14
Enter data[13]:15
8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
1. Insert as Root, If Tree is NULL
2. Insert Left node & Then Right Node in Each Level
3. Once, level is full of nodes, proceed to next level.
Implementation:
#include<stdio.h> #include<malloc.h> /*Create a Structure with data, count of the nodes in left subtree(lc), count of the nodes in the right subtree(rc), structure pointer to the left child & right child */ struct node { int data; int lc; int rc; struct node *left , *right; }; /* Function to create a memory block & store the received data in it & return the address of the newly created memory block */ struct node* newnode ( int data ) { struct node *new = ( struct node* ) malloc ( sizeof ( struct node ) ); new -> data = data; new -> left = new -> right = NULL; new -> lc = 0; //Since, left subtree is NULL new -> rc = 0; //Since, right subtree is NULL return new; } /* Function insert to find a position to where the new data has to be inserted. */ struct node* insert ( struct node *root , int data ) { /* If the tree is empty, insert the new node & make it as root */ if ( root == NULL ) root = newnode ( data ); else { /* If the number of nodes in left subtree equals number of nodes in the right subtree, insert the data in the leftmost leaf node */ if ( root -> lc == root -> rc ) { root -> lc ++; //Update the left count root -> left = insert ( root -> left , data ); } /* If the number of nodes in the left subtree is less than the number of nodes in the right subtree, insert the data in the leftmost leaf node */ else if ( root -> lc < root -> rc ) { root -> lc ++; //Update the left count root -> left = insert ( root -> left , data ); } /* If the number of nodes in the right subtree is less than the number of nodes in the left subtree, insert the data in the rightmost leaf node */ else { root -> rc ++; //Update the right count root -> right = insert ( root -> right , data ); } } /* Return the original root which is not changed. */ return root; } /* Inorder Function to perform Inorder Traversal. a. Visit the Left Node b. Visit the Root Node c. Visit the Right Node */ void inorder ( struct node *root ) { if ( root == NULL ) return; inorder ( root -> left ); //Recur for left subtree printf ( "%d " , root -> data ); //Print the data inorder ( root -> right ); //Recur for right subtree } int main() { /* Declare the root node & Initialize it as "NULL" */ struct node *root = NULL; int i , data , N; /* Create the Root node & insert the data "1" */ root = insert ( root , 1 ); printf ( "Enter the number of nodes excluding root node:" ) ; /* Number of nodes - 1 (root node) */ scanf ( "%d" , &N ); for ( i = 0 ; i < N ; i ++ ) { printf ( "Enter data[%d]:" , i ); scanf ( "%d" , &data ); insert ( root , data ); } /* To print the in-order traversal of the tree */ inorder ( root ); return 0; }
Output:
Enter the number of nodes excluding root node:14
Enter data[0]:2
Enter data[1]:3
Enter data[2]:4
Enter data[3]:5
Enter data[4]:6
Enter data[5]:7
Enter data[6]:8
Enter data[7]:9
Enter data[8]:10
Enter data[9]:11
Enter data[10]:12
Enter data[11]:13
Enter data[12]:14
Enter data[13]:15
8 4 12 2 10 6 14 1 9 5 13 3 11 7 15