Binary Tree ADS

tree.c

/*
 *
 * Principles of programming, coursework 1 [100%]
 * Luke Mitchell - lm0466
 * 08/12/2011
 *
 */
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "tree.h"
 
#define DEBUG
#undef DEBUG
 
/* Data specific procedures */
 
// finds the node with n as the name
// returns null on failure
tree_node_t* search_tree (tree_t *t, phonebook_entry_t *n)
{
    #ifdef DEBUG
        printf ("SEARCH_TREE: checking for empty tree\r\n");
    #endif
 
    // ensure tree is not empty
    if (t->curr == NULL)
        return NULL;
 
    char *nname;
    char *tname;
 
    #ifdef DEBUG
        printf ("SEARCH_TREE: resetting tree\r\n");
    #endif
 
    // reset the tree to the root node
    tree_reset(t);
 
    #ifdef DEBUG
             printf ("SEARCH_TREE: Uppercasing \'%s\'...", n->name);
        #endif
     
    // uppercase the string we're searching for
    nname = calloc (1, (strlen(n->name) + 1));
    strcpy (nname, n->name);
        string_uppercase (nname);
 
    #ifdef DEBUG
        printf ("ok\r\n");
    #endif
 
        while (1) // somewhere in this loop the nname data gets junk appended to it
        {
        // allocate some memory
        // calloc zeros this
        tname = calloc (1, (strlen(t->curr->data->name) + 1));
 
        #ifdef DEBUG
            printf ("SEARCH_TREE: Uppercasing \'%s\'...", t->curr->data->name);
        #endif
 
        strcpy (tname, t->curr->data->name);
        string_uppercase (tname);
 
        #ifdef DEBUG
            printf ("ok\r\n");
                        printf ("SEARCH_TREE: looking for \'%s\', current node value is \'%s\'\r\n", nname, tname);
                #endif
 
                if (less_than(nname, tname))
        {
            #ifdef DEBUG
                            printf ("SEARCH_TREE: \'%s\' is less than  \'%s\'\r\n", nname, tname);
                #endif
 
                        if (advance_tree_left (t))
                                break;
                }
 
        if (greater_than(nname, tname))
        {
            #ifdef DEBUG
                                printf ("SEARCH_TREE: \'%s\' is greater than  \'%s\'\r\n", nname, tname);
                        #endif
 
                        if (advance_tree_right (t))
                                break;
        }
 
        if (equal_to(nname, tname))
        {
            #ifdef DEBUG
                                printf ("SEARCH_TREE: \'%s\' is equal to  \'%s\'\r\n", nname, tname);
                        #endif
 
            return t->curr;
        }
         
        free (tname);
        }
 
    #ifdef DEBUG
            printf ("SEARCH_TREE: couldn't find \'%s\'\r\n", n->name);
    #endif
 
        return NULL;
}
 
// See search_tree, but using a char instead of phone_entry_t
tree_node_t* search_tree_for_name (tree_t *t, char *n)
{
    tree_node_t* tn;
 
    phonebook_entry_t* pe = malloc (sizeof(phonebook_entry_t));
    strcpy (pe->name, n);
 
    #ifdef DEBUG
        printf ("SEARCH_TREE_FOR_NAME: calling search_tree\r\n");
    #endif
     
    tn = search_tree (t, pe);
    free (pe);
     
    return tn;
}
 
// Adds a node to the tree, with the data specified
void add_tree_node (tree_t *t, phonebook_entry_t *data)
{
    tree_node_t* n = malloc (sizeof(tree_node_t));
     
    n->data = data;
    n->left = NULL;
    n->right = NULL;
 
    #ifdef DEBUG
        printf ("ADD_TREE_NODE: adding node with name \'%s\' and a number \'%s\'\r\n", n->data->name, n->data->number.start->data);
    #endif
 
    tree_reset (t);
 
    // first node added?
    if (t->root == NULL)
    {
        t->root = n;
    }
    else
    {
        while (1)
        {
            #ifdef DEBUG
                            printf ("ADD_TREE_NODE: current node is \'%s\'\r\n", t->curr->data->name);
                        #endif
 
            if (greater_than (data->name, t->curr->data->name))
            {
                if (t->curr->right == NULL)
                {
                    #ifdef DEBUG
                        printf ("ADD_TREE_NODE: adding node to the right\r\n");
                    #endif
     
                    t->curr->right = n;
                    break;
                }
                else
                {
                    #ifdef DEBUG
                        printf ("ADD_TREE_NODE: advancing node to the right\r\n");
                    #endif
 
                    advance_tree_right (t);
                }
            }
            else // less than or equal to
            {
                if (t->curr->left == NULL)
                {
                    #ifdef DEBUG
                                                printf ("ADD_TREE_NODE: adding node to the left\r\n");
                                        #endif
                     
                    t->curr->left = n;
                    break;
                }
                else
                {
                    #ifdef DEBUG
                        printf ("ADD_TREE_NODE: advancing node to the left\r\n");
                    #endif
 
                    advance_tree_left (t);
                }
            }
        }
    }
 
    n->parent = t->curr;  
    t->curr = n;
}
 
// Returns 1 on equal to,
// returns 0 on !equal to
int equal_to (char* a, char* b)
{
    return (strcmp (a, b) == 0) ? 1 : 0;
}
 
// Returns 1 on less than
// returns 0 on greater than or equal to
int less_than (char *a, char *b)
{
    return (strcmp (a, b) < 0) ? 1 : 0;
}
 
// Returns 1 on greater than
// returns 0 on less than or equal to
int greater_than (char *a, char *b)
{
    return (strcmp (a, b) > 0) ? 1 : 0;
}
 
/* Data independant procedures */
 
// Creates an empty tree
// returns a pointer to it
tree_t* create_tree ()
{
    tree_t* t = malloc (sizeof(tree_t));
    t->root = NULL;
    t->curr = NULL;
    return t;
}
 
// Destroys a tree
// and frees all the memory from the nodes
void destroy_tree (tree_t *t)
{
    // free tree nodes  
    // todo
    // 1 advance left until leaf
    // 2 remove leaf
    // 3 retreat to parent
    // 4 advance right if possible
    // 5 go to (1)
 
    // free tree itself
    free (t);
}
 
// Determines if node n is a leaf (no left and right pointer)
// returns 1 on leaf, 0 on not leaf
int is_leaf (tree_node_t *n)
{
    return (n->left == NULL && n->right == NULL) ? 1 : 0;
}
 
// Resets the current pointer to the root node
void tree_reset (tree_t *t)
{
    t->curr = t->root;
}
 
// Removes a node from the tree
// does nothing if n isn't found
void rem_tree_node (tree_t *t, tree_node_t *n)
{
    // is n in t?
    if (search_tree (t, n->data) == NULL)
        return;
 
    // is n a root node
    if (n->parent == NULL)
    {
        if (is_leaf (n))
        {
            // root node of an otherwise empty tree
            t->root = NULL;
            t->curr = NULL;
        }
        else
        {
            // rearrange somehow
            // todo 
        }
    }
    else
    {
        // leaf?
        if (is_leaf (n))
        {
            if (n->parent->left == n)
                n->parent->left = NULL;
            else
                n->parent->right = NULL;
        }
        else
        {
            if (n->parent->left == n)
                n->parent->left = n->left;
            else
                n->parent->right = n->right;
        }
    }
 
    free (n);
}
 
// Advances the current pointer to the left
// returns 0 on success, -1 when a a node with no ->left is reached
int advance_tree_left (tree_t *t)
{
    if (t->curr->left == NULL)
        return -1;
    else
        t->curr = t->curr->left;
 
    return 0;
}
 
// Advances the current pointer to the right
// returns 0 on success, -1 when a node with no ->right is reached
int advance_tree_right (tree_t *t)
{
    if (t->curr->right == NULL)
        return -1;
    else
        t->curr = t->curr->right;
 
    return 0;
}
 
// Retreats the current pointer to the previous node
// returns 0 on success, -1 when the root is reached
int retreat_tree (tree_t *t)
{
    if (t->curr->parent == t->root)
        return -1;
    else
        t->curr = t->curr->parent;
 
    return 0;
}
 
/* Misc. procedures */
 
// Converts a char array to uppercase
void string_uppercase (char* str)
{
    int i;
     
    for (i = 0; i < (strlen(str) + 1); i++)
        str[i] = toupper (str[i]);
}

tree.h

/*
 *
 * Principles of programming, coursework 1 [100%]
 * Luke Mitchell - lm0466
 * 08/12/2011
 *
 */
 
#ifndef TREE_H
#define TREE_H

// See https://gist.github.com/lukem512/1b009ff0b06877662d4d 
#include "list.h"
 
#define MAX_STR_LENGTH 32
 
// data type
typedef struct phonebook_entry {
        char    name[MAX_STR_LENGTH];
        list    number;
} phonebook_entry_t;
 
typedef struct tree_node {
    phonebook_entry_t *data; // Data specific member
    struct tree_node *parent, *left, *right;
} tree_node_t;
 
typedef struct tree {
    tree_node_t *root;
    tree_node_t *curr;
} tree_t;
 
// Data-specific procedures
tree_node_t* search_tree (tree_t *, phonebook_entry_t *);
tree_node_t* search_tree_for_name (tree_t *, char *);
void add_tree_node (tree_t *, phonebook_entry_t *);
int equal_to (char *, char *);
int less_than (char *, char *);
int greater_than (char *, char *);
 
// Data-independant procedures 
tree_t* create_tree ();
void destroy_tree (tree_t *);
void tree_reset (tree_t *t);
void rem_tree_node (tree_t *, tree_node_t *);
int advance_tree_left (tree_t *);
int advance_tree_right (tree_t *);
int retreat_tree (tree_t *);
 
// Misc procedures
void string_uppercase (char *);
 
#endif