6
\$\begingroup\$

My implementation of BST. Critique will be appreciated!

#include <iostream>
template <class T>
class Node {

    template <class X>
    friend class BST;
    template <class X>
    friend void clear(Node<X> *root);
    template <class X>
    friend bool search(const Node<X> *root, const X x);
    template <class X>
    friend Node<X>* to_add(Node<X> *root, const X x);
    template <class X>
    friend std::ostream& preorder(std::ostream& ss, Node<X> *root);
    template <class X>
    friend std::ostream& postorder(std::ostream& ss, Node<X> *root); 

    T data;
    Node<T> *left;
    Node<T> *right;

    Node(): data(), left(nullptr), right(nullptr) { }
    Node(T dt): data(dt), left(nullptr), right(nullptr) { }

    T get() const { return data; }
};

template<class T>
void clear(Node<T> *root);

template <class T>
class BST {
    template <class X>
    friend void clear(Node<X>* root);
    template <class X>
    friend std::ostream& bst_preorder(std::ostream& ss, BST<X>& tree);
    template <class X>
    friend std::ostream& bst_postorder(std::ostream& ss, BST<X>& tree);

    Node<T> *root;

public:
    BST(): root(nullptr) { }
    BST(Node<T> *n): root(n) { }
    ~BST() {
        clear(root);
    }

    bool in_tree(T x) const;
    BST<T>& insert(T x);
};

template<class T>
void clear(Node<T>* root) {
    if (root) {
        if (root->left) {
            clear(root->left);
        }
        if (root->right) {
            clear(root->right);
        }
        delete root;
    }
}


template<class T>
bool search(const Node<T>* root, const T x) {
    if (root) {
        if (x == root->data) 
            return true;
        else if (x < root->data) 
            return search(root->left, x);
        else 
            return search(root->right, x);
    }

    else
        return false;
}

template<class T>
bool BST<T>::in_tree(const T x) const {
    return search(root, x);
}

template<class T>
Node<T>* to_add(Node<T> *root, const T x) {
    if (root->left == nullptr && root->data > x)
        return root;
    else if (root->right == nullptr && root->data < x)
        return root;
    else if (root->data > x)
        return to_add(root->left, x);
    else if (root->data < x)
        return to_add(root->right, x);
    else
        return nullptr;
}

template<class T>
BST<T>& BST<T>::insert(const T x) {
    Node<T>* temp = new Node<T>(x);

    if (!root)
        root = temp;
    else {
        Node<T>* correct = to_add(root, x);
        if (correct) {
            if (correct->data > x)
                correct->left = temp;
            else 
                correct->right = temp;
        }
    }

    return *this;
}

template <class T>
std::ostream& preorder(std::ostream& ss, Node<T>* root) {
    ss << root->data << " ";
    if (root->left) 
        preorder(ss, root->left);
    if (root->right)
        preorder(ss, root->right);

    return ss;
}

template<class T>
std::ostream& bst_preorder(std::ostream& ss, BST<T>& tree) {
    if (tree.root) {
        return preorder(ss, tree.root);
    }

    return ss;
}

template<class T>
std::ostream& postorder(std::ostream& ss, Node<T>* root) {
    if (root->left)
        postorder(ss, root->left);
    if (root->right)
        postorder(ss, root->right);

    ss << root->data << " ";

    return ss;
}

template<class T>
std::ostream& bst_postorder(std::ostream&& ss, BST<T>& tree) {
    if (tree.root) {
        return postorder(ss, tree.root);
    }

    return ss;
}
\$\endgroup\$

1 Answer 1

6
\$\begingroup\$

The main thing I can think of, is that anyone using the BST class, shouldn't have to know what a Node is. The user should just be adding a value, searching for a value, etc.in the BST class. With this in mind, I would suggest keeping the Node class a private member of BST, and all the functions, add,search, etc. should be members of BST.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.