Question

BST_Node *BST_harmonize(BST_Node *root, int semitones, double time_shift)
{
/* Let's play with notes, because we can.
*
* This function traverses the BST, and for each existing
* note, inserts a new, modified note (i.e. it will add sounds
* to an already existing song, based on the notes it already has)
*
* The new note has the followin properties:
* - The frequency is shifted by the specified number of semitones
* (A semitone is the difference between one note and the
* immediately next one in the musical scale - ot what is the
* same, the difference in pitch between a white key and the
* black key immediately next to it in a piano)
* - It plays in the same *bar* as the original note
* - But its *index* is shifted by the specified time_shift
* (this value is between 0 and 1, but you have to check
* that the final index remains between 0 and 1)
*
* Both the 'semitones' and 'time_shift' parameter can be
* positive or negative. A typical value for semitones
* could be 4 or 7, corresponding to musical 3rds or
* musical 5ths - this should produce some interesting
* harmony! but you can play with this function and try
* various things for fun.
*
* In practice, figuring out the frequency of the note
* you have to insert is easy. For instance, suppose
* you have an existing note in the BST with
*
* freq=440.0, at bar=10, index=.25
*
* Now suppose the user specified
*
* semitones=4
* time_shift=.1
*
* Then you go to the note_freq[] array, find the index
* of the entry for frequency 440.0 (let's say it's
* j), then go to note_freq[j+4] to find the frequency
* of the note you need to add.
*
* NOTE: If the value of j+semitones is < 0 or > 99
* then there is no note with the frequency you
* want. In that case you don't insert a new
* note.
*
* You then add a new note with that frequency at
* bar=10 (same bar!)
* index=.25 + .1 (the original index plus the time_shift)
*
* NOTE: If the resulting index is less than 0, or >= 1,
* then you DO NOT insert the new note.
*
* This function is crunchy - and if you don't think it
* through before you start implementing it you'll run into
* all kinds of trouble.
*
* This is the problem solving exercise for A2, so don't
* look for people on Piazza to give you answers, or tell you
* what to do, or verify you're doing the right thing.
*
* It's up to you how to solve this, and if you want an opinion,
* you can come to visit us during office hours!
*
* Expected result: The BST will have about twice as many notes
* as before, and the new notes are shifted in pitch and
* in time as specified by the parameters.
*/
  
/*** TO DO:
* Implement this function
****/
  
return NULL;

}

Answer 1

# include <stdio.h>
# include <malloc.h>

struct nodess
{
   int data;
   struct nodess *left;
   struct nodess *right;
}*rooot;

void finding(int items,struct nodess **parm,struct nodess **loc)
{
   struct nodess *pointr,*pointrsave;

   if(rooot==NULL)
   {
       *loc=NULL;
       *parm=NULL;
       return;
   }
   if(items==rooot->data)
   {
       *loc=rooot;
       *parm=NULL;
       return;
   }
   if(items<rooot->data)
       pointr=rooot->left;
   else
       pointr=rooot->right;
   pointrsave=rooot;

   while(pointr!=NULL)
   {
       if(items==pointr->data)
       { *loc=pointr;
           *parm=pointrsave;
           return;
       }
       pointrsave=pointr;
       if(items<pointr->data)
           pointr=pointr->left;
       else
           pointr=pointr->right;
   }
   *loc=NULL;
   *parm=pointrsave;
}

void insert(int items)
{ struct nodess *temp,*parmnt,*loction;
   finding(items,&parmnt,&loction);
   if(loction!=NULL)
   {
       printf("items already present");
       return;
   }

   temp=(struct nodess *)malloc(sizeof(struct nodess));
   temp->data=items;
   temp->left=NULL;
   temp->right=NULL;

   if(parmnt==NULL)
       rooot=temp;
   else
       if(items<parmnt->data)
           parmnt->left=temp;
       else
           parmnt->right=temp;
}

void case_a(struct nodess *parm,struct nodess *loc )
{
   if(parm==NULL)
       rooot=NULL;
   else
       if(loc==parm->left)
           parm->left=NULL;
       else
           parm->right=NULL;
}

void case_b(struct nodess *parm,struct nodess *loc)
{
   struct nodess *child;
   if(loc->left!=NULL)
       child=loc->left;
   else
       child=loc->right;

   if(parm==NULL )
       rooot=child;
   else
       if( loc==parm->left)
           parm->left=child;
       else
           parm->right=child;
}

void case_c(struct nodess *parm,struct nodess *loc)
{
   struct nodess *pointr,*pointrsave,*suc,*parmsuc;
   pointrsave=loc;
   pointr=loc->right;
   while(pointr->left!=NULL)
   {
       pointrsave=pointr;
       pointr=pointr->left;
   }
   suc=pointr;
   parmsuc=pointrsave;

   if(suc->left==NULL && suc->right==NULL)
       case_a(parmsuc,suc);
   else
       case_b(parmsuc,suc);

   if(parm==NULL)
       rooot=suc;
   else
       if(loc==parm->left)
           parm->left=suc;
       else
           parm->right=suc;

   suc->left=loc->left;
   suc->right=loc->right;
}
int del(int items)
{
   struct nodess *parmnt,*loction;
   if(rooot==NULL)
   {
       printf("Tree empty");
       return 0;
   }

   finding(items,&parmnt,&loction);
   if(loction==NULL)
   {
       printf("items not present in tree");
       return 0;
   }

   if(loction->left==NULL && loction->right==NULL)
       case_a(parmnt,loction);
   if(loction->left!=NULL && loction->right==NULL)
       case_b(parmnt,loction);
   if(loction->left==NULL && loction->right!=NULL)
       case_b(parmnt,loction);
   if(loction->left!=NULL && loction->right!=NULL)
       case_c(parmnt,loction);
   free(loction);
}

int preorder(struct nodess *pointr)
{
   if(rooot==NULL)
   {
       printf("Tree is empty");
       return 0;
   }
   if(pointr!=NULL)
   {
       printf("%d ",pointr->data);
       preorder(pointr->left);
       preorder(pointr->right);
   }
}

void inorder(struct nodess *pointr)
{
   if(rooot==NULL)
   {
       printf("Tree is empty");
       return;
   }
   if(pointr!=NULL)
   {
       inorder(pointr->left);
       printf("%d ",pointr->data);
       inorder(pointr->right);
   }
}

void postorder(struct nodess *pointr)
{
   if(rooot==NULL)
   {
       printf("Tree is empty");
       return;
   }
   if(pointr!=NULL)
   {
       postorder(pointr->left);
       postorder(pointr->right);
       printf("%d ",pointr->data);
   }
}

void display(struct nodess *pointr,int level)
{
   int i;
   if ( pointr!=NULL )
   {
       display(pointr->right, level+1);
       printf("\n");
       for (i = 0; i < level; i++)
           printf(" ");
       printf("%d", pointr->data);
       display(pointr->left, level+1);
   }
}
main()
{
   int choice,num;
   rooot=NULL;
   while(1)
   {
       printf("\n");
       printf("1.Insert\n");
       printf("2.Delete\n");
       printf("3.Inorder Traversal\n");
       printf("4.Preorder Traversal\n");
       printf("5.Postorder Traversal\n");
       printf("6.Display\n");
       printf("7.Quit\n");
       printf("Enter your choice : ");
       scanf("%d",&choice);

       switch(choice)
       {
       case 1:
           printf("Enter the number to be inserted : ");
           scanf("%d",&num);
           insert(num);
           break;
       case 2:
           printf("Enter the number to be deleted : ");
           scanf("%d",&num);
           del(num);
           break;
       case 3:
           inorder(rooot);
           break;
       case 4:
           preorder(rooot);
           break;
       case 5:
           postorder(rooot);
           break;
       case 6:
           display(rooot,1);
           break;
       case 7:
break;
       default:
           printf("Wrong choice\n");
       }
   }
}