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 71 | #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
// In your code, you can and should follow the same pattern, but please make sure you
// can write it yourself. Do not copy. It is fine if your code comes out very similar.
// CAUTION: Remember to parenthesize (*a_root).
typedef struct _BSTNode {
int value;
struct _BSTNode* left;
struct _BSTNode* right;
} BSTNode;
void insert(int value, BSTNode** a_root) {
if(*a_root == NULL) { // If tree is empty...
BSTNode* new_node = malloc(sizeof *new_node);
*new_node = (BSTNode) { .value = value, .left = NULL, .right = NULL };
*a_root = new_node;
}
else if(value < (*a_root) -> value) { // If value belongs in left subtree
insert(value, &(*a_root) -> left);
}
else if(value >= (*a_root) -> value) { // If value belongs in left subtree
insert(value, &(*a_root) -> right);
}
}
void print_in_order(BSTNode* root) {
if(root != NULL) { // IN-ORDER TRAVERSAL (remember this)
print_in_order(root -> left); // - Traverse left subtree
printf("[%d]\n", root -> value); // - Visit root node
print_in_order(root -> right); // - Traverse right subtree
}
}
void free_tree(BSTNode** a_root) {
// We can only free a tree that contains node(s).
if(*a_root != NULL) { // POST-ORDER TRAVERSAL (remember this)
free_tree(&(*a_root) -> left); // - Traverse left subtree
free_tree(&(*a_root) -> right); // - Traverse right subtree
free(*a_root); // - Visit the root
*a_root = NULL;
}
}
// PRE-ORDER TRAVERSAL (remember this)
// - Visit the root
// - Traverse left subtree
// - Traverse right subtree
int main(int argc, char* argv[]) {
BSTNode* root = NULL; // size=0
// append(6, &head, &tail); // not for BST
insert(6, &root);
insert(2, &root);
insert(4, &root);
insert(1, &root);
insert(3, &root);
insert(5, &root);
insert(7, &root);
print_in_order(root);
free_tree(&root);
assert(root == NULL);
return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */
|
© Copyright 2024 Alexander J. Quinn This content is protected and may not be shared, uploaded, or distributed.