binary search. traverse the tree to reach the nodes which contains the values between lower and upper to add them to the list. The doTreeSearchBetween function can append right to the list using functions from list.h
Implement the TreeSearchBetween() function and a stub helper function, doTreeSearchBetween()
tree.c
Record.h
List.h
List TreeSearchBetween(Tree t, Record lower, Record upper) { // TODO: Complete this function return ListNew(); } if (n // n - the current node // 1 - a list to accumulate results static void doTreeSearchBetween(Tree t, Node n, Record lower, Record upper, List 1) { // TODO: Complete this function // if tree is null NULL) { return NULL; } // compare middle element int mid = (n->left + n->right) / 2; // if values > lower, add it to the list if (n->rec > ) // if values #include
#include #include "List.h" #include "Record.h" #include "Tree.h" typedef struct node *Node; struct node { Record rec; Node left; Node right; }; struct tree { Node root; int (*compare) (Record, Record); }; ///// // Auxiliary functions static void doTreeFree (Node n, bool freeRecords); static Node doTreeInsert(Tree t, Node n, Record rec, bool *res); static Node newNode(Record rec); static Node doTreeDelete(Tree t, Node n, Record rec, bool *res); static Node joinTrees (Node ti, Node t2); static Record doTreeSearch(Tree t, Node n, Record rec); static void doTreeSearchBetween(Tree t, Node n, Record lower, Record upper, List 1); static void doTreeListInOrder(Node n); 6 7 #define MIN_ZID 1 #define MAX_ZID 9999999 8 #define MAX_FAMILY_NAME_LENGTH 15 #define MAX_GIVEN_NAME_LENGTH 15 9 10 11 12 13 typedef struct record *Record; 14 ** * 15 16 17 18 * Creates a record with the given zid, family name, and given name. Returns NULL if any of these are invalid. */ Record RecordNew(int zid, char *familyName, char *givenName); ** * Frees all memory allocated to the given record */ void RecordFree(Record r); 19 20 21 22 23 24 25 26 27 28 ** * Returns the zid contained in the given record */ int RecordGetZid(Record r); 29 30 ** 31 * * Returns the family name contained in the given record. The returned string should not be modified or freed. */ char *RecordGetFamilyName(Record r); ** 32 33 34 35 36 37 38 39 40 41 * * Returns the given name contained in the given record. The returned string should not be modified or freed. */ char *RecordGetGivenName(Record r); // Complexity: 0(1) List ListNew(void); // Frees the given list, but not the records contained in the list // Complexity: 0(1) void ListFree(List 1); // Adds a record to the end of the list. Does NOT make a copy of the // record before adding it to the list. // Average complexity: 0(1) void ListAppend(List 1, Record r); // Returns the number of items in the list // Complexity: 0(1) int ListSize(List 1); //// WIL /// // DO NOT use these functions typedef struct listIterator *ListIterator; // Creates an iterator for the given list // Complexity: 0(1) ListIterator ListItNew(List 1); // Gets the next item in the list. The item should not be modified. // Complexity: 0(1) Record ListitNext(ListIterator it); // Checks if the list has a next item // Complexity: 0(1) bool ListItHasNext(ListIterator it); // Frees the given iterator // Complexity: 0(1) void ListitFree(ListIterator it); Inserting: 11 13 17 19 23 29 31 37 41 43 Searching between 38 and 49 Search returned: 41 43 Inserting: 11 13 17 19 23 29 31 37 41 43 Searching between 10 and 20 Search returned: 11 13 17 19 Inserting: 11 13 17 19 23 29 31 37 41 43 Searching between 32 and 35 Search returned
