Discussion :

[alex2746]

Bonjour,
J'ai une méthode qui reçoit en paramètres un arbre naire d'entier et deux entiers et qui doit me retourner la longueur du chemin entre ces deux noeuds (donc le nombre d'arêtes). Je peux utiliser tout ce que je veux (récursivité, backtrack, etc si nécessaire) mais je n'y arrive pas... J'ai aussi accès à toutes les méthodes "normales" d'un arbre et d'un noeud: getRacine(), getValeur(), getGauche(), getDroit(), ...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
public int longChemin(Arbre<int> arbre, int noeudA, int noeudB){
 
}

Exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
                              1
 
                    3                   2
 
               7   8   5           4      6
 
                                    9
 
(3 et 2 sont fils de 1)
(7, 8 et 5 sont fils de 3)
(4 et 6 sont fils de 2)
(9 est fils de 4)

Pour cet exemple, si on fournit:
-> 8 et 4, retourner 4
-> 3 et 2, retourner 2
-> 9 et 6, retourner 3
etc

Pouvez-vous m'aider? Merci d'avance.

[Rei Ichido]

Personnellement, je ferai quelque chose du genre :

Pour noeudA et noeudB, je génère la liste des parents.
Je vérifie ensuite si noeudA est dans listeParentsB ou le contraire ; dans ce cas le calcul est immédiat, c'est l'index de position dans la liste.
Sinon, je parcoure listeParentsA jusqu'à trouver un élément qui existe dans listeParentsB : c'est le premier parent commun, et il n'y a plus qu'à faire la somme des indices de sa position dans les deux listes (monter/redescendre).

[hwoarang]

Salut,

D'apres ton graphique, le noeud 3 a 3 fils. C'est normal?

Ensuite, pour trouver le plus court chemin, tu peux, comme cela t'a été suggéré, construire la hiérarchie de A, construire la hiérarchie de B puis chercher le premier element commun.
Exemple entre 8 et 4:
Pour 8 : 8 -> 3 ->1
Pour 4 : 4 -> 2 -> 1
Premier element commun : 1. Ca fait donc 4 transitions.

Exemple entre 9 et 6:
Pour 9 : 9 -> 4 -> 2 ->1
Pour 6 : 6 -> 2 -> 1
Premier element commun : 2. Ca fait donc 3 transitions.
L'avantage de cette solution est que la hiérarchie d'un noeud pourra éventuellement t'aider pour un prochain calcul.

Sinon, une autre option plus spécialisée serait de parcourir l'arbre a la recherche du noeud ou on ne prendrait pas le meme chemin pour A et B. Une fois trouvé, il faut additionner la profondeur de A et la profondeur de B à partir de ce noeud.
Cette méthode est plus optimisée (moins de recherche et moins d'information à remonter) mais étant très spécialisée, il y a moins de chance qu'elle te serve pour un autre probleme).

a+

[alex2746]

Merci!
Je comprends mieux la méthode qui consiste à créer les deux listes des parents.
J'aimerais donc essayer avec celle-ci.

Mais pouvez-vous m'aider pour créer ces listes de parents?
Car je connais les méthodes de parcours d'un arbre : préfixé, postfixé et infixé mais je ne vois pas comment récupérer que les ancêtres d'un noeud....

Merci d'avance.

[Rei Ichido]

Cette méthode est plus optimisée (moins de recherche et moins d'information à remonter) mais étant très spécialisée, il y a moins de chance qu'elle te serve pour un autre probleme).
a+

Tu pourrais détailler ?
Ma méthode s'effectue concrètement en o(n), où n est la profondeur de l'arbre :
- remontée de l'arbre : o(n)
- vérification de la présence : o(n)
- comparaison des noeuds jusqu'à trouver le 1er ancêtre commun : o(n) pour peu qu'on n'utilise pas des contains, mais qu'on parcoure les 2 listes en même temps avec le décalage idoine pour la différence de profondeur initiale.

J'ai du mal à concevoir qu'il puisse y avoir mieux que ça ^^ Cela dit je ne suis pas du tout un expert en algorithmique

[hwoarang]

Tu pourrais détailler ?

Je ne pensais pas en terme de complexité mais plutot d'optimisation mémoire. En effet, dans ton cas, tu es obligé de balader une liste des parents qui sera remplie en parcourant l'arbre. Et, il faut parcourir 2 fois les branches communes. Pour finir, il faut chercher le 1er parent commun.
Dans la 2e solution, on ne pacours qu'une fois la branche commune et, une fois qu'on a trouvé, on remonte directement le nombre de branches (donc pas de liste de parents à maintenir et pas de post traitement à faire).
A part ca, ca revient au meme.

Mais pouvez-vous m'aider pour créer ces listes de parents?

Deja, il faudrait dire s'il est normal qu'un noeud ait 3 fils...

[alex2746]

Oui, c'est normal.
C'est un arbre n-aire, les noeuds peuvent avoir 0, 1, 2, 3, .... fils.

Merci d'avance.

[hwoarang]

OK. Dans ce cas, commence à poster ton code pour voir exactement ou ca bloque. Il faudrait au moins poster la classe Arbre et la classe Noeud...

[Rei Ichido]

Mais pouvez-vous m'aider pour créer ces listes de parents?
Car je connais les méthodes de parcours d'un arbre : préfixé, postfixé et infixé mais je ne vois pas comment récupérer que les ancêtres d'un noeud....

Merci d'avance.

Tu pars du noeud, tu prend son ancêtre, et par répétition jusqu'à ce qu'il n'y ait plus d'ancêtre ? Tu n'as pas accès à un ancêtre depuis un noeud ? Quand tu cites getRacine(), c'est uniquement au niveau de l'arbre et pas au niveau des noeuds ? Si c'est le cas c'est plus compliqué ^^

[alex2746]

En effet, la méthode getRacine() est juste pour l'arbre...

En gros:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
class Noeud{
 
private T valeur;
 
public Noeud (T valeur){...}
public T getValeur(){...}
public void setValeur(T a){...}
public int getNbFils(){...}
public Noeud getFils(int numFils){...}
public void setFils(int numFils, Noeud fils){...}
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
class Arbre {
 
private Noeud racine;
 
public Arbre(){...}
public Noeud getRacine(){...}
public void setRacine(Noeud n){...}
}

Merci d'avance.

[hwoarang]

Tu as oublié l'info principale : Si c'est un arbre n-aire, comment est il rangé ? Avec un arbre binaire, c'est facile de deviner mais avec un n-aire, ca depend de toi

[alex2746]

On ne me parle pas de rang dans mon énoncer, on me donne juste cet arbre n-aire la comme exemple mais je suppose que mon algorithme devra fonctionner pour n'importe quel arbre n-aire...

Merci d'avance.

[hwoarang]

Dans ce cas, ca change pas mal l'enoncé. Ca veut dire que l'arbre n'est pas trié donc il faut partir du début et trouver la hiérarchie des 2 elements. Ensuite, il faut trouver les plus vieux ancetres communs.

Pour t'aider à commencer, je partirais sur une fonction genre :
boolean getHierarchieFils(List<Noeud> peres, int numFils);

Celle-ci serait recursive et regarderait si la valeur du noeud correspond à numFils. Si oui, elle renvoie true et si non, elle renvoie false.
Ensuite, a chaque fois que true aura été renvoyé, il faut ajouter le Noeud comme étant pere (et propager le true pour ajouter tous les peres précédent)...

[alex2746]

Merci pour ta réponse.
J'ai essayé d'écrire cette méthode mais je n'y arrive vraiment pas... je n'arrive même pas à parcourir l'arbre pour trouver le numéro du noeud recherché...

Peux tu m'aider à l'écrire stp?

Merci d'avance.

[Rei Ichido]

J'imagine que tu ne peux pas changer la classe ?
Avoir accès au père ça permet de remonter l'arbre, sinon c'est emmerdant ~~

Enfin bon tu peux toujours faire un parcours complet de l'arbre et en déduire une HashMap Parent->Pere.

[alex2746]

Non, je ne peux pas modifier la classe

[hwoarang]

Ce n'est pas t'aider que de faire tes devoirs à ta place mais un petit (gros) coup de pouce pour commencer :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public void displayPeres(Arbre arbre, int numFils)
{
  if(this.displayPeres(arbre.getRacine(), numFils) == false)
  {
    System.out.println("Impossible de trouver : " + numFils);
  }
}
 
private boolean displayPeres(Noeud noeud, int numFils)
{
  boolean ret = false;
  if(noeud.getValeur() == numFils)
  {
    ret = true;
  }
  else
  {
    int i = 0;
    while((ret == false) && (i < noeud.getNbFils()))
    {
      Noeud nf = noeud.getFils(i);
      ret = this.displayPeres(nf, numFils);
      i++;
    }
 
    if(ret != false)
    {
      System.out.println("Pere : " + this.getValeur());
    }
  }
  return ret;
}

Ce code suppose que les elements dans l'arbre sont uniques (ou bien qu'il faut n'en trouver qu'un).

La, tu devrais avoir toutes les billes pour resoudre seul ton probleme...