Minimalist Tree

Question

While working on a small project, I tried to implement a super simple tree class in C++. It supports an arbitrary number of branches from each node.

In addition to general comments, my main concerns are:

• Are there other common tree functions that should be implemented? (So far I know about traversal and search, but I don't think I'll need them for my project.)
• Can this class leak memory?
• How can I write good unit tests?

Tree.h:

#ifndef Tree_h
#define Tree_h

#include<vector>

// Templated tree class
template <typename T>
class Tree {

  public:

    // Child nodes
    std::vector<Tree<T> *> branches;

    // Top datum
    T leaf;

    // Constructor from element
    Tree<T>(const T & leaf_in) : leaf(leaf_in) { }

    // Copy constructor (deep copy)
    Tree<T>(const Tree<T> & tree_in) {
      cloneTree(this, tree_in);
    }

    // Overloaded assignment operator
    Tree<T> & operator=(const Tree<T> & tree_in) {
      // Do nothing if called on itself
      if (this == & tree_in) {
        return * this;
      }
      // Delete this tree
      chopTree();
      // Copy the other tree in its place
      cloneTree(this, tree_in);
      return * this;
    }

    // Grow function
    // Modifies heap
    void grow(const T & leaf) {
      Tree * branch = new Tree(leaf);
      branches.push_back(branch);
    }

    // Destructor
    ~Tree<T>() {
      chopTree();
    }

  private:

    // Cleans up heap from grow function
    // Recursively called on each branch
    void chopTree() {
      for (auto branch : branches) {
        branch->chopTree();
        delete branch;
        branch = 0;
      }
      branches.clear();
    }

    // Copies all of another tree's items into this tree
    // Requires that other != this
    void cloneTree(Tree<T> * self, const Tree<T> & other) {
      self->leaf = other.leaf;
      // copy the leaves
      for (auto branch : other.branches) {
        self->grow(branch->leaf);
      }
      // copy the branches
      for (int i = 0; i < self->branches.size(); ++i) {
        cloneTree(self->branches.at(i), * other.branches.at(i));
      }
    }
};

#endif // Tree_h

Note: There are several other C++ Tree questions, but I didn't find the answers I was looking for. In case there is a duplicate question that I missed, let me know in the comments, and I'll delete the question.

Answer 1

Collections in C++ are a subject that has often be studied. There are many things you could improve to your tree data structure:

• First of all, it doesn't have a default constructor. I tried to write Tree<int> tree; and got a compile-time error. Consider making your tree default-constructible and thus consider the fact that some trees can be empty, which means that they could also have an empty or is_empty method (default-constructing a tree with anything else than an empty state would probably be a gate to a whole new class of errors). Have a look at the proposal N3700 - Hierarchical Data Structures and Related Concepts for the C++ Standard Library for a concrete example of well-designed tree data structures.

• Instead of raw pointers, consider using std::unique_ptr to store yur branches. This will make your code safer with regards to exception safety. It also means that you can get rid of chopTree and of the constructor altogether: when the constructor generated by the compiler will be called, it will destruct branches, which will destruct every Tree object stored recursively. That said, it also means that you have to implement other functions differently, for example, grow will have to use std::make_unique:

  void grow(const T & leaf) {
    auto branch = std::make_unique<Tree<T>>(leaf);
    branches.push_back(std::move(branch));
  }
  

• operator= should be implemented in terms of copy-and-swap idiom to simplify the code and to guard it against spurious exception problems:

  Tree<T> & operator=(Tree<T> other) {
      std::swap(*this, other);
      return *this;
  }
  

  Now, you use cloneTree only once, so you can actually put its code into the copy constructor.

• You can create a move constructor to improve the behaviour of std::swap:

  Tree(Tree && other) :
      branches(std::move(other.branches)),
      leaf(std::move(other.leaf))
  {}
  

  You can also add a similar move assignment operator, but its exact implementation will be left as an exercice to the reader.

• As long as you are inside the class definition, you can use Tree instead of Tree<T>. This is known as the injected class name and solves tricky name shadowing problems. Most of the time we use it mostly because it is terser and convenient as well as reducing the refactoring cost when we need to modify the template parameters of the class.