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

• Facebook
• Google+
• Linkedin
• Blogspot
• Google-Code
• Github
• YouTube
• Twitter

Read More..

A skill based approach to creating open online courses

Posted by Sean Lip, Software Engineer, Open Online Education

Google has offered a number of open online courses in the past two years, and some of our recent research highlights the importance of having effective and relevant activities in these courses. Over the past decade, the Open Learning Initiative (OLI) at Carnegie Mellon, and now at Stanford, has successfully offered free open online courses that are centered around goal-directed activities that provide students with targeted feedback on their work. In order to improve understanding about how to design online courses based around effective activities, Google and OLI recently collaborated on a white paper that outlines the skill-based approach that OLI uses to create its courses.

OLI courses are focused around a set of learning objectives which identify what students should be able to do by the time they have completed a course module. These learning objectives are broken down into skills, and individual activities in the course are aimed towards developing students’ mastery with these skills. A typical activity from the Engineering Statics course is shown below:

During the course, students’ attempts at questions related to a particular skill are then fed as inputs into a probabilistic model which treats the degrees of mastery for each skill as mathematically independent variables. This model estimates how likely a student is to have mastered individual skills, and its output can help instructors determine which students are struggling and take appropriate interventions, as well as inform the design of future versions of the same course. The paper also outlines the advantages and limitations of the existing system, which could be useful starting points for further research.

We hope that this white paper provides useful insight for creators of online courses and course platforms, and that it stimulates further discussion about how to help people learn online more effectively.

Read More..