Buddy Book Program

////////////////////////////////////////////////////////////////////////////////
///  
///  \file buddy_book.c
///  \brief This is a database manager for a basic social networking site,
///         BuddyBook.com. It was built to store an indifinite number of people.
///         It stores basic information on each user such as their ID, first and
///         last name, age, and a list of their buddies.
///  
///  <br>Author(s): Nicholas Guthrie
///  <br>Created: 2011-03-24
///  <br>Email: nickguthrie@knights.ucf.edu
///  <br>Web: http://nickguthrie.com
///  <br>Title: Buddy Book
///  <br>Course: COP3502C Compute Science I
///  <br> Class #: 16173
///  <br>Section #: 0001
///  
///  THIS SOFTWARE IS PROVIDED BY THE NICHOLAS GUTHRIE''AS IS'' AND ANY EXPRESS
///  OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
///  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
///  NO EVENT SHALL UCF BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
///  EXEMPLARY,OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
///  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
///  OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
///  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
///  OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
///  ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
///  
////////////////////////////////////////////////////////////////////////////////

///////////////////////////
//   Library Includes    //
///////////////////////////
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


///////////////////////////
// #defines & Constants  //
///////////////////////////
#define _CRT_SECURE_NO_WARNINGS


///////////////////////////
//  Struct Declarations  //
///////////////////////////
////////////////////////////////////////////////////////////////////////////////
/// 
/// \brief This is a member of the BSTnode so that every user can have a linked-
///        list of their buddies
/// 
////////////////////////////////////////////////////////////////////////////////
typedef struct buddyList {
     int buddy;
     struct buddyList *next;
} buddies;

////////////////////////////////////////////////////////////////////////////////
/// 
/// \brief This stores each user's information.
/// 
////////////////////////////////////////////////////////////////////////////////
typedef struct tree_node {
     int ID;			///< (+) used to sort accounts
     char firstName&#91;21&#93;;	///< first name of user
     char lastName&#91;21&#93;;		///< last name of user
     int age;			///< age of user
     buddies *myBuddies;	///< linked list of buddies
     int numBuddies;		///< current # of buddies
     struct tree_node *left;	///< buddy to the left branch
     struct tree_node *right;	///< buddy to the right branch
} BSTnode;


///////////////////////////
// Function Declarations //
///////////////////////////

//////////////////////
//  BST Operations  //
//////////////////////
/// Initializations
struct tree_node * CreateTreeNode();
/// Search Functions
struct tree_node* FindName(struct tree_node *current_ptr, char FirstName&#91;21&#93;,
			   char LastName&#91;21&#93;);
struct tree_node * FindID(struct tree_node *current_ptr, int ID);
/// Operations
struct tree_node * InsertTreeNode(struct tree_node *root,
				  struct tree_node *element);
struct tree_node* DeleteTreeNode(struct tree_node* root, int value);
/// Determine Tree Status
int isLeaf(struct tree_node *node);
int hasOnlyLeftChild(struct tree_node *node);
int hasOnlyRightChild(struct tree_node *node);

struct tree_node* parent(struct tree_node *root, struct tree_node *node);
struct tree_node* maxVal(struct tree_node *root);
struct tree_node* minVal(struct tree_node *root);

//////////////////////
//    Buddy List    //
//////////////////////
struct buddyList * AddBuddy(struct tree_node * person, int ID);
struct buddyList * UnBuddy(struct tree_node * person, int ID);
struct buddyList * Delete(struct buddyList *front, int num);
int LLFind(struct buddyList * AllBuddies, int budy );

//////////////////////
// Print Functions  //
//////////////////////
void PrintBuddies(FILE * output,
		  struct tree_node * AllPeople, struct tree_node * person);
void PrintFound(FILE * output, struct tree_node * tNode);
void PrintPerson(FILE * output, struct tree_node * tNode);
void PrintTree(FILE * output, BSTnode *AllPeople);



///////////////////////////
//        Main           //
///////////////////////////
int main(){
     /////////////////////
     //   Variables     //
     /////////////////////
     FILE *input, *output;	// i/o variables
     struct tree_node *AllPeople=NULL; // tree of all people
     int num_commands;		// # of commands in file
     char command&#91;20&#93;;		// command to execute
     int i;			// navigation variables

     char tFirstName&#91;21&#93;, tLastName&#91;21&#93;, dFirstName&#91;21&#93;, dLastName&#91;21&#93;;
     int tID;
     struct tree_node *tNode, *tBuddy;

     
     /////////////////////
     // Initializations //
     /////////////////////
     //Input/Output
     input = fopen("buddyBook.in", "r");
     output = fopen("buddyBook.out", "w");
     if(input == NULL || output == NULL)
     {
	  fprintf(output, "File not Found, Press ENTER to exit\n");
	  getchar(); // pause for user input
	  return 0;
     }
     //BSTnode
     AllPeople = NULL;

     fscanf(input, "%d", &num_commands);
     
     for(i = 0; i < num_commands; i++){
	  fscanf(input, "%s", command);
	  if(strcmp("ADD", command)==0){
	       struct tree_node *NewNode = CreateTreeNode();
	       fscanf(input, "%d%s%s%d", &NewNode->ID, NewNode->firstName,
		      NewNode->lastName, &NewNode->age);

	       /////////////////
	       //  Age Check  //
	       /////////////////
	       if(NewNode->age < 13)
	       {
		    fprintf(output, "%s %s rejected - You must be 13 or over to"
			    " create a profile.\n", NewNode->firstName,
			    NewNode->lastName);
		    free(NewNode);
	       }
	       else
	       {
		    if(FindName(AllPeople, NewNode->firstName,
				NewNode->lastName)!=NULL)
		    {
			 fprintf(output, "%s %s is already a member of Buddy"
				 " Book.\n", NewNode->firstName,
				 NewNode->lastName);
		    }
		    else{
			 fprintf(output, "Added %s %s, age %d\n",
				 NewNode->firstName,
				 NewNode->lastName, NewNode->age);
			 AllPeople = InsertTreeNode(AllPeople, NewNode);
		    }
	       }
	  }
	  else if(strcmp("FINDNAME", command)==0)
	  {
	       fscanf(input, "%s%s", tFirstName, tLastName);
	       tNode = FindName(AllPeople, tFirstName, tLastName);
	       if(tNode == NULL){
		    fprintf(output, "%s %s not found.\n", tFirstName, tLastName);
	       }
	       else
	       {
		    PrintFound(output, tNode);		    
	       }

	  }
	  else if(strcmp("FINDID", command)==0)
	  {
	       fscanf(input, "%d", &tID);
	       tNode = FindID(AllPeople, tID);
	       if(tNode == NULL){
		    fprintf(output, "ID %d not found.\n", tID);
	       }
	       else
	       {
		    PrintFound(output, tNode);		    
	       }
	  }
	  else if(strcmp("BUDDY", command)==0)
	  {
	       // store first name set in tNode
	       fscanf(input, "%s%s", tFirstName, tLastName);
	       tNode = FindName(AllPeople, tFirstName, tLastName);

	       // store second name set in tBuddy
	       fscanf(input, "%s%s", dFirstName, dLastName);
	       tBuddy = FindName(AllPeople, dFirstName, dLastName);

	       if(tNode == NULL || tBuddy == NULL)
	       {
		    fprintf(output, "Cannot Perform BUDDY Command:\n");
		    if(tNode == NULL)
			 fprintf(output, "   %s %s - This profile does not exist.\n",
				 tFirstName, tLastName);
		    if(tBuddy == NULL){
			 fprintf(output, "   %s %s - This profile does not exist.\n",
				 dFirstName, dLastName);
		    }
	       }
	       else if(LLFind(tNode->myBuddies, tBuddy->ID) ||
		       LLFind(tBuddy->myBuddies, tNode->ID))
	       {
		    fprintf(output, "Cannot Perform BUDDY Command:\n"
			    "   %s %s and %s %s are already Buddies.\n",
			    tFirstName, tLastName, dFirstName, dLastName);
	       }

	       else
	       {
		    // store the buddies
		    tNode->myBuddies = AddBuddy(tNode, tBuddy->ID);
		    tBuddy->myBuddies = AddBuddy(tBuddy, tNode->ID);
		    fprintf(output, "%s %s and %s %s are now Buddies.\n", tFirstName,
			    tLastName, dFirstName, dLastName);
	       }	       
	  }
	  else if(strcmp("UNBUDDY", command)==0)
	  {
	       fscanf(input, "%s%s", tFirstName, tLastName);
	       tNode = FindName(AllPeople, tFirstName, tLastName);
	       fscanf(input, "%s%s", dFirstName, dLastName);
	       tBuddy = FindName(AllPeople, dFirstName, dLastName);



	       if(tNode == NULL || tBuddy == NULL)
	       {
		    fprintf(output, "Cannot Perform UNBUDDY Command:\n");
		    if(tNode == NULL)
			 fprintf(output, "   %s %s - This profile does not exist.\n",
				 tFirstName, tLastName);
		    if(tBuddy == NULL){
			 fprintf(output, "   %s %s - This profile does not exist.\n",
				 dFirstName, dLastName);
		    }
	       }


	       else if(tNode->myBuddies == NULL)
	       {
		    fprintf(output, "Cannot Perform UNBUDDY Command:\n"
			    "   %s %s and %s %s are not currently Buddies.\n",
			    tFirstName, tLastName, dFirstName, dLastName);
	       }
	       else
	       {
		    tBuddy->myBuddies = UnBuddy(tBuddy, tNode->ID);
		    tNode->myBuddies = UnBuddy(tNode, tBuddy->ID);

		    fprintf(output, "%s %s and %s %s are no longer Buddies.\n",
			    tFirstName, tLastName, dFirstName,
			    dLastName);
	       }
	  }
	  else if(strcmp("PRINTTREE", command)==0)
	  {
	       if(AllPeople != NULL){
		    fprintf(output, "Members of Buddy Book:\n");
		    PrintTree(output, AllPeople);
	       }
	       else{
		    fprintf(output, "Cannot Perform PRINTTREE Command:\n"
			    "   There are currently no members of Buddy Book.\n");
	       }
	  }
	  else if(strcmp("PRINTBUDDIES", command)==0)
	  {
	       fscanf(input, "%s%s", tFirstName, tLastName);
	       tBuddy = FindName(AllPeople, tFirstName, tLastName);
	       if(tBuddy == NULL){
		    fprintf(output, "Cannot Perform PRINTBUDDIES Command:\n"
			    "   %s %s - This profile does not exist.\n",
			    tFirstName, tLastName);
	       }
	       else{
		    PrintBuddies(output, AllPeople, tBuddy);
	       }

	  }
	  else if(strcmp("DELETE", command)==0)
	  {
	       fscanf(input, "%s%s", tFirstName, tLastName);
	       tBuddy = FindName(AllPeople, tFirstName, tLastName);

	       if(tBuddy == NULL)
	       {
		    fprintf(output, "Cannot Perform DELETE Command:\n"
			    "   %s %s - This profile does not exist.\n",
			    tFirstName, tLastName);
	       }
	       else
	       {
		    while(tBuddy->myBuddies !=NULL){
			 //removes friend before deleting person.
			 FindID(AllPeople, tBuddy->myBuddies->buddy)->numBuddies--;
			 

			 tBuddy->myBuddies = Delete(tBuddy->myBuddies,
						    tBuddy->myBuddies->buddy);
		    }
		    fprintf(output, "Deleted %s %s.\n", tBuddy->firstName,
			    tBuddy->lastName);
		    AllPeople = DeleteTreeNode(AllPeople, tBuddy->ID);
	       }
	  }
     }
}//END main


//////////////////////////////
// Function Implamentations //
//////////////////////////////
struct tree_node* CreateTreeNode(){
     struct tree_node * temp;
     temp = (struct tree_node*)malloc(sizeof(struct tree_node));
     temp->left = NULL;
     temp->right = NULL;
}


////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Finds a person based on name then prints:
///         <first name> <last Name> age <age> <# of buddies>
///         IF no person exists print error msg.
///  \param current_ptr valid node of a person
///  \param FirstName first name of the person to find
///  \param LastName last name of the person to find
///  \return tree_node of the person IF found
///          NULL IF the person is not found
///  
////////////////////////////////////////////////////////////////////////////////
struct tree_node* FindName(struct tree_node *current_ptr, char FirstName[21],
			   char LastName[21]) {

     int ln_test, fn_test;
     // Check if  there are nodes in the tree.

     if (current_ptr != NULL) {
	  ln_test = strcmp(current_ptr->lastName, LastName);
	  // Found the value at the root.
	  // Search to the left.
	  if (ln_test > 0)
	       return (struct tree_node *)FindName(current_ptr->left, FirstName,
						   LastName);
	  // Or...search to the right.
	  else if(ln_test < 0)
	       return (struct tree_node *)FindName(current_ptr->right, FirstName,
						   LastName);
	  else if(ln_test == 0)
	  {
	       fn_test = strcmp(current_ptr->firstName, FirstName);
	       if(fn_test > 0)
		    return (struct tree_node *)FindName(current_ptr->left,
							FirstName, LastName);
	       else if(fn_test < 0)
		    return (struct tree_node *)FindName(current_ptr->right,
							FirstName, LastName);
	       else
		    return current_ptr;
	  }
     }
     else
	  return NULL; // No node found.
}

////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Finds a person based on ID then prints
///         <first name> <last Name> age <age> <# of buddies>
///         if no person exists print error msg.
///  \param curent_ptr pointer to a valid tree node
///  \param ID Id of a person
///  \return tree node of a person IF found
///          NULL IF no person found
///
////////////////////////////////////////////////////////////////////////////////
struct tree_node* FindID(struct tree_node *current_ptr, int ID)
{
     // Check if there are nodes in the tree.
     if (current_ptr != NULL) {
	  // Found the value at the root.
	  if(current_ptr->ID == ID)
	       return current_ptr;
	  // Search to the left.
	  if (current_ptr->ID > ID)
	       return (struct tree_node *)FindID(current_ptr->left, ID);
	  // Or...search to the right.
	  else
	       return (struct tree_node *)FindID(current_ptr->right, ID);
     }
     else
	  return NULL; // No node found.       
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief Makes two people buddies.
///         Prints error IF the person is not in the dB or IF already buddies.
///  \param current_ptr pointer to a valid tree node
///  \param ID of the buddy to add
///  \return A pointer to the front of the list.
///
////////////////////////////////////////////////////////////////////////////////
struct buddyList *AddBuddy(struct tree_node *person,int ID){
     struct buddyList *temp;
     struct buddyList *iter;
     struct buddyList *savelink;
     struct buddyList * front = person->myBuddies;
     person->numBuddies++;



     // Create the new node.
     temp = (struct buddyList*)malloc(sizeof(struct buddyList));
     temp->buddy = ID;
     temp->next = NULL;

     // insert into an empty list
     if (front == NULL){
	  return temp;
     }


     if (ID < front->buddy) {
	  temp->next = front;
	  return temp;
     }

     // Start iter at the front of the linked list.
     iter = front;

     // Use front to iterate to the right spot to insert temp.
     while (iter->next != NULL && iter->next->buddy < ID)
	  iter = iter->next;

     // Save the node to patch to.
     savelink = iter->next;

     // Insert temp.
     iter->next = temp;
     temp->next = savelink;
  
     return front;
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief Removes two buddies from each other's buddy lists.
///         IF no person exists print error msg.
///  \return A pointer to the front of the buddy list.
///
////////////////////////////////////////////////////////////////////////////////
struct buddyList *UnBuddy(struct tree_node * person, int ID){
     struct buddyList * front = person->myBuddies;
     struct buddyList *temp, *del;
     temp = front;
     

     // Only need to delete if the list is not null.
     if (temp != NULL) {
	  person->numBuddies--;
	  // Take care of the case where first node needs to be deleted.
	  if (temp->buddy == ID) {
	       del = temp -> next;
	       free(temp);
	       return del;
	  }
	  // Otherwise, loop until you find the node to delete and do so.
	  while (temp->next != NULL) {
	       if (temp ->next->buddy == ID) {
		    del = temp -> next;
		    temp->next = temp ->next->next;
		    free(del);
		    return front;
	       }
	       temp = temp -> next;
	  }
     }
     return NULL;
}


////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Deletes the user from the database removes from all buddies
///  \param front front of the buddyList.
///  \param num ID of the person you want to delete
///  \return A pointer to the front of the buddy list.
///  
////////////////////////////////////////////////////////////////////////////////
struct buddyList * Delete(struct buddyList *front, int num)
{
     struct buddyList *temp, *del;
     temp = front;

     // only need to delete if the list != null.
     if (temp != NULL) {
	  // take care of the case where first node needs to be deleted.
	  if (temp->buddy == num)
	  {
	       del = temp->next;
	       free(temp);
	       return del;
	  }
	  // otherwise, loop until you find the node to delete, then delete.
	  while (temp->next != NULL)
	  {
	       if (temp->next->buddy == num)
	       {
		    del = temp -> next;
		    temp->next = temp->next->next;
		    free(del);   
		    return front;
	       }
	       temp = temp -> next;
	  }    
     }
     return front;
}


////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Prints the member's name, the # of buddies, and an alphabetical list
///         of buddies
///  \param output Output file to write text to.
///  \param AllPeople Root tree node of all people.
///  \param person Person to print the  buddies of.
///  \return void
///  
////////////////////////////////////////////////////////////////////////////////
void PrintBuddies(FILE *output, struct tree_node * AllPeople,
		  struct tree_node * person)
{
     if(person->myBuddies != NULL && person->numBuddies != 0)
     {
	  char * howmany;
	  if(person->numBuddies == 1)
	       howmany = "Buddy";
	  else
	       howmany = "Buddies";

	  fprintf(output, "%s %s has %d %s:\n", person->firstName,
		  person->lastName, person->numBuddies, howmany);

	  struct buddyList * helper_ptr = person->myBuddies;
	  struct tree_node * tNode = person;

	  while(helper_ptr != NULL){
	       tNode = FindID(AllPeople, helper_ptr->buddy);
	       if(tNode != NULL){
		    fprintf(output, "   %s %s\n", tNode->firstName,
			    tNode->lastName);
	       }
	       helper_ptr = helper_ptr->next;
	  }
     }

     else
     {
	  fprintf(output, "%s %s has no Buddies.\n", person->firstName,
		  person->lastName);
     }
}


////////////////////////////////////////////////////////////////////////////////
///
///  \brief Prints all members in alphabetical order (last, first name) + some
///         basic info for each member
///  \param output Output file to print to.
///  \param AllPeople valid tree node of root person to print tree of
///  \return void
///
////////////////////////////////////////////////////////////////////////////////
void PrintTree(FILE * output, BSTnode *AllPeople){
     BSTnode *helper_ptr = AllPeople;
     if(helper_ptr != NULL){
	  if(helper_ptr->right != NULL)
	  {
	       PrintTree(output, helper_ptr->left);	       
	  }
	  fprintf(output, "   ");
	  PrintPerson(output, helper_ptr);
	  if(helper_ptr->left != NULL){
	       PrintTree(output, helper_ptr->right);
	  }
     }
}//END PrintTree


////////////////////////////////////////////////////////////////////////////////
///  
///  \brief Adds the node to the list
///  \param root Root node of the tree_node.
///
///
////////////////////////////////////////////////////////////////////////////////
struct tree_node * InsertTreeNode(struct tree_node *root,
				  struct tree_node *element){
     if (root == NULL) 
	  return element;
     else {
	  // element should be inserted to the right.
	  if (element->ID > root->ID) {

	       // There is a right subtree to insert the node.
	       if (root->right != NULL)
		    root->right = InsertTreeNode(root->right, element);

	       // Place the node directly to the right of root.
	       else
		    root->right = element;
	  }

	  // element should be inserted to the left.
	  else {

	       // There is a left subtree to insert the node.
	       if (root->left != NULL)
		    root->left = InsertTreeNode(root->left, element);

	       // Place the node directly to the left of root.
	       else
		    root->left = element;
	  } 

	  // Return the root pointer of the updated tree.
	  return root;
     }
}


////////////////////////////////////////////////////////////////////////////////
/// 
/// \brief Prints "Found:"
/// \return void
///
////////////////////////////////////////////////////////////////////////////////
void PrintFound(FILE * output, struct tree_node * tNode)
{
     fprintf(output, "Found:  ");
     PrintPerson(output, tNode);
}


////////////////////////////////////////////////////////////////////////////////
///
/// \brief Prints a person and all their buddies to file.
/// \return void
///
////////////////////////////////////////////////////////////////////////////////
void PrintPerson(FILE * output, struct tree_node * tNode)
{
     char * howmany;
     if(tNode->numBuddies ==1)
	  howmany = "Buddy";
     else
	  howmany = "Buddies";
     
     fprintf(output, "%s %s, age %d, %d %s\n", tNode->firstName,
	     tNode->lastName, tNode->age, tNode->numBuddies,
	     howmany);
}

////////////////////////////////////////////////////////////////////////////////
///
/// \brief Deletes a node from a tree.
/// \param root Root of the node to delete the person from.
/// \param value ID of the person to delete
/// \return TreeNode root of the deleted tree.
///
////////////////////////////////////////////////////////////////////////////////
struct tree_node* DeleteTreeNode(struct tree_node* root, int value)
{
     struct tree_node *delnode, *new_del_node, *save_node;
     struct tree_node *par;
     int save_val;

     delnode = FindID(root, value); // Get a pointer to the node to delete.
     par = parent(root, delnode); // Get the parent of this node.
  
     // Take care of the case where the node to delete is a leaf node.
     if (isLeaf(delnode))
     {
	  // Deleting the only node in the tree.
	  if (par == NULL)
	  { 
	       free(root); // free the memory for the node.
	       return NULL;
	  }

	  // Deletes the node if it's a left child.
	  if (value < par->ID)
	  {
	       free(par->left); // Free the memory for the node.
	       par->left = NULL;
	  }

	  // Deletes the node if it's a right child.
	  else
	  {
	       free(par->right); // Free the memory for the node.
	       par->right = NULL;    
	  }
	  return root; // Return the root of the new tree.
     }

     // Take care of the case where the node to be deleted only has a left child
     if (hasOnlyLeftChild(delnode)) {
  
	  // Deleting the root node of the tree.
	  if (par == NULL) {
	       save_node = delnode->left;
	       free(delnode); // Free the node to delete.
	       return save_node; // Return the new root node of the resulting tree.
	  }

	  // Deletes the node if it's a left child.
	  if (value < par->ID) {
	       save_node = par->left; // Save the node to delete.
	       par->left = par->left->left; // Readjust the parent pointer.
	       free(save_node); // Free the memory for the deleted node.
	  }

	  // Deletes the node if it's a right child.
	  else {
	       save_node = par->right; // Save the node to delete.
	       par->right = par->right->left; // Readjust the parent pointer.
	       free(save_node); // Free the memory for the deleted node.
	  }

	  return root; // Return the root of the tree after the deletion.
     }

     // Takes care of the case where the deleted node only has a right child.
     if (hasOnlyRightChild(delnode)) {
  
	  // Node to delete is the root node.
	  if (par == NULL) {
	       save_node = delnode->right;
	       free(delnode);
	       return save_node;
	  }

	  // Delete's the node if it is a left child.
	  if (value < par->ID) {
	       save_node = par->left;
	       par->left = par->left->right;
	       free(save_node);
	  }

	  // Delete's the node if it is a right child.
	  else {
	       save_node = par->right;
	       par->right = par->right->right;
	       free(save_node);
	  }
	  return root;
     }
 
     // Find the new physical node to delete.
     new_del_node = minVal(delnode->right); 
     save_val = new_del_node->ID;

     DeleteTreeNode(root, save_val);  // Now, delete the proper value.

     // Restore the ID to the original node to be deleted.
     delnode->ID = save_val; 

     return root;
}



////////////////////////////////////////////////////////////////////////////////
///
/// \bfief finds the parent of the tree.
/// \param root tree to find root of
/// \param node Node to check if is root
/// \return the parent of the node pointed to by node in the tree rooted at root
///         IF the node is the root, or the node doesn't exist, NULL is returned
///
////////////////////////////////////////////////////////////////////////////////
struct tree_node* parent(struct tree_node *root, struct tree_node *node) {

     // Take care of NULL cases.
     if (root == NULL || root == node)
	  return NULL;

     // The root is the direct parent of node.
     if (root->left == node || root->right == node)
	  return root;

     // Look for node's parent in the left side of the tree.
     if (node->ID < root->ID)
	  return parent(root->left, node);

     // Look for node's parent in the right side of the tree.
     else if (node->ID > root->ID)
	  return parent(root->right, node);

     return NULL; // Catch any other extraneous cases.

}


////////////////////////////////////////////////////////////////////////////////
///
/// \brief Checks if a node is a leaf.
/// \param node The node in the tree to check if it is a leaf.
/// \return 1 if the node is a leaf node,
///         0 otherwise
/// 
////////////////////////////////////////////////////////////////////////////////
int isLeaf(struct tree_node *node)
{
     return (node->left == NULL && node->right == NULL);
}

////////////////////////////////////////////////////////////////////////////////
///
/// \brief Determines if a node has only left children.
/// \param node The node to determine if it has only left children.
/// \return 1 IF node has a left child && no right children
////////////////////////////////////////////////////////////////////////////////
int hasOnlyLeftChild(struct tree_node *node)
{
     return (node->left!= NULL && node->right == NULL);
}

////////////////////////////////////////////////////////////////////////////////
///
/// \brief Determines if a node has only right children.
/// \param node The node to determine if it has only right children.
/// \return 1 IF node has a right child && no left children
/// 
////////////////////////////////////////////////////////////////////////////////
int hasOnlyRightChild(struct tree_node *node)
{
     return (node->left== NULL && node->right != NULL);
}

////////////////////////////////////////////////////////////////////////////////
///
/// \brief Finds the minimum value in a tree
/// \param root The root of the tree to search.
/// \return A TreeNode pointer to the minimum value node.
///
////////////////////////////////////////////////////////////////////////////////
struct tree_node* minVal(struct tree_node *root)
{
     // Root stores the minimal value.
     if (root->left == NULL)
	  return root;

     // The left subtree of the root stores the minimal value.
     else
	  return minVal(root->left);
}

////////////////////////////////////////////////////////////////////////////////
///
/// \brief Finds the maximum value in a tree.
/// \param root The root of the tree to find the maximum value of.
/// \return A pointer to the node storing the maximum value in the tree with the
///         root, root.  Will not work if called with an empty tree.
///
////////////////////////////////////////////////////////////////////////////////
struct tree_node* maxVal(struct tree_node *root)
{
     // root stores the maximal value.
     if (root->right == NULL)
	  return root;

     // the right subtree of the root stores the maximal value.
     else
	  return maxVal(root->right);
}

////////////////////////////////////////////////////////////////////////////////
///
/// \brief Finds a buddy in a linked list of buddies.
/// \param AllBuddies A pointer to Allbuddies.
/// \param buddy The buddy to find in the list of buddies.
///
////////////////////////////////////////////////////////////////////////////////
int LLFind(struct buddyList * AllBuddies, int buddy)
{
     struct buddyList * helperBuddy = AllBuddies;
     while(helperBuddy != NULL)
     {
	  if(helperBuddy->buddy == buddy)
	       return 1;
	  helperBuddy = helperBuddy->next;
     }
     return 0;
}

Leave a Reply

You must be logged in to post a comment.