1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>
// AS ALWAYS: Do not copy code from lecture examples (or anywhere else except code that
// you wrote yourself) without explicit permission from the instructor (me).
typedef struct _BSTNode {
char const* name;
struct _BSTNode* left;
struct _BSTNode* right;
} BSTNode;
void insert(BSTNode** a_root, char const* name) {
// If tree at *a_root is empty, then replace the empty tree with a tree of size = 1.
if(*a_root == NULL) {
BSTNode* new_root = malloc(sizeof(*new_root));
*new_root = (BSTNode) { .name = name, .left = NULL, .right = NULL };
*a_root = new_root;
}
// If name (to be inserted) is "less than" the name at *a_root, insert in left subtree.
else if(strcmp(name, (*a_root) -> name) < 0) {
insert(&((*a_root) -> left), name);
}
else {
insert(&((*a_root) -> right), name);
}
}
void print_bst(BSTNode const* root) { // IN-ORDER traversal
if(root != NULL) { // … because printing an empty tree means printing nothing at all.
print_bst(root -> left); // 1. Traverse the left subtree.
printf("%s\n", root -> name); // 2. Visit (print value of) the root
print_bst(root -> right); // 3. Traverse the right subtree.
}
}
void free_bst(BSTNode** a_root) { // POST-ORDER traversal
// ⚠ IMPORTANT: Free the subtrees «before» you free the root.
if(*a_root != NULL) { // No need to free an empty tree.
free_bst(&((*a_root) -> left)); // 1. Traverse the left subtree.
free_bst(&((*a_root) -> right)); // 2. Traverse the right subtree.
free(*a_root); // 3. Visit (free) the root node.
*a_root = NULL;
}
}
int main(int argc, char* argv[]) {
BSTNode* root = NULL;
// Tree has size = 0 (empty tree)
insert(&root, "delta");
insert(&root, "bravo");
insert(&root, "alpha");
insert(&root, "charlie");
insert(&root, "foxtrot");
insert(&root, "echo");
insert(&root, "golf");
insert(&root, "india");
// Tree has size = 8 (8 nodes)
print_bst(root);
free_bst(&root);
assert(root == NULL);
return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */
|
© Copyright 2021 Alexander J. Quinn This content is protected and may not be shared, uploaded, or distributed.