Thursday, November 3, 2016

Creating a templated Binary Search Tree Class in C

Creating a basic template Tree Class in C++
(Works in Linux and Windows)

If you just want the code and not the walkthrough, it is attached at the end (I use the GNU GPL license, so do whatever you want with the code as long as you mention me).

There a multiple benefits of creating a Tree class based on a template. With a template, the tree can be a container for anything while still being fairly clean code. We will also create this class to be easily inherited for other trees such as an AVL and Huffman tree (which we will implement later).

A tree is a widely used data structure which organizes a set of nodes containing data. More can be found on it here: http://en.wikipedia.org/wiki/Tree_%28data_structure%29

This tree will be a Binary Search Tree; however, it will be easily inheritable so that other trees (Binary trees, such as AVL and Red-Black) can be defined based on it.

First we will set up our Node as a holder for the data and tree information such as the parent and connected nodes (the leaves). I overload the < operator so that we can search and sort this tree using the c++ algorithm include if we so desire.

template <class T>
class Node {
public:
    T data;
    Node *left, *right, *parent;

    Node() {
        left = right = parent = NULL;
    };
    Node(T &value) {
        data = value;
    };
    ~Node() {
    };   
    void operator= (const Node<T> &other) {
        data = other.data;
    };
    bool operator< (T &other) {
        return (data < other);
    };
};

Our tree will basically just be a bunch of these Nodes pointing to each other, with some functions to manage the data structure.

template <class T>
class Tree {
public:
    Tree() {
        root = NULL;
    };

    ~Tree() {
        m_destroy(root);
    };

    //We will define these all as virtuals for inherited trees (like a Huffman Tree and AVL Tree shown later)
    virtual void insert(T &value) {
        m_insert(root,NULL,value);
    };
    virtual Node<T>* search(T &value) {
        return m_search(root,value);
    };
    virtual bool remove(T &value) {
        return m_remove(root,value);
    };
    virtual bool operator< (Tree<T> &other) {
        return (root->data < other.first()->data);
    };
    void operator= (Tree<T> &other) {
        m_equal(root,other.first());
    };
    Node<T>*& first() {
        return root;
    };


protected:
    //this will be our root node and private functions
    Node<T> *root;
    void m_equal(Node<T>*& node, Node<T>* value) {
        if(value != NULL) {
            node = new Node<T>();
            *node = *value;
            if(value->left != NULL)
                m_equal(node->left, value->left);
            if(value->right != NULL)
                m_equal(node->right, value->right);
        }
    }

    void m_destroy(Node<T>* value) {
        if(value != NULL) {
            m_destroy(value->left);
            m_destroy(value->right);
            delete value;
        }
    };
    void m_insert(Node<T> *&node, Node<T> *parent, T &value) {
        if(node == NULL) {
            node = new Node<T>();
            *node = value;
            node->parent = parent;
        } else if(value < node->data) {
            m_insert(node->left,node,value);
        } else
            m_insert(node->right,node,value);
    };
    void m_insert(Node<T> *&node, Node<T> *parent, Tree<T> &tree) {
        Node<T> *value = tree.first();
        if(node == NULL) {
            node = new Node<T>();
            *node = *value;
            node->parent = parent;
        } else if(value->data < node->data) {
            m_insert(node->left,tree);
        } else
            m_insert(node->right,tree);
    };
    Node<T>* m_search(Node<T> *node, T &value) {
        if(node == NULL)
            return NULL;
        else if(value == node->data)
            return node;
        else if(value < node->data)
            return m_search(node->left,value);
        else
            return m_search(node->right,value);
    };

    bool m_remove(Node<T> *node, T &value) {
        //messy, need to speed this up later
        Node<T> *tmp = m_search(root,value);
        if(tmp == NULL)
            return false;
        Node<T> *parent = tmp->parent;
        //am i the left or right of the parent?
        bool iamleft = false;
        if(parent->left == tmp)
            iamleft = true;
        if(tmp->left != NULL && tmp->right != NULL) {
            if(parent->left == NULL || parent->right == NULL) {
                parent->left = tmp->left;
                parent->right = tmp->right;
            } else {
                if(iamleft)
                    parent->left = tmp->left;
                else
                    parent->right = tmp->left;
                T data = tmp->right->data;
                delete tmp;
                m_insert(root,NULL,data);
            }
        } else if(tmp->left != NULL) {
            if(iamleft)
                parent->left = tmp->left;
            else
                parent->right = tmp->left;
        } else if(tmp->right != NULL ) {
            if(iamleft)
                parent->left = tmp->right;
            else
                parent->right = tmp->right;
        } else {
            if(iamleft)
                parent->left = NULL;
            else
                parent->right = NULL;
        }
        return true;
    };
};

And thats all we need for a basic binary search tree. The full code is shown below

Tree.h 

Consider donating to further my tinkering.


Places you can find me

Related Post:

Posted by graba at 1:55 AM
Labels: , , , , , , , , ,

0 comments:

Post a Comment

Subscribe to: Post Comments (Atom)
 
Copyright 2009 Information Blog
Powered By Blogger