Language is C. Please read carefully and write the functions below. Thank you.

#include "imgUtils.c"

/** * This is the structure we are going to use to store each individual node of * the BST. Remember that each Quad corresponds to a rectangular area on the * image: * * (tx,ty) w * x------------------------- * | | * | | * | | * | | * h | Quad | * | key = tx+(ty*sx) | * | | * | | * | | * | | * -------------------------x * (tx + w, ty + h) * */ typedef struct quad { int tx, ty; // The (x,y) coordinates of the top-left pixel in the quad int w; // How many pixels wide the quad is int h; // How many pixels high the quad is

int sx; // Width of the original image, this is needed for the key. // This *MUST* be the same for all nodes in the BST

int key; // A unique identifier (remember we discussed BST nodes // should have unique keys to identify each node). The // key identifier here will be created as: // key = tx + (ty * sx) // This means that only one quad can start at a specific // pixel.

int wsplit; // 1 if this quad is supposed to be split along the width // 0 if this quad is supposed to be split along the height

/** * TODO: Complete the definition of the Quad struct */

} Quad;

///////////////////////////////////////////////////////////////////////////////

Quad *new_Quad(int tx, int ty, int w, int h, int wsplit, int sx) { /** * This function creates and initializes a new Quad for a rectanglecstarting * at (tx, ty) with a width 'w' and height 'h'. The width ofcthe image in * which this rectangle exists is 'sx', use this to computecthe key as: * * key = tx + (ty * sx) * * TODO: Implement this function */

return NULL; }

Quad *BST_insert(Quad *root, Quad *new_node) { /** * This function inserts a new Quad node into the BST rooted atc'root'. The * new_node must already be initialized with validcdata, and must have a * unique key. * * Your function must make sure that there are no duplicate nodescwith the * same key in the BST, and if it finds any you shouldcprint the following * message to the screen: * * printf("Duplicate Quad (tx,ty,sx)=%d,%d, %d, was ignored ",....); * (of course you need to provide the relevant variables to print) * * And it must return without inserting anyting in the BST. * * TODO: Implement this function */

return NULL; }

Quad *BST_search(Quad *root, int tx, int ty) { /** * This function searches the BST for a Quad at the speficied position. If * found, it must return a pointer to the quad that contains it. * * Search has to happen according to the BST search process - so you need to * figure out what value to use during the search process to decide which * branch of the tree to search next. * * Note that the 'sx' value does not need to be passed in here since it must * be the same as the one in any Quad already in the tree. * * Return NULL if the Quad doesn't exist in the BST. * * TODO: Implement this function */ return NULL; }

Quad *find_successor(Quad *right_child) { /** * This function finds the successor of a Quad node by searching the right * subtree for the node that is most to the left (that will be the node * with the smallest key in that subtree) * * TODO: Implement this function */ return NULL; }

Quad *BST_delete(Quad *root, int tx, int ty) { /** * Deletes from the BST a Quad at the specified position. You must implement * the three cases of BST deletion we discussed in class. Make sure the * function can remove a Quad at any position without breaking the tree! * * Once again, remember that 'sx' is stored in the tree. * * TODO: Implement this function */

return NULL; }

Quad *delete_BST(Quad *root) { /** * This function deletes the BST and frees all memory used for nodes in it. * Recall that there is a specific order in which this needs to be done! * (consult the Unit 4 notes as needed) * * This function should return NULL. * * TODO: Implement this function */

return NULL; }

void BST_inorder(Quad *root, int depth) { /** * This function performs an in-order traversal of the BST and prints out the * information for each Quad using this exactly this print statement: * * printf("Depth=%d, key=%d, tx:ty (%d:%d), w=%d, h=%d, wsplit=%d ",...) * * Obviously, you must provide the variables to the printf function - we're * just giving you the formatting string. * * The depth value is increased by 1 for each recursive call so when you * print, you can see at what level each node is located! (this should help * you debug your code by making it easier to check the shape of your BST). * * TODO: Implement this function */

return; }

void BST_preorder(Quad *root, int depth) { /** * This function performs a pre-order traversal of the BST and prints out the * information for each Quad using this exactly this print statement: * * printf("Depth=%d, key=%d, tx:ty (%d:%d), w=%d, h=%d, wsplit=%d ",...) * * Obviously, you must provide the variables to the printf function - we're * just giving you the formatting string. * * The depth value is increased by 1 for each recursive call so when you * print, you can see at what level each node is located! (this should help * you debug your code by making it easier to check the shape of your BST). * * TODO: Implement this function */

return; }

void BST_postorder(Quad *root, int depth) { /** * This function performs a post-order traversal of the BST and prints out * the information for each Quad using this exactly this print statement: * * printf("Depth=%d, key=%d, tx:ty (%d:%d), w=%d, h=%d, wsplit=%d ",...) * * Obviously, you must provide the variables to the printf function - we're * just giving you the formatting string. * * The depth value is increased by 1 for each recursive call so when you * print, you can see at what level each node is located! (this should help * you debug your code by making it easier to check the shape of your BST). * * TODO: Implement this function */

return; }