I wrote a template class named "Tree<T>" in C++ which attributes are :
- T data
- std::vector<Tree*> sons;
I wrote the basic methods consisting of writing and reading in those two attributes. Now, I'm writing methods that return the min and max depth.
I have no compilation problems but when I test these methods on an example, I get false values. Here's the code for the minDepth and maxDepth methods (the other methods have names that make clear what they do) :
int numberOfLevels() //we assume that this methode will be called on an initialized node
{
if (nbSons()==0) return 1;
std::vector<int> v;
for (int i=0;i<nbSons();i++) v.push_back(sons[i]->numberOfLevels());
return 1+max_v(v);
}
int maxDepth()
{
return numberOfLevels()-1;
}
int minDepth()
{
if (nbSons()==0) return 0;
std::vector<int> v;
for (int i=0;i<nbSons();i++) v.push_back(sons[i]->minDepth());
return 1+min_v(v);
}
In the main, I define the tree shown in the attached picture, then I call min and max depth methods. Here's the main :
Tree<int>* root=new Tree<int>(1);
root->addAsLastSon(new Tree<int>(2)); // node 0
root->addAsLastSon(new Tree<int>(6)); // node 1
root->addAsLastSon(new Tree<int>(7)); // node 2
// Sons of node 0
(root->getSon(0))->addAsLastSon(new Tree<int>(3)); //node 00
(root->getSon(0))->addAsLastSon(new Tree<int>(4)); //node 01
// Son of node 01
((root->getSon(0))->getSon(1))->addAsLastSon(new Tree<int>(5));
// Sons of node 2
(root->getSon(2))->addAsLastSon(new Tree<int>(8)); //node 20
// Sons of node 20
((root->getSon(2))->getSon(0))->addAsLastSon(new Tree<int>(9)); //node 200
((root->getSon(2))->getSon(0))->addAsLastSon(new Tree<int>(11));
((root->getSon(2))->getSon(0))->addAsLastSon(new Tree<int>(12));
//Son of node 200
(((root->getSon(2))->getSon(0))->getSon(0))->addAsLastSon(new Tree<int>(10));
std::cout<<"Minimum depth : "<<root->minDepth()<<std::endl;
std::cout<<"Maximum depth : "<<root->maxDepth()<<std::endl;
I obtain :
Minimum depth : 1
Maximum depth : 3 (instead of 4)
I can't figure out why.
