1  #ifndef TREE_H
  2  #define TREE_H
  3  
  4  #include <vector>
  5  using namespace std;
  6  
  7  class Tree
  8  {
  9  public:
 10    // Construct an empty tree 
 11    Tree()
 12    {
 13    }
 14  
 15    // Construct a tree with root, parent, and searchOrder 
 16    Tree(int root, vector<int>& parent, vector<int>& searchOrders)
 17    {
 18      this->root = root;
 19      this->parent = parent;
 20      this->searchOrders = searchOrders;
 21    }
 22  
 23    // Return the root of the tree 
 24    int getRoot() const
 25    {
 26      return root;
 27    }
 28  
 29    // Return the parent of vertex v 
 30    int getParent(int v) const
 31    {
 32      return parent[v];
 33    }
 34  
 35    // Return search order 
 36    vector<int> getSearchOrders() const
 37    {
 38      return searchOrders;
 39    }
 40  
 41    // Return number of vertices found 
 42    int getNumberOfVerticesFound() const
 43    {
 44      return searchOrders.size();
 45    }
 46  
 47    // Return the path of vertices from v to the root in a vector 
 48    vector<int> getPath(int v) const
 49    {
 50      vector<int> path;
 51  
 52      do
 53      {
 54        path.push_back(v);
 55        v = parent[v];
 56      }
 57      while (v != -1);
 58  
 59      return path;
 60    }
 61  
 62    // Print the whole tree 
 63    void printTree() const
 64    {
 65      cout << "Root is: " << root << endl;
 66      cout << "Edges: ";
 67      for (unsigned i = 0; i < searchOrders.size(); i++) 
 68      {
 69        if (parent[searchOrders[i]] != -1) 
 70        {
 71          // Display an edge
 72          cout << "(" << parent[searchOrders[i]] << ", " <<
 73            searchOrders[i] << ") ";
 74        }
 75      }
 76      cout << endl;
 77    }
 78  
 79  private:
 80    int root; // The root of the tree
 81    vector<int> parent; // Store the parent of each vertex
 82    vector<int> searchOrders; // Store the search order
 83  };
 84  #endif