Example of a Binary Tree

I can't remember where I got this code sample from, but I found it to be a good one for understanding b-trees.

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// our data structure (a binary tree node)
typedef struct node{
int data;
struct node* left;
struct node* right;
} node;


// initializes a node struct
node* newNode(int data){
node *node;
node = malloc(sizeof(node));
if (node != NULL){
node->data = data;
node->left = NULL;
node->right = NULL;
}
return(node);
}


// inserts a node into the btree
node* insert(node *node, int data){
if(node == NULL) {
return (newNode(data));
}else{
if(data <= node->data){
node->left = insert(node->left, data);
}else{
node->right = insert(node->right, data);
}
}
return (node);
}

// retreives a node, by it's data
int lookup(node *node, int target) {
if(node == NULL){
return 0;
}else{
if(target == node->data){
return 1;
}else{
if (target < node->data){
return (lookup(node->left, target));
}else{
return (lookup(node->right, target));
}
}
}
}

// prints each item in the btree
void traverse(node *node){
if(node == NULL){
return;
}

printf("data: %i\n", node->data);

if(node->left){
traverse(node->left);
}

if(node->right){
traverse(node->right);
}
}


// releases the entire btree
void empty(node *node){
if(node == NULL){
return;
}

if(node->left){
empty(node->left);
}

if(node->right){
empty(node->right);
}

printf("releasing item %i\n", node->data);
free(node);
}



int main(int argc, char *argv[], char *env[]){
node *root_node;
root_node = insert(NULL, 5);
insert(root_node,7);
insert(root_node,2);
insert(root_node,1);
insert(root_node,10);

printf("3 is in the btree: %s\n", (lookup(root_node,3) == 1 ? "YES" : "NO"));
printf("2 is in the btree: %s\n", (lookup(root_node,2) == 1 ? "YES" : "NO"));


traverse(root_node);

empty(root_node);

return 0;
}