Logo 
Search:

C Programming Articles

Submit Article
Home » Articles » C Programming » Data File StructureRSS Feeds

Program to reconstruct a binary search tree

Posted By: Boyce Fischer     Category: C Programming     Views: 7259

Program to reconstruct a binary search tree.

Code for Program to reconstruct a binary search tree in C Programming

#include <stdio.h>
#include <conio.h>
#include <alloc.h>

#define MAX 101

struct node
{
    struct node *left ;
    int data ;
    struct node *right ;
} ;

void insert ( struct node **, int ) ;
void preorder ( struct node * ) ;
void postorder ( struct node * ) ;
void inorder ( struct node * ) ;
struct node * recons ( int *, int *, int ) ;
void deltree ( struct node * ) ;

intin[MAX], pre[MAX], x ;

void main( )
{
    struct node *t, *p, *q ;
    int req, i, num ;

    t = NULL ;  /* empty tree */
clrscr( ) ; printf ( "Specify the number of items to be inserted: " ) ; while ( 1 ) { scanf ( "%d", &req ) ; if ( req >= MAX || req <= 0 ) printf ( "\nEnter number between 1 to 100.\n" ) ; elsebreak ; } for ( i = 0 ; i < req ; i++ ) { printf ( "Enter the data: " ) ; scanf ( "%d", &num ) ; insert ( &t, num ) ; } printf ( "\nIn-order Traversal:\n" ) ; x = 0 ; inorder ( t ) ; printf ( "\nPre-order Traversal:\n" ) ; x = 0 ; preorder ( t ) ; printf ( "\nPost-order Traversal:\n" ) ; x = 0 ; postorder ( t ) ; deltree ( t ) ; t = NULL ; t = recons ( in, pre, req ) ; printf ( "\n\nAfter reconstruction of the binary tree.\n" ) ; x = 0 ; printf ( "\nIn-order Traversal:\n" ) ; inorder ( t ) ; x = 0 ; printf ( "\nPre-order Traversal:\n" ) ; preorder ( t ) ; x = 0 ; printf ( "\nPost-order Traversal:\n" ) ; postorder ( t ) ; deltree ( t ) ; getch( ) ; } /* inserts a new node in a binary search tree */
void insert ( struct node **sr, int num ) { if ( *sr == NULL ) { *sr = ( struct node * ) malloc ( sizeof ( struct node ) ) ; ( *sr ) -> left = NULL ; ( *sr ) -> data = num ; ( *sr ) -> right = NULL ; return ; } else/* search the node to which new node will be attached */
{ /* if new data is less, traverse to left */
if ( num < ( *sr ) -> data ) insert ( &( ( *sr ) -> left ), num ) ; else/* else traverse to right */
insert ( &( ( *sr ) -> right ), num ) ; } } void preorder ( struct node *t ) { if ( t != NULL ) { printf ( "%d\t", pre[x++]= t -> data ) ; preorder ( t -> left ) ; preorder ( t -> right ) ; } } void postorder ( struct node *t ) { if ( t != NULL ) { postorder ( t -> left ) ; postorder ( t -> right ) ; printf ( "%d\t", t -> data ) ; } } void inorder ( struct node *t ) { if ( t != NULL ) { inorder ( t -> left ) ; printf ( "%d\t", in[x++]= t -> data ) ; inorder ( t -> right ) ; } } struct node * recons ( int *inorder, int *preorder, int noofnodes ) { struct node *temp, *left, *right ; int tempin[100], temppre[100], i, j ; if ( noofnodes == 0 ) return NULL ; temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ; temp -> data = preorder[0] ; temp -> left = NULL ; temp -> right = NULL ; if ( noofnodes == 1 ) return temp ; for ( i = 0 ; inorder[i] != preorder[0] ; ) i++ ; if ( i > 0 ) { for ( j = 0 ; j <= i ; j++ ) tempin[j] = inorder[j] ; for ( j = 0 ; j < i ; j++ ) temppre[j] = preorder[j + 1] ; } left = recons ( tempin, temppre, i ) ; temp -> left = left ; if ( i < noofnodes - 1 ) { for ( j = i ; j < noofnodes - 1 ; j++ ) { tempin[j - i] = inorder[j + 1] ; temppre[j - i] = preorder[j + 1] ; } } right = recons ( tempin, temppre, noofnodes - i - 1 ) ; temp -> right = right ; return temp ; } void deltree ( struct node *t ) { if ( t != NULL ) { deltree ( t -> left ) ; deltree ( t -> right ) ; } free ( t ) ; }
  
Share: 


Didn't find what you were looking for? Find more on Program to reconstruct a binary search tree Or get search suggestion and latest updates.

Boyce Fischer
Boyce Fischer author of Program to reconstruct a binary search tree is from Frankfurt, Germany.
 
View All Articles

 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
No Comment Found, Be the First to post comment!