Tree Template Class Implementation for C++

Question

I have not done any parameter checking, however I think the meat of the class is there. Let me know what you think.

#include <cstddef>
#include <vector>
using namespace std;

template<class T>
class TreeNode {

private:

    T* data;
    TreeNode<T>* parent;
    vector< TreeNode<T>* > children;

public:

    TreeNode(TreeNode<T>* parent, T data);
    ~TreeNode();

    T& getData() const;
    void setData(const T& data);
    void addChild(const T& data);
    void removeChild(const size_t& indx);
    TreeNode<T>* findChild(const T& data) const;
    TreeNode<T>* getChild(const size_t& indx) const;
    TreeNode<T>* getParent() const;
    int getNumChildren() const;

};

template<class T>
TreeNode<T>::TreeNode(TreeNode<T>* parent, T data) : parent(parent) {
    this->data = new T(data);
}

template<class T>
TreeNode<T>::~TreeNode() {
    delete data;
    for(TreeNode<T>* childNode : children)
        delete childNode;
}

template<class T>
T& TreeNode<T>::getData() const {
    return *this->data;
}

template<class T>
void TreeNode<T>::setData(const T& data) {
    *this->data = data;
}

template<class T>
void TreeNode<T>::addChild(const T& data) {
    children.push_back(new TreeNode<T>(this, data));
}

template<class T>
void TreeNode<T>::removeChild(const size_t& indx) {
    children.erase(children.begin()+indx);
}

template<class T>
TreeNode<T>* TreeNode<T>::findChild(const T& data) const {
    for(int i=0; i<children.size(); i++)
        if(children[i]->getData() == data)
            return children[i];
    return NULL;
}

template<class T>
TreeNode<T>* TreeNode<T>::getChild(const size_t& indx) const {
    return children[indx];
}

template<class T>
TreeNode<T>* TreeNode<T>::getParent() const {
    return parent;
}

template<class T>
int TreeNode<T>::getNumChildren() const {
    return children.size();
}

Answer 1

• Do not get in the habit of using using namespace std.

• Since you're using <cstddef> for size_t, you should make it std::size_t for C++.

• Since you define your own destructor, you should also overload the copy constructor and the assignment operator. This is known as The Rule of Three in C++. This is especially important in the case of raw pointers as data members as the compiler-provided copy constructor and assignment operator will only copy the pointer (shallow copy), not the data (deep copy).

  You should also follow Dieter's advice (in the comments): use T data instead of T* data, and remove thenew/delete. Use as little manual memory allocation as possible in C++.

• You're using a range-based for-loop in the destructor, which must mean you're using C++11. Bearing this in mind, one change you should make is using nullptr instead of NULL.

Answer 2

In addition to the suggestions from Jamal, a few other notes to improve your code:

• Avoid superfluous use of this-> in member functions. One way to do this is to avoid using the same name for parameters as for internal variable names. One common idiom is to prepend "internal" class members with an underscore. It makes it easier to see, at a glance, which are member data and which are parameters.

  Compare the original:

  *this->data = data;
  

  to an alternative version:

  _data = data;
  

• Decide whether your container will "own" the contained objects or not. If it is to "own" them, it means that they'll be deleted when the container is deleted (which is what your destructor currently does) but it also means that it should either move or create objects as they're added.

• Consider either exposing the underlying vector or providing a means by which resizing might be avoided. As it is currently written, the std::vector inside each TreeNode is dynamically resized when needed as each child node is added. This can create undesirable performance problems if, for example, it were known that each node had no more than three children, it would be nice to be able to invoke children.reserve(3).

• Consider adding move constructors for performance gain.

• Consider adding iterators to do common tree things such as in-order, pre-order and post-order tree traversal.