Created
October 31, 2016 16:31
-
-
Save cypok/9fd74d3051537bfa095afcb32c53219a to your computer and use it in GitHub Desktop.
Simple BST with no copy & paste
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
#include <assert.h> | |
#include <stdbool.h> | |
typedef enum eChildKind { | |
LEFT, | |
RIGHT, | |
} ChildKind; | |
typedef struct tTreeNode { | |
struct tTreeNode *children[2]; | |
int data; | |
} TreeNode; | |
typedef struct tTree { | |
TreeNode *root; | |
} Tree; | |
TreeNode **child_of(TreeNode *parent, ChildKind kind) { | |
return &parent->children[kind]; | |
} | |
Tree *create() { | |
Tree *tree = malloc(sizeof(Tree)); | |
if (tree == NULL) { | |
return NULL; | |
} | |
tree->root = NULL; | |
return tree; | |
} | |
TreeNode **find_place(TreeNode **node, int value) { | |
if ((*node == NULL) || ((*node)->data == value)) { | |
return node; | |
} else { | |
ChildKind kind = (value < (*node)->data) ? LEFT : RIGHT; | |
TreeNode **child = child_of(*node, kind); | |
return find_place(child, value); | |
} | |
} | |
bool contains(Tree *tree, int value) { | |
return *find_place(&tree->root, value) != NULL; | |
} | |
void add(Tree *tree, int value) { | |
TreeNode **node = find_place(&tree->root, value); | |
if (*node == NULL) { | |
TreeNode *new_node = malloc(sizeof(TreeNode)); | |
assert(new_node != NULL); | |
for (ChildKind kind = LEFT; kind <= RIGHT; kind++) { | |
*child_of(new_node, kind) = NULL; | |
} | |
new_node->data = value; | |
*node = new_node; | |
} else { | |
assert((*node)->data == value); | |
} | |
} | |
void print_impl(TreeNode *node, int depth) { | |
if (node != NULL) { | |
for (ChildKind kind = LEFT; kind <= RIGHT; kind++) { | |
print_impl(*child_of(node, kind), depth + 1); | |
if (kind == LEFT) { | |
// it's a binary crunch | |
for (int i = 0; i < depth; i++) { | |
printf(" "); | |
} | |
printf("%d\n", node->data); | |
} | |
} | |
} | |
} | |
void print(Tree *tree) { | |
print_impl(tree->root, 0); | |
} | |
int main() { | |
Tree *tree = create(); | |
add(tree, 5); | |
add(tree, 3); | |
add(tree, 7); | |
add(tree, 1); | |
add(tree, 4); | |
add(tree, 6); | |
add(tree, 8); | |
add(tree, 5); | |
add(tree, 8); | |
print(tree); | |
for (int i = 1; i <= 9; i++) { | |
printf("%d: %s\n", i, contains(tree, i) ? "yes" : "no"); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment