Vinh La Kiến

48 bundles
2 files2 months ago
1

Main.c

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194
#include <stdlib.h> #include <stdio.h> #include <stdbool.h> #include "Node.h" #include "BST.h" void testStartEnd(); void testEmpty(); void testSorted(); void testReverseSorted(); void testBalanced(); void printTree(BST* tree); void printNodes(Node* node, int spaces); int main() { printf("%s\n", "=========================================="); printf("%s\n", " TESTING BST"); printf("%s\n", " 1 = true, 0 = false"); printf("%s\n", "=========================================="); testStartEnd(); printf("%s\n", "=========================================="); testEmpty(); printf("%s\n", "=========================================="); testSorted(); //end getchar(); } void testStartEnd() { //test initializeBST BST* tree = initializeBST(); printf("%s\n", "POST BST INITIALIZATION"); printf("tree is initialized = %i\n", (tree->count == 0)); //test deleteBST deleteBST(tree); printf("%s\n", "POST BST DELETE"); printf("tree is initialized = %i\n", (tree->count == 0)); } void testEmpty() { //start BST* tree = initializeBST(); //testing with no nodes printf("%s\n", "WITHOUT NODES:"); //test list double* arr1 = list(tree); printf("tree list is empty = %i\n", (arr1 == NULL)); //test contains printf("contains 7 = %i\n", contains(tree, 7)); //test delete printf("deleted 7 = %i\n", delete(tree, 7)); //test isEmpty printf("tree is empty = %i\n", isEmpty(tree)); //test size printf("count = %i\n", size(tree)); //end deleteBST(tree); } void testSorted() { //start BST* tree = initializeBST(); printf("%s\n", "WITH SORTED NODES:"); //test adding unique values printf("add 3 = %i\n", insert(tree, 3)); printf("add 6 = %i\n", insert(tree, 6)); printf("add 7 = %i\n", insert(tree, 7)); printf("add 13 = %i\n", insert(tree, 13)); printf("add 14 = %i\n", insert(tree, 14)); printTree(tree); //test adding a duplicate printf("add 6 again = %i\n", insert(tree, 6)); //test the size function printf("count = %i\n", size(tree)); //test contains with an existing value printf("contains 7 = %i\n", contains(tree, 7)); //test delete with an existing value printf("deleting 7 = %i\n", delete(tree, 7)); printTree(tree); //test delete with a non-existant value printf("deleting 8 = %i\n", delete(tree, 7)); //check size again after deleting printf("count = %i\n", size(tree)); //test contains with a non-existant value printf("contains 7 = %i\n", contains(tree, 7)); //test list double* arr = list(tree); for (int i = 0; i < size(tree); i++) printf("%f ", arr[i]); printf("\n"); free(arr); //end deleteBST(tree); } /* * The following functions can be used to print out the entire tree structure horizontally * using a simple recursive function. It is good for testing correct insertion and deletion. */ void testReverseSorted() { //start BST* tree = initializeBST(); printf("%s\n", "WITH REVERSE SORTED NODES:"); //test adding unique values printf("add 14 = %i\n", insert(tree, 14)); printf("add 13 = %i\n", insert(tree, 13)); printf("add 7 = %i\n", insert(tree, 7)); printf("add 6 = %i\n", insert(tree, 6)); printf("add 3 = %i\n", insert(tree, 3)); //test adding a duplicate printf("add 6 again = %i\n", insert(tree, 6)); //test the size function printf("count = %i\n", size(tree)); //test contains with an existing value printf("contains 7 = %i\n", contains(tree, 7)); //test delete with an existing value printf("deleting 7 = %i\n", delete(tree, 7)); printTree(tree); //test delete with a non-existant value printf("deleting 8 = %i\n", delete(tree, 7)); //check size again after deleting printf("count = %i\n", size(tree)); //test contains with a non-existant value printf("contains 7 = %i\n", contains(tree, 7)); //test list double* arr = list(tree); for (int i = 0; i < size(tree); i++) printf("%f ", arr[i]); printf("\n"); free(arr); //end deleteBST(tree); } void testBalanced() { //start BST* tree = initializeBST(); printf("%s\n", "WITH BALANCED NODES:"); printf("add 3 = %i\n", insert(tree, 3)); printf("add 6 = %i\n", insert(tree, 6)); printf("add 7 = %i\n", insert(tree, 7)); printf("add 13 = %i\n", insert(tree, 13)); printf("add 14 = %i\n", insert(tree, 14)); printTree(tree); //test adding a duplicate printf("add 6 again = %i\n", insert(tree, 6)); //test the size function printf("count = %i\n", size(tree)); //test contains with an existing value printf("contains 7 = %i\n", contains(tree, 7)); //test delete with an existing value printf("deleting 7 = %i\n", delete(tree, 7)); printTree(tree); //test delete with a non-existant value printf("deleting 8 = %i\n", delete(tree, 7)); //check size again after deleting printf("count = %i\n", size(tree)); //test contains with a non-existant value printf("contains 7 = %i\n", contains(tree, 7)); //test list double* arr = list(tree); for (int i = 0; i < size(tree); i++) printf("%f ", arr[i]); printf("\n"); free(arr); //end deleteBST(tree); } void printTree(BST* tree) { printf("\n%s\n", "Current tree structure: "); printNodes(tree->root, 4); printf("\n"); } void printNodes(Node* node, int spaces) { int i; if (node != NULL) { printNodes(node->right, spaces + 10); for (i = 0; i < spaces; i++) printf(" "); printf("%f\n", node->value); printNodes(node->left, spaces + 10); } }

BST.c

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220
#include "BST.h" #include "Node.h" #include <stdbool.h> #include <stdlib.h> void postOrderDelete(Node* node); int inOrderList(double* arr, Node* node, int index); bool recursiveContains(Node* node, double value); bool recursiveInsert(Node* current, Node*parent, double value); void deleteNode(BST* tree, Node* node, Node* parent); BST* initializeBST() { BST* tree = malloc(sizeof(BST)); tree->count = 0; tree->root = NULL; return tree; } void deleteBST(BST* tree) { //post order traversal to delete each node if (tree->count > 0) postOrderDelete(tree->root); //delete BST free(tree); } void postOrderDelete(Node* node) { //TODO - Write a post-order traversal that deletes each node from memory if (node == NULL) return; postOrderDelete(node->left); postOrderDelete(node->right); free(node); } double* list(BST* tree) { if (tree->count == 0) return NULL; double* arr = calloc(tree->count, sizeof(double)); inOrderList(arr, tree->root, 0); return arr; } int inOrderList(double* arr, Node* node, int index) { //TODO - Write an in-order traversal that places each value in the given array // - Note: it needs to return index at the end to keep the index correctly if (node == NULL) return index; index = inOrderList(arr, node->left, index); arr[index] = node->value; index = inOrderList(arr, node->right, index + 1); return index; } bool contains(BST* tree, double value) { return recursiveContains(tree->root, value); } bool recursiveContains(Node* node, double value) { //TODO - Write a recursive binary search for the given value // - Return true if it's found, false if not if (node == NULL) return false; if (node->value == value) return true; bool result = recursiveContains(node->left, value); if (result == true) return true; result = recursiveContains(node->right, value); if (result == true) return true; return false; } bool insert(BST* tree, double value) { //if there are no nodes yet, make this value the root if (tree->count == 0) { tree->root = malloc(sizeof(Node)); tree->root->value = value; tree->root->left = NULL; tree->root->right = NULL; tree->count++; return true; } //call recursive insert to handle the rest if (recursiveInsert(tree->root, NULL, value)) { tree->count++; return true; } else return false; } bool recursiveInsert(Node* current, Node* parent, double value) { //TODO - follow the lecture pseudocode to write the recursive insert function // - returns true if the value was added, false if not // - don't forget to set the new node's left and right child to NULL if (current == NULL) { Node* node = malloc(sizeof(Node)); node->value = value; node->left = NULL; node->right = NULL; if (value < parent->value) { parent->left = node; } else { parent->right = node; } return true; } else { if (value < current->value) { if (recursiveInsert(current->left, current, value)) return true; } else if (recursiveInsert(current->right, current, value)) return true; return false; } } bool delete(BST* tree, double value) { //handle if tree is empty if (tree->count == 0) return false; //find the value in the tree and its parent Node* node = tree->root; Node* parent = NULL; bool foundIt = (node->value == value); while (node != NULL && !foundIt) { if (value < node->value) { parent = node; node = node->left; } else if (value > node->value) { parent = node; node = node->right; } else { foundIt = true; } } if (!foundIt) return false; //call the deleteNode function to delete the found node deleteNode(tree, node, parent); tree->count--; return true; } void deleteNode(BST* tree, Node* node, Node* parent) { //TODO - follow the lecture pseudocode to write the deleteNode function // - returns true if the value was deleted, false if not // - don't forget to free the memory for the node you're deleting if (parent == NULL) return; if (node->value < parent->value) deleteNode(tree, node, parent->left); else if (node->value > parent->value) deleteNode(tree, node, parent->right); else { if (parent->left == NULL) { Node* temp = parent->right; free(parent); parent = temp; return; } else if (parent->right == NULL) { Node* temp = parent->left; free(parent); parent = temp; return; } Node* latestLeftNode = parent->right; while (latestLeftNode != NULL && latestLeftNode->left != NULL) latestLeftNode = latestLeftNode->left; parent->value = latestLeftNode->value; deleteNode(tree, latestLeftNode, parent->right); } } bool isEmpty(BST* tree) { return (tree->count == 0); } int size(BST* tree) { return tree->count; }