Skip to content

Instantly share code, notes, and snippets.

@hosaka
Created August 10, 2015 16:33
Show Gist options
  • Save hosaka/ae58f6a00c9621c74a3b to your computer and use it in GitHub Desktop.
Save hosaka/ae58f6a00c9621c74a3b to your computer and use it in GitHub Desktop.
Most simple binary tree implementation in C
#include <stdio.h>
#include <stdlib.h>
// node structure
typedef struct node_s
{
int value;
struct node_s *lnode;
struct node_s *rnode;
} node_t;
// compare nodes values
int tree_compare_nodes(node_t *lnode, node_t *rnode)
{
if ( lnode->value < rnode->value )
{
return -1;
}
else if ( lnode->value > rnode->value )
{
return 1;
}
else
{
return 0;
}
}
// insert node into the tree
void tree_insert_node (int val, node_t **tree)
{
// create new node if doesn't exist
if ( *tree == NULL )
{
*tree = malloc( sizeof(node_t) );
(*tree)->value = val;
(*tree)->lnode = NULL;
(*tree)->rnode = NULL;
return;
}
// insert on the left if smaller
if ( (*tree)->value < (*tree)->value )
{
tree_insert_node(val, &(*tree)->lnode);
}
// insert on the right if bigger
else if ( (*tree)->value > (*tree)->value )
{
tree_insert_node( val, &(*tree)->rnode);
}
}
// locate a node in the tree
node_t *tree_search_node (int val, node_t *tree)
{
if (tree != NULL)
{
if (val == tree->value)
{
return tree;
}
else if (val < tree->value)
{
return tree_search_node(val, tree->lnode);
}
else
{
return tree_search_node(val, tree->rnode);
}
}
else
{
return NULL;
}
}
void tree_traverse(node_t *tree)
{
if ( tree->lnode )
{
tree_traverse(tree->lnode);
}
printf("%d\n", tree->value);
if ( tree->rnode )
{
tree_traverse(tree->rnode);
}
}
// deconstruct the tree
void tree_destruct (node_t *tree)
{
if (tree != NULL)
{
tree_destruct(tree->lnode);
tree_destruct(tree->rnode);
free(tree);
}
}
int main (int argc, char *argv)
{
node_t *tree = NULL;
tree_insert_node(50, &tree);
tree_insert_node(25, &tree);
tree_insert_node(100, &tree);
tree_insert_node(20, &tree);
tree_traverse(tree);
tree_destruct(tree);
return EXIT_SUCCESS;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment