Calcul de la profondeur max et min d'un arbre (pas nécessairement binaire)

[invite2ec0a62b]

Bonsoir à tous,

J'ai créé une classe Tree<T> template. La classe contient deux champs, un pour stocker l'information T data et un pour stocker l'adresse des fils std::vector<Tree*> sons

J'ai codé les fonctions basiques d'affichage et d'écriture dans ces champs.

J'ai aussi essayé d'écrire deux méthodes qui calculent la profondeur max et min de l'arbre. Voici leur implémentation (au sein de la classe donc nul besoin de le rappeler avec les :: ) :

 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);
    }

Je n'ai pas de problèmes de compilation mais quand je teste sur l'arbre dessiné en pièce jointe, la méthode maxDepth me renvoie un mauvais chiffre. Voici le main correspondant :

    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;

Je reçois sur la console :

Minimum depth : 1
Maximum depth : 3 (au lieu de 4)

Je n'arrive pas à comprendre pourquoi. J'ai aussi tester ces méthodes sur un arbre binaire (un arbre tel que chacun de ses noeud possède au plus deux fils), et ça a donné les résultats attendus.
-----

[geometrodynamics_of_QFT]

y'a un truc que je comprends pas...
tu appelles la fonction NumberOfLevel récursivement dans une boucle for???
Pourquoi ce double parcours de l'arbre quand un seul suffit?

[geometrodynamics_of_QFT]

jte conseille d'abandonner la boucle for...surtout en travaillant sur des arbres de dimension inconnue.
Ton code fournit sans doute la dernière valeur obtenue dans le for (branche terminant par 12?)
debug en ralongeant la dernière branche ^^