All pastes #430421 Raw Edit

Untitled

public cpp v1 · immutable
·published 2007-04-08 23:40 UTC
rendered paste body
#include <functional>template< typename T, typename Compare=std::less<int> >class BinaryTree {  private:    struct BTNode {        BTNode(const T &value) : value(value){}        const T &value;        BTNode *left, *right;    };    BTNode *root;  public:    BinaryTree(){root=0;}    ~BinaryTree(){};    void insert(const T&val) {        BTNode *node = new BTNode(val);        if (root)            insert(node, root);        else            root = node;    }    void remove(const T&val) {        BTNode * parent = 0, node = root, tmp;        //Loops until node is null or val == node->value        while (node && (Compare(val,node->value) || Compare(node->value,val))) {            tmp = node;            node = Compare(val, node->value) ? node->left : node->right;            parent = tmp;        }        if (!node)            return;        tmp = remove(node);        if (parent) {            if (parent->left == node)                parent->left = tmp;            else                parent->right = tmp;        }        else            root = tmp;        delete node;    }  private:    /**     * Inserts node into parents tree     */    void insert(BTNode * node, BTNode * parent) {        if ( Compare(node->value,parent->value) ) { //node < parent            if ( parent->left )                insert(node, parent->left);            else                parent->left = node;        }        else {            if ( parent->right )                insert(node, parent->right);            else                parent->right = node;        }    }    /**     * @return A pointer to the node to replace with     */    BTNode *remove(BTNode * node) {        if (node->left) {            if (node->right)                insert(node->right, node->left);            return node->left;        }        else if (node->right)            return node->right;        return 0;    }};