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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef struct _BSTNode { // canonical name "struct _BSTNode:
int value;
struct _BSTNode* left; // size of address is the same
// no matter the type
struct _BSTNode* right;
} BSTNode; // shortcut name "BSTNode"
void insert(int value, BSTNode** a_root) {
if (*a_root == NULL) {
BSTNode* new_node = malloc(sizeof(*new_node));
*new_node = (BSTNode) {
.value = value, .left = NULL, .right = NULL
};
*a_root = new_node;
}
// value is smaller, put on left
else if (value < (*a_root)->value) {
insert(value, &((*a_root)->left));
}
// value is larger, put on right
// value is equal also ends up on right
else {
insert(value, &((*a_root)->right));
}
}
void _plain_print_tree(const BSTNode* root) {
if (root != NULL) {
_plain_print_tree(root->left);
printf("[%d] ", root->value);
_plain_print_tree(root->right);
}
}
void print_tree(BSTNode const* root, char* prefix) {
printf("%s", prefix);
_plain_print_tree(root);
printf("\n");
}
void destroy_tree(BSTNode** a_root) {
// TODO: implement
// it will be similar to _plain_print_tree
}
int main(int argc, char* argv[]) {
// tree of size 0
BSTNode* root = NULL;
assert(root == NULL);
print_tree(root, "Empty Tree: ");
// tree of size 1
insert(6, &root);
assert(root != NULL);
assert(root->left == NULL);
assert(root->right == NULL);
assert(root->value == 6);
print_tree(root, "Tree Size 1: ");
// tree of size 2
insert(5, &root);
assert(root->left != NULL);
assert(root->left->left == NULL);
assert(root->left->right == NULL);
assert(root->left->value == 5);
print_tree(root, "Tree Size 2: ");
// tree of size 3
insert(8, &root);
assert(root->right != NULL);
assert(root->right->left == NULL);
assert(root->right->right == NULL);
assert(root->right->value == 8);
print_tree(root, "Tree Size 3: ");
// tree of size 4
insert(2, &root);
assert(root->left->left != NULL);
assert(root->left->left->left == NULL);
assert(root->left->left->right == NULL);
assert(root->left->left->value == 2);
print_tree(root, "Tree Size 4: ");
destroy_tree(&root);
assert(root == NULL);
return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */
|
© Copyright 2022 Alexander J. Quinn This content is protected and may not be shared, uploaded, or distributed.