In C Write an implementation of the set class with associate

In C++

Write an implementation of the set class, with associated iterators using a binary search tree.

Add to each node a link to the next smallest and next largest node.

Note: To make your code simpler, add a header and tail node which are not part of the binary search tree but help make the linked list part of the code simpler

please don\'t copy the code from the other questions in Chegg because they all wrong. Thanks.

Solution

template <typename T>

struct TreeNode {

    T data;

    TreeNode *left, *right, *parent;

    ~TreeNode() {

        delete left;

        delete right;

        parent = 0;

    }

};

template <typename T>

class BSTreeSet {

    /*friend ostream& operator<<(ostream& out, const BSTreeSet<T> BST) {

        BST.inorderPrint(out);

        return out;

    }*/

    public:

        BSTreeSet();

        BSTreeSet(T initRoot);

        ~BSTreeSet() { delete root; }

        bool insert(T obj);

        void remove(T obj);

        bool contains(T obj);

        bool isEmpty() const { return root == NULL; };

        void inorderPrint(ostream& out);

    private:

        bool insertHelper(TreeNode<T> *node, T obj);

        void removeHelper(TreeNode<T> *node, T obj);

        bool containsHelper(TreeNode<T> *node, T obj);

        void IOPrint(TreeNode<T> *node, ostream& out);

        TreeNode<T> *root;

};

template <typename T>

void BSTreeSet<T>::remove(T obj) {

    return removeHelper(root, obj);

}

template <typename T>

void BSTreeSet<T>::removeHelper(TreeNode<T> *node, T obj) {

    if (node == NULL) return;

    if (node->data < obj) removeHelper(node->right, obj);

    else if (node->data > obj) removeHelper(node->left, obj);

    else if (node->left != NULL && node->right != NULL) {

        TreeNode<T> *temp = node->right;

        while (temp->left != NULL) temp = temp->left;

        node->data = temp->data;

        removeHelper(temp, temp->data);

    } else {

        TreeNode<T> *old = node;

        node = (node->left != NULL) ? node->left : node->right;

        delete old;

    }

}