Martin Broadhurst > Data Structures
Binary tree
Contents
Introduction
This is an unbalanced binary tree.
Creation
Create with MBbinarytree_create.
It is passed a pointer to a comparison function with the same return value behaviour as strcmp.
Adding elements
Add elements with MBbinarytree_add.
The tree behaves like a set, not allowing duplicates, and if an element is added that compares equal to an existing element, it replaces it and the existing element is returned.
Removing elements
Remove elements with MBbinarytree_remove.
Accessing elements
Find elements with MBbinarytree_find.
Example
#include <stdio.h>
#include <string.h>
#include <binarytree.h>
int main(void)
{
MBbinarytree * tree;
char * elements[] = {"D", "B", "C", "F", "E", "G", "A"};
const unsigned int n = sizeof(elements) / sizeof(const char*);
unsigned int i;
const char * data;
tree = MBbinarytree_create((MBcmpfn)strcmp);
for (i = 0; i < n; i++) {
MBbinarytree_add(tree, elements[i]);
}
MBbinarytree_for_each(tree, (MBforfn)puts);
printf("Size is %d\n", MBbinarytree_get_count(tree));
for (i = 0; i < n; i++) {
data = MBbinarytree_find(tree, elements[i]);
if (data) {
printf("Found %s\n", data);
}
else {
printf("Couldn't find %s\n", elements[i]);
}
}
for (i = 0; i < n; i++) {
printf("Removing %s\n", elements[i]);
data = MBbinarytree_remove(tree, elements[i]);
if (data) {
printf("%s successfully removed\n", data);
}
else {
printf("Couldn't find %s\n", elements[i]);
}
printf("Size is now %d\n", MBbinarytree_get_count(tree));
}
MBbinarytree_delete(tree);
return 0;
}
Source code
Download
The following archives contain the full source code, example programs and build instructions for all of the data structures:
Articles