I need to implement a binary search tree in C using these methods:

/** Create a proper, empty binary search tree object. * * Pre: compare is the name of a user-defined function satisfying the BST specification * display is the name of a user-defined function satisfying the BST specification * destroy is the name of a user-defined function satisfying the BST specification * * Returns: a BST object with NULL root and configured to use the three user-supplied * functions for comparing, destroying and displaying user-defined data objects * stored in the tree */ BST BST_create(int32_t (*compare)(const BSTNode* const left, const BSTNode* const right), void (*display)(FILE* fp, const BSTNode* const pD), void (*destroy)(BSTNode* pNode));

/** Inserts user data object into a BST, unless it duplicates an existing object. * * Pre: pTree points to a proper BST object * userNode points to a proper BSTNode object * * Returns: true iff the insertion was performed; the implementation will not * insert a new element that is equal to one that's already in the * BST (according to the user-supplied comparison function) */ bool BST_insert(BST* const pTree, const BSTNode* const userNode);

/** Searches a proper BST for an occurence of a user data object that equals * *pData (according to the user-supplied comparison function). * * Pre: pTree points to a proper BST object * pData points to a proper BSTNode object * * Returns: pointer to matching user data object; NULL if no match is found */ BSTNode* BST_find(const BST* const pTree, const BSTNode* const userNode);

/** Deallocates all dynamic memory associated with a proper BST object. * * Pre: *pTree is a proper BST object * Post: all the user payloads and payload wrappers associated with *pTree * have been freed * the BST object itself is NOT freed since it may or may not have * been allocated dynamically; that's the responsibility of the caller * * Calls: Payload_destroy() to handle destruction of the user's data object */ void BST_destroy(BST* const pTree);

Structs used:

struct _PayloadWrapper { Payload* userdata; // pointer to a user data object BSTNode node; }; typedef struct _PayloadWrapper PayloadWrapper;

struct _Payload { char* str; }; typedef struct _Payload Payload;

Payload.c

// Payload.c #include "Payload.h" #include #include

/** Creates a dynamically-allocated Payload object initialized so that * weight == wt. * * Pre: wt is initialized * * Returns: pointer to new Payload object */ Payload* Payload_create(uint32_t wt) { Payload* newLoad = malloc(sizeof(Payload)); newLoad->weight = wt; return newLoad; }

/** Compares two Payload objects by comparing their weight fields. * * Pre: left and right point to proper Payload objects * * Returns: < 0 if left->weight < right->weight * 0 if left->weight == right->weight * > 0 if left->weight > right->weight */ int32_t Payload_compare(const Payload* const left, const Payload* const right) { /*** Implementation here is up to you. ***/ return strcmp(left->str, right->str); }

/** Destroys a user payload object; this one's trivial but a more * interesting Payload type would require a more interesting * destructor. * Here, we do need to take into account whether: * - the Payload object has dynamic content (here, no) * - the Payload object itself was allocated dynamically (yes) */ void Payload_destroy(Payload* pLoad) { free(pLoad); }

/** Writes a formatted representation of a Payload object. * * Pre: fp is open on an output device * pLoad points to a proper Payload object */ void Payload_display(FILE* fp, const Payload* const pLoad) {

fprintf(fp, "%"PRIu32, pLoad->weight); }

PayloadWrapper.c

#include "PayloadWrapper.h" #include #include

/** Creates a new PayloadWrapper object holding *pData. * * Pre: *data is a proper Payload object * * Returns: pointer to a dynamically-allocated proper PayloadWrapper * that encapsulates pData */ PayloadWrapper* PayloadWrapper_create(Payload* pData) { PayloadWrapper* newWrapper = malloc(sizeof(PayloadWrapper)); newWrapper->userdata = pData; newWrapper->node.lchild = NULL; newWrapper->node.rchild = NULL; return newWrapper; }

/** Given a pointer to a BSTNode object, computes the address of the * surrounding PayloadWrapper object. * * Pre: pNode points to a proper BSTNode, contained in a proper PayloadWrapper * * Returns: a pointer to the surrounding PayloadWrapper */ PayloadWrapper* PayloadWrapper_getPtr(const BSTNode* const pNode) { return (PayloadWrapper*) ((uint8_t*) pNode - offsetof(PayloadWrapper, node));

}

/** Compares two Payload objects by comparing their weight fields. * * Pre: left and right point to proper Payload objects * * Returns: < 0 if left->weight < right->weight * 0 if left->weight == right->weight * > 0 if left->weight > right->weight */ int32_t PayloadWrapper_compare(const BSTNode* const leftNode, const BSTNode* const rightNode) { PayloadWrapper* leftWrapper = NULL; PaylaodWrapper* rightWrapper = NULL; /*** Implementation here is up to you. ***/ return Payload_compare(leftWrapper->userdata, rightWrapper->userdata); }

/** Deallocates all memory associated with a PayloadWrapper object. */ void PayloadWrapper_destroy(BSTNode* pNode) { /*** Implementation here is up to you. ***/ free(pNode); }

/** Writes a formatted representation of a Payload object. * * Pre: fp is open on an output device * pNode points to a proper BSTNode inside a PayloadWrapper object */ void PayloadWrapper_display(FILE* fp, const BSTNode* const pNode) { const PayloadWrapper* wrapper = PayloadWrapper_getPtr(pNode); Payload_display(fp, wrapper->userdata); }