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.

[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.

[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.

[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