summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/02/01/binary_tree.c34
-rw-r--r--src/02/01/binary_tree.h18
-rw-r--r--src/02/02/README.md4
-rw-r--r--src/02/02/btree.c37
-rw-r--r--src/02/03/btree.c44
-rw-r--r--src/02/03/main.c25
-rw-r--r--src/02/04/hash.c56
-rw-r--r--src/02/04/list.c32
-rw-r--r--src/02/04/tuple.c12
-rw-r--r--src/02/05/btree.c65
10 files changed, 299 insertions, 28 deletions
diff --git a/src/02/01/binary_tree.c b/src/02/01/binary_tree.c
index cc3e666..16eec3d 100644
--- a/src/02/01/binary_tree.c
+++ b/src/02/01/binary_tree.c
@@ -2,6 +2,12 @@
#include <stdio.h>
#include <stdlib.h>
+/**
+ * Initialize a new node for a Binary Tree.
+ *
+ * @param data the data to assign to the root of the tree.
+ * @return The root of the binary tree.
+ */
Node *initialize(int data) {
Node *item = malloc(sizeof(Node));
item->data = data;
@@ -10,6 +16,16 @@ Node *initialize(int data) {
return item;
}
+/*
+ * Traverses a binary tree using the traversal algorithm specified.
+ * Time: O(n)
+ * Space: O(1)
+ *
+ * @param node The root of the binary tree
+ * @param vistior A callback function to invoke on each node during the tree
+ * traversal
+ * @param traversal Specifies what type of traversal to perform
+ */
void traverse(Node *node, Visitor visitor, enum Traversal traversal) {
if (!node)
return;
@@ -36,10 +52,26 @@ void traverse(Node *node, Visitor visitor, enum Traversal traversal) {
}
}
+/**
+ * Frees the memory allocated for a node in a tree
+ *
+ * @param node The node in the binary tree to free
+ */
static void destructor(Node *node) { free(node); }
-void destroy(Node *head) { traverse(head, destructor, POSTORDER); }
+/**
+ * Frees the memory associated with each node in a binary tree.
+ *
+ * @param root The root of the tree
+ */
+void destroy(Node *root) { traverse(root, destructor, POSTORDER); }
+/**
+ * A helper method to print out a visual representation of the tree
+ *
+ * @param node A node in a binary tree.
+ * @param level The level in the tree that the node is at
+ */
void inspect(Node *node, int level) {
if (!node)
return;
diff --git a/src/02/01/binary_tree.h b/src/02/01/binary_tree.h
index e30b71a..f4ae62c 100644
--- a/src/02/01/binary_tree.h
+++ b/src/02/01/binary_tree.h
@@ -1,3 +1,6 @@
+/**
+ * A struct to represent a node in a Binary Tree
+ */
struct node {
int data;
struct node *left;
@@ -5,8 +8,21 @@ struct node {
};
typedef struct node Node;
+
+/**
+ * A signature of a function pointer
+ * that can be used to traverse a binary tree.
+ */
typedef void(Visitor)(Node* node);
-enum Traversal { INORDER = 1, PREORDER = 2, POSTORDER = 4 };
+
+/**
+ * The different types of traversals that the binary tree can perform
+ */
+enum Traversal {
+ INORDER = 1, // In order traversal
+ PREORDER = 2, // Pre order traversal
+ POSTORDER = 4 // Post order traversal
+};
Node *initialize(int data);
void traverse(Node *node, Visitor visitor, enum Traversal traversal);
diff --git a/src/02/02/README.md b/src/02/02/README.md
index 16cd9c1..91598ae 100644
--- a/src/02/02/README.md
+++ b/src/02/02/README.md
@@ -1 +1,3 @@
-Design a recursive linear-time algorithm that tests whether a binary tree satisfies the search tree order property at every node.
+Design a recursive linear-time algorithm that
+tests whether a binary tree satisfies the
+search tree order property at every node.
diff --git a/src/02/02/btree.c b/src/02/02/btree.c
index dea5996..88226ab 100644
--- a/src/02/02/btree.c
+++ b/src/02/02/btree.c
@@ -2,6 +2,11 @@
#include <limits.h>
#include <stdio.h>
+/**
+ * A helper function used
+ * to print a visual representation
+ * of a Binary Tree
+ */
static void inspect(BTree *tree, int level) {
if (!tree)
return;
@@ -14,6 +19,19 @@ static void inspect(BTree *tree, int level) {
inspect(tree->right, level + 1);
}
+/**
+ * A recursive function that can
+ * be used to ensure that each node in
+ * a Binary Tree satisfies the
+ * Binary Search Tree property.
+ *
+ * @param tree A tree or subtree to verify
+ * @param min the minimum value that each node must be greater than
+ * @param max the maximum value that each node must be less than.
+ * @return Returns tree when the tree is a binary search tree, otherwise false.
+ *
+ *
+ */
static bool in_range(BTree *tree, int min, int max) {
if (!tree)
return true;
@@ -25,6 +43,12 @@ static bool in_range(BTree *tree, int min, int max) {
return in_range(tree->left, min, data) && in_range(tree->right, data, max);
}
+/**
+ * Initializes a binary tree.
+ *
+ * @param the data to assign to the root node in the tree.
+ * @return the root of the tree.
+ */
BTree *btree_init(int data) {
BTree *tree = malloc(sizeof(BTree));
tree->left = NULL;
@@ -33,6 +57,19 @@ BTree *btree_init(int data) {
return tree;
}
+/**
+ * A function that determines if a binary tree
+ * is a binary search tree or not.
+ *
+ * @param tree The root of the tree to inspect
+ * @return Returns true when the tree is a binary search tree;
+ */
bool btree_is_bst(BTree *tree) { return in_range(tree, INT_MIN, INT_MAX); }
+/**
+ * A helper function used to print a visual
+ * representation of the binary tree.
+ *
+ * @param tree The tree or subtree to inspect
+ */
void btree_inspect(BTree *tree) { inspect(tree, 0); }
diff --git a/src/02/03/btree.c b/src/02/03/btree.c
index f895c5a..81fcaca 100644
--- a/src/02/03/btree.c
+++ b/src/02/03/btree.c
@@ -1,6 +1,13 @@
#include "btree.h"
#include <stdio.h>
+/**
+ * A helper function used to print a visual
+ * representation of a binary tree.
+ *
+ * @param tree the tree or subtree to inspect
+ * @param level the level of the subtree
+ */
static void inspect(BTree *tree, int level) {
if (!tree)
return;
@@ -13,6 +20,12 @@ static void inspect(BTree *tree, int level) {
inspect(tree->right, level + 1);
}
+/**
+ * Initializes the root of a binary tree
+ *
+ * @param data the data to assign to the root of the tree.
+ * @return Returns the root of the tree.
+ */
BTree *btree_init(int data) {
BTree *tree = malloc(sizeof(BTree));
tree->left = NULL;
@@ -21,25 +34,34 @@ BTree *btree_init(int data) {
return tree;
}
+/**
+ * Inserts a new node into a binary tree.
+ *
+ * @param tree the tree to insert the new new into
+ * @return Returns the root of the tree.
+ */
BTree *btree_insert(BTree *tree, int data) {
if (!tree)
return btree_init(data);
- if (data <= tree->data) {
- if (tree->left) {
+ if (data <= tree->data)
+ if (tree->left)
btree_insert(tree->left, data);
- } else {
+ else
tree->left = btree_init(data);
- }
- } else {
- if (tree->right) {
- btree_insert(tree->right, data);
- } else {
- tree->right = btree_init(data);
- }
- }
+ else if (tree->right)
+ btree_insert(tree->right, data);
+ else
+ tree->right = btree_init(data);
return tree;
}
+/**
+ * A helper function used to print
+ * a visual representation of a binary
+ * tree.
+ *
+ * @param tree The root of the tree to inspect
+ */
void btree_inspect(BTree *tree) { inspect(tree, 0); }
diff --git a/src/02/03/main.c b/src/02/03/main.c
index 44e82e2..4f605aa 100644
--- a/src/02/03/main.c
+++ b/src/02/03/main.c
@@ -1 +1,24 @@
-int main(int argc, char *argv[]) { return 0; }
+#include "btree.h"
+#include <stdio.h>
+
+int main(int argc, char *argv[]) {
+ printf("=== COMP-272 - Assignment 02 - Question 03 ===\n");
+ printf("Tree 1: unbalanced tree\n");
+ BTree *tree = btree_insert(NULL, 1);
+ btree_insert(tree, 5);
+ btree_insert(tree, 2);
+ btree_insert(tree, 4);
+ btree_insert(tree, 3);
+ btree_inspect(tree);
+
+ printf("Tree 2: balanced tree\n");
+ tree = btree_insert(NULL, 3);
+ btree_insert(tree, 2);
+ btree_insert(tree, 4);
+ btree_insert(tree, 1);
+ btree_insert(tree, 5);
+ btree_inspect(tree);
+
+ printf("Bye\n");
+ return 0;
+}
diff --git a/src/02/04/hash.c b/src/02/04/hash.c
index cc0089d..f7cc5ec 100644
--- a/src/02/04/hash.c
+++ b/src/02/04/hash.c
@@ -4,6 +4,12 @@
#include <stdlib.h>
#include <string.h>
+/**
+ * Initialize a new hash table.
+ *
+ * @param size The number of buckets to allocate for the chash table.
+ * @return Returns the hash table.
+ */
Hash *hash_init(int size) {
Hash *hash = malloc(sizeof(Hash));
hash->size = size;
@@ -11,8 +17,26 @@ Hash *hash_init(int size) {
return hash;
}
-unsigned int hash_index(Hash *hash, int key) { return key % hash->size; }
+/**
+ * Computes a hash code for the given key.
+ *
+ * @param hash The hash table that the key is used in.
+ * @param key The key to produce a hash code for
+ * @return Returns a hash code for the given key.
+ */
+unsigned int hash_code(Hash *hash, int key) { return key % hash->size; }
+/**
+ * A function to search for a specific key in a linked list.
+ * This performs a O(n) search to find the matching key.
+ * A possible optimization would be to convert this to do a binary
+ * search for the given key using a binary search tree instead of a linked
+ * list.
+ *
+ * @param list The linked list to search for the given key
+ * @param key The key to search for in the linked list
+ * @return Returns the data associated with the given key.
+ */
void *search(Node *list, int key) {
Node *current = list;
@@ -26,14 +50,30 @@ void *search(Node *list, int key) {
return NULL;
}
+/**
+ * A function to fetch a specify value from a hash table by key.
+ *
+ * @param hash The hash table to search.
+ * @param key The key associated with the value to return
+ * @return Returns the data associated with the key or NULL if the key is not
+ * found.
+ */
void *hash_get(Hash *hash, int key) {
- unsigned int bucket = hash_index(hash, key);
+ unsigned int bucket = hash_code(hash, key);
Node *n = hash->buckets + bucket;
return (n->data) ? search(n, key) : NULL;
}
+/**
+ * A function to set the value associated with a key
+ * in a hash table.
+ *
+ * @param hash The hash table to insert the key/value pair into
+ * @param key The key associated with the value to insert.
+ * @param value The value associated with the key to insert.
+ */
void hash_set(Hash *hash, int key, void *value) {
- unsigned int bucket = hash_index(hash, key);
+ unsigned int bucket = hash_code(hash, key);
Tuple *tuple = tuple_initialize(key, value);
Node *n = hash->buckets + bucket;
@@ -43,6 +83,11 @@ void hash_set(Hash *hash, int key, void *value) {
hash->buckets[bucket] = *list_initialize(tuple);
}
+/**
+ * A function that pretty prints a key/value pair.
+ *
+ * @param data The Tuple to print.
+ */
void print_tuple(void *data) {
Tuple *t = data;
@@ -52,6 +97,11 @@ void print_tuple(void *data) {
printf("(nil)");
}
+/**
+ * Prints a visual representation of a hash table.
+ *
+ * @param hash The hash table to inspect
+ */
void hash_inspect(Hash *hash) {
for (int i = 0; i < hash->size; i++) {
printf("%2d: ", i);
diff --git a/src/02/04/list.c b/src/02/04/list.c
index cfc3b2c..1de7a03 100644
--- a/src/02/04/list.c
+++ b/src/02/04/list.c
@@ -2,6 +2,12 @@
#include <stdio.h>
#include <stdlib.h>
+/**
+ * Initializes a new node for a linked list.
+ *
+ * @param data The data to bind to the new node in the list.
+ * @return Returns a new linked list node
+ */
Node *list_initialize(void *data) {
Node *node = malloc(sizeof(Node));
node->data = data;
@@ -9,6 +15,13 @@ Node *list_initialize(void *data) {
return node;
}
+/**
+ * Adds a new item to the tail of a linked list
+ *
+ * @param head The head of a linked list
+ * @param data The data to add to the tail of a linked list
+ * @return Returns the new node tail node
+ */
Node *list_add(Node *head, void *data) {
Node *tail;
Node *tmp = head;
@@ -23,6 +36,13 @@ Node *list_add(Node *head, void *data) {
return tail->next;
}
+/**
+ * Returns a specific node by zero based index in a linked list.
+ *
+ * @param self the head of the linked list
+ * @param index the offset from the head of the node to return
+ * @return Returns the node at the specified offset or NULL.
+ */
Node *list_get(Node *self, int index) {
if (!self || index < 0)
return NULL;
@@ -34,6 +54,12 @@ Node *list_get(Node *self, int index) {
return self;
}
+/**
+ * Returns the total number of nodes in a linked list.
+ *
+ * @param head The head of a linked list
+ * @returns Returns the # of items in the list.
+ */
int list_size(Node *head) {
int i = 0;
for (Node *tmp = head; tmp && tmp != NULL; tmp = tmp->next)
@@ -41,6 +67,12 @@ int list_size(Node *head) {
return i;
}
+/**
+ * Prints a visual representation of a linked list.
+ *
+ * @param self The head of the linked list
+ * @param printer A callback function to invoke to print each item.
+ */
void list_inspect(Node *self, Printer printer) {
if (!self)
return;
diff --git a/src/02/04/tuple.c b/src/02/04/tuple.c
index 9e31975..f7ff327 100644
--- a/src/02/04/tuple.c
+++ b/src/02/04/tuple.c
@@ -1,6 +1,13 @@
#include "tuple.h"
#include "stdlib.h"
+/**
+ * Initializes a new tuple bound to a key/value pair.
+ *
+ * @param key The key to bind to
+ * @param value The value to bind to
+ * @return Returns a new Tuple
+ */
Tuple *tuple_initialize(int key, void *value) {
Tuple *tuple = malloc(sizeof(Tuple));
tuple->key = key;
@@ -8,4 +15,9 @@ Tuple *tuple_initialize(int key, void *value) {
return tuple;
}
+/**
+ * A destructor for a Tuple
+ *
+ * @param tuple The tuple to free
+ */
void tuple_destroy(Tuple *tuple) { return free(tuple); }
diff --git a/src/02/05/btree.c b/src/02/05/btree.c
index 42b2e14..a356b50 100644
--- a/src/02/05/btree.c
+++ b/src/02/05/btree.c
@@ -2,6 +2,12 @@
#include "stack.h"
#include <stdio.h>
+/**
+ * Prints a visual representation of a binary tree
+ *
+ * @param tree The tree or subtree to print
+ * @param level The level in the tree that the subtree belongs to
+ */
static void inspect(BTree *tree, int level) {
if (!tree)
return;
@@ -14,6 +20,12 @@ static void inspect(BTree *tree, int level) {
inspect(tree->right, level + 1);
}
+/**
+ * Initializes a new instance of a binary tree.
+ *
+ * @param data The data to bind to the root of the new subtree.
+ * @return Returns the new subtree.
+ */
BTree *btree_init(int data) {
BTree *tree = malloc(sizeof(BTree));
tree->left = NULL;
@@ -22,26 +34,40 @@ BTree *btree_init(int data) {
return tree;
}
-void btree_pre_order_number(BTree *root) {
- BTree *original = root;
- if (root == NULL)
+/**
+ * Performs and caches the result of a pre order traversal
+ * on a binary tree. Cached results are stored in the root of
+ * the tree and not on each node of the tree.
+ *
+ * @param tree The subtree to perform the traversal on
+ */
+void btree_pre_order_number(BTree *tree) {
+ BTree *original = tree;
+ if (tree == NULL)
return;
Stack *stack = stack_init();
int i = 0;
- stack_push(stack, root);
+ stack_push(stack, tree);
while (stack_size(stack) > 0) {
- root = stack_pop(stack);
- original->pre_order[i++] = root->data;
+ tree = stack_pop(stack);
+ original->pre_order[i++] = tree->data;
- if (root->right != NULL)
- stack_push(stack, root->right);
- if (root->left != NULL)
- stack_push(stack, root->left);
+ if (tree->right != NULL)
+ stack_push(stack, tree->right);
+ if (tree->left != NULL)
+ stack_push(stack, tree->left);
}
}
+/**
+ * Performs and caches the result of an in order traversal
+ * on a binary tree. Cached results are stored in the root of
+ * the tree and not on each node of the tree.
+ *
+ * @param root The subtree to perform the traversal on
+ */
void btree_in_order_number(BTree *root) {
BTree *original = root;
if (root == NULL)
@@ -65,6 +91,13 @@ void btree_in_order_number(BTree *root) {
}
}
+/**
+ * Performs and caches the result of an post order traversal
+ * on a binary tree. Cached results are stored in the root of
+ * the tree and not on each node of the tree.
+ *
+ * @param root The subtree to perform the traversal on
+ */
void btree_post_order_number(BTree *root) {
BTree *original = root;
if (root == NULL)
@@ -92,6 +125,13 @@ void btree_post_order_number(BTree *root) {
}
}
+/**
+ * Insert a new items into a binary tree.
+ *
+ * @param tree The tree to insert the data into.
+ * @param data The data to insert into the tree.
+ * @return Returns the new root of the tree.
+ */
BTree *btree_insert(BTree *tree, int data) {
if (!tree)
return btree_init(data);
@@ -109,4 +149,9 @@ BTree *btree_insert(BTree *tree, int data) {
return tree;
}
+/**
+ * Prints a visual representation of a binary tree.
+ *
+ * @param tree The subtree to inspect.
+ */
void btree_inspect(BTree *tree) { inspect(tree, 0); }
generated by cgit v1.2.3 (git 2.39.1) at 2026-02-02 23:51:13 +0000