Arbre n-aire en java

Version imprimable

22/10/2010, 15h43
minouch

Arbre n-aire en java

Bonjour,
est ce que quelqu'un peut me donner un lien de cour détaillé sur la programmation des arbres n-aires en java
j'ai recherché mais j'ai trouvé seulement des cours sur les arbres binaires
merci :)
22/10/2010, 15h45
dinobogan

Un arbre n-aire est simplement une structure ou un noeud peut posséder plusieurs fils.
Tu recherches quoi en particulier comme cours ? La quasi totalité de ce qui se fait sur un arbre binaire est transposable facilement sur un arbre n-aire. Que cherches-tu à faire ?
23/10/2010, 02h21
minouch

BSR,
je cherche à créer un arbre n_aire en java pour en faire ensuite sortir ses différentes branches et les sauvegarder dans une matrice (chaque branche(ensemble de noeuds) va être sauvegardée dans une ligne)
j'ai déjà réussi à faire ça avec un arbre binaire mais c'est pas le cas pour un arbre n-aire :(
23/10/2010, 22h59
dinobogan

Explique ce qui te bloques, parce que je ne comprend pas ce que tu ne comprends pas ;)

BSR,
si j'ai l'arbre suivant

Code:

1
2
3
4
5
6
7
8
 
        SW1
      /         \
   SW2        HW2
  /     \         /     \ 
SW3  HW3   SW3   HW3
  |       |         |      |
SW4   SW4    SW4  SW4

je dois avoir comme affichage SW1 SW2 SW3 SW4
SW1 SW2 HW3 SW4
SW1 HW2 SW3 SW4
SW1 HW2 HW3 SW4
càd j'affiche à chaque fois une branche de l'arbre à partir du noeud pere jusqu'à le dernier fils de la branche
mon problème est dans la fonction parcours
mon code est le suivant :

Code:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
import java.util.ListIterator;
import java.util.Vector;
import java.util.*;
 
public class Arbre5 {
    private int value;
    private String value_noeud;
 
    private Vector<Arbre5> fils;
 
    private Vector<Arbre5> pere;
 
    public Arbre5(int n)//n est le nbre des fils de chaque noeuds 
    {
        this.value = n;
        fils = new Vector<Arbre5>();
        pere=new Vector<Arbre5>();
    }
 
    public String getValue()//le nom du noeud 
    {
        return this.value_noeud;
    }
 
    public void ajouteFils(Arbre5 Ar)
    {
            if(!(this.fils.contains(Ar)))//on vérifie tt d'abord que le nouveau noeud à ajouter n'est pas déja existant
            {
                this.fils.add(Ar);
            }
    }
    public void ajoutePere(Arbre5 Ar)
    {
            if(!(this.pere.contains(Ar)))
            {
                this.pere.add(Ar);
            }
    }
    public void setValeur(String ch)//pour le nom du noeud 
    {
        this.value_noeud = ch;
    }
 
    public Arbre5 donneFils(int n)//retourne le noeud à l'indice n du vecteur des fils d'un noeud parent qq 
    {
        try{
            return this.fils.get(n);//retourner le fils à l'indice n 
         }
        catch(ArrayIndexOutOfBoundsException e){
            e.toString();
            return null;
        }
    }
 
    public int getFilsSize()// retourne le nombre de fils d'un noeud 
    {
        return this.fils.size();
    }
    public int getPereSize()// retourne le nombre de pere d'un noeud 
    {
        return this.pere.size();
    }
 
   public ListIterator<Arbre5> elements()
   {
	   return fils.listIterator();//une listeIterator sur chaque fils 
   }
   public ListIterator<Arbre5> elements1()
   {
	   return pere.listIterator();//une listeIterator sur chaque pere 
   }
 
 
 
   public static void parcours(Arbre5 arbre)
   {
	   ListIterator<Arbre5> list = arbre.elements();
	   ListIterator<Arbre5> list1 = arbre.elements1();
	 if (list.hasNext())
	 {
		 cherche_suivants(arbre);
		 parcours(list.next());
	 //System.out.println("next"+arbre.getValue());
	 }
	 //else System.out.print("\t"+" next"+arbre.donneFils(0).getValue()+"\t");      
if(list1.hasPrevious())
		 {
	     cherche_précédents(arbre);
 
		 parcours(list1.previous());
		// System.out.println("previous "+arbre.getValue());
 
		 }
	 }  
   public static void cherche_suivants(Arbre5 arbre)
   {
	   ListIterator<Arbre5> list = arbre.elements();
		 if(list.hasNext())
		 {
			 System.out.println("suivant "+arbre.getValue());
			 cherche_suivants(list.next());
		 }
		 else//cas de noeud n'ayant aucun fils 
			 System.out.println("suivant"+arbre.getValue());
   }
   public static void cherche_précédents(Arbre5 arbre)
   { System.out.println("précédent du "+arbre.getValue());
 
	   ListIterator<Arbre5> list1 = arbre.elements1();//liste pour les pères
		if/*while*/(list1.hasNext())
		 {//System.out.println("précédent "+arbre.getValue());
 
			 cherche_précédents(list1.next());				
 
		 }
		else System.out.println("pas de precedents");
   }
public static void parcours_profondeur(Arbre5 arbre) {
 
	    System.out.println(arbre.getValue());
	    ListIterator<Arbre5> list = arbre.elements();
	    while(list.hasNext()){
	        parcours_profondeur(list.next());
	    }    
    }
public static void affiche_fils(Arbre5 Arb)
{
	System.out.println("fils de "+Arb.getValue());
 
	if(Arb.getFilsSize()!=0)
	for(int ss=0;ss<Arb.getFilsSize();ss++)
	{System.out.print(Arb.donneFils(ss).getValue()+"\t");     
	}
else System.out.println("aucun fils");
 
	System.out.print("\n");
}
   public static void main(String[] args) {
 
	   Arbre5 SW1 = new Arbre5(2);//2 est le nbre de files et arbre c'est le noeud racine/père 
 
	   Arbre5 SW2 = new Arbre5(2);
	   Arbre5 HW2 = new Arbre5(2);
 
	   Arbre5 SW3 = new Arbre5(1);																									
	   Arbre5 HW3 = new Arbre5(1);
	    Arbre5 SW4 = new Arbre5(1);
	   Arbre5 SW5 = new Arbre5(0);  
	    SW1.setValeur("SW1");
	    SW2.setValeur("SW2");
	    SW3.setValeur("SW3");
	    SW4.setValeur("SW4");
	    SW5.setValeur("SW5");
	    HW2.setValeur("HW2");
	    HW3.setValeur("HW3");
 
	    //AJOUT DES NOEUDS 
	    SW1.ajouteFils(SW2);
	    SW1.ajouteFils(HW2);
 
	    SW2.ajouteFils(SW3);
	    SW2.ajouteFils(HW3);
 
	    HW2.ajouteFils(SW3);
	    HW2.ajouteFils(HW3);
 
	    SW3.ajouteFils(SW4);
	    HW3.ajouteFils(SW4);
 
	    SW4.ajouteFils(SW5);
	    /*******ajout pere*******/
	    SW2.ajoutePere(SW1);
	    HW2.ajoutePere(SW1);
	    SW3.ajoutePere(SW2);
	    HW3.ajoutePere(SW2);
	    SW3.ajoutePere(HW2);
	    HW3.ajoutePere(HW2);
	    SW4.ajoutePere(SW3);
	    SW4.ajoutePere(HW3);
	    SW5.ajoutePere(SW4);
	    SW5.ajoutePere(SW4);
	    /*******fin ajout pere*******/
 
	    affiche_fils(SW1);
		 affiche_fils(SW2);
		 affiche_fils(HW2);
		 affiche_fils(SW3);
		 affiche_fils(HW3);
		 affiche_fils(SW4);
		 affiche_fils(SW5);
 
	    System.out.println("début parcours profondeur");
	    parcours_profondeur(SW1);
	    System.out.println("fin parcours profndeur \n");
 
 
	  parcours(SW1);
	 // cherche_suivants(SW1);
	 // cherche_précédents(SW1);
	 // System.out.println("noeud suivant");
	  //cherche_suivants(SW2);
	  //cherche_précédents(SW2);
 
   } 	 
	}

merci pour votre aide ^_^

Il te faudrait quelque chose comme ceci:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
 
	public void recursivite() {
		ListIterator<Arbre5> fils = elements();
		if ( fils != null && fils.hasNext() ) {// Si on a des fils
			while ( fils.hasNext() ) {
				fils.next().recursivite();// On peut descendre dans l'arbre alors on descend!
			}
		} else {// Sinon on est une feuille de l'arbre
			afficher();
			System.out.println( "#####" );// Séparation entre chaque branche
		}
	}
 
	private void afficher() {
		if ( elements1().hasNext() ) { // On a alors un père, on remonte jusque'a lui
			elements1().next().afficher();
		}
		System.out.println( value_noeud );
	}

A adapter car ici je fais comme si un nœud n'a qu'un père, ce qui n'est pas ce que tu souhaites apparemment.

Kaoualeo

28/10/2010, 14h55
dinobogan

minouch, ton exemple n'est pas clair car plusieurs noeuds ont le même nom :roll:
28/10/2010, 16h40
minouch

merci beaucoup kaoualeo pour la réponse
je vais l'essayer tout de suite :)
Pour mon exemple je dois avoir plusieurs noeuds ayant le même nom du fait que les fils d'une implantation SW doivent être les mêmes d'une implantation HW

non le code ne marche pas il me donne une exception
en plus j'ai trouvé une solution mains non satisfaisante puisque dans mon cas un noeud peut avoir plusieurs pères
ce que j'ai fait c'est la sauvegarde du résultat du parcours en profondeur dans une matrice tel qu'à chaque passage par une feuille je passe à la ligne suivante dans ma matrice
j'obtiens la matrice suivante :
SW1 SW2 SW3 SW4 SW5
HW3 SW4 SW5 null null
SW3 SW4 SW5 null null
HW3 SW4 SW5 null null

et puis je cherche les précédents (jusqu'au noeud racine SW1)de chaque première case de chaque ligne de ma matrice pour les ajouter dans ma matrice
ça m'a donné un bon résultat sauf que pour un fils ayant plus qu'un père ça pose un problème j'obtiens toujours le même père d'un tel type de fils exemple HW3 a deux pères SW2 et HW2 mais j'obtiens seulement SW2
voici ma méthode de recherche de précédents
Code:

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 33 34 35 36 37 38 39 40 41 /********* fct pour extraire les précédents des noeuds ayant des précédents**********/ public static Vector <Arbre5> precedent1=new Vector(); public static Vector cherche_précédents1(Arbre5 arbre) { ListIterator<Arbre5> list1 = arbre.elements1();//liste pour les pères precedent1.add(arbre); if(list1.hasNext()) {cherche_précédents1(list1.next());/*list1.remove();*/} //else System.out.println("pas de precedents"); return precedent1; } /*********fin fct pour extraire les précédents des noeuds ayant des précédents retournant le resultat sous forme d'un vect precedent1 pour chauqe noeud**********/ public static Vector<Arbre5> precedent=new Vector(); public static String[][]mat_preced=new String[500][500];//pour stocker les précédents de chaque noeud dans une ligne public static int zz=0/*pour les lignes*/, aa=0/*pour les colonnes*/; public static int ss=0;//pour parcourir noeuds_avec_preced public static int rri=0;//pour parcourir precedent1 public static String[][]cherche_précédents(Vector<Arbre5>noeuds_avec_preced ) { while(ss<noeuds_avec_preced.size()) //if(noeuds_avec_preced.elementAt(ss).getValue().equals(arbre.getValue()))//ce noeud a des preced à mettre { precedent1.clear(); precedent1=cherche_précédents1(noeuds_avec_preced.elementAt(ss));//elle va me retourner un vect precedent1 possédant les pères du noeud noeuds_avec_preced.firstElement() //for(int mm=0;mm<precedent1.size();mm++) //System.out.println(precedent1.elementAt(mm).getValue()); for(rri=0;rri<precedent1.size();rri++) { mat_preced[zz][aa]=precedent1.elementAt(rri).getValue(); aa++; } ss++; //passer à l'élément suivant du vecteur zz++;aa=0; //passer à la ligne suivante et commencer avec la première colonne rri=0; } return mat_preced; }
bon en fait je suis entrain à la fin de sauvegarder les précédents de chaque noeud donné dans un vecteur et dès que je finis avec ce noeud je sauvegarde le vecteur dans un ligne de la matrice et puis je le vide et je passe à la ligne suivante dans la matrice
prière de m'aider merci ^_^

En modifiant le code déjà donné, pour construire la chaine à afficher au fur et à mesure de la descente dans l'arbre.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 public void recursivite(String encours) { ListIterator<Arbre5> fils = elements(); if ( fils != null && fils.hasNext() ) {// Si on a des fils while ( fils.hasNext() ) { fils.next().recursivite(encours + value_noeud));// On peut descendre dans l'arbre alors on descend! } } else {// Sinon on est une feuille de l'arbre System.out.println(encours);// Séparation entre chaque branche } }
Et tu lances avec un appel à recursivite("") sur le noeud père. Ça va te créer des Strings en veux-tu, en voilà, mais si tu n'as pas un arbre de folie, ça passera sans souci ; et sinon, il faut changer de méthode, on ne peut pas passer un StringBuilder aux fils (ils auraient tous le même).

28/10/2010, 19h54
minouch

merci beaucoup pour votre réponse mais voila ce que j'obtiens en exécutant ce code!
Exception in thread "main" java.lang.StackOverflowError
at java.util.AbstractList.listIterator(Unknown Source)
at java.util.AbstractList.listIterator(Unknown Source)

merci beaucoup Rei Ichido pour votre code
il marche bien avec quelques petites modifications
je vais essayer maintenant de sauvegarder les résultats dans une matrice au lieu d'un affichage seulement
merci encore une fois :)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public static void recursivite(String encours,Arbre5 arbre) { ListIterator<Arbre5> list = arbre.elements(); if (list != null && list.hasNext() ) {// Si on a des fils while ( list.hasNext() ) { recursivite(encours + arbre.getValue(),list.next());// On peut descendre dans l'arbre alors on descend! } } else // Sinon on est une feuille de l'arbre System.out.println(encours+"SW5");// Séparation entre chaque branche }

26/05/2015, 00h57
bassoumbah

compter le nombre de noeuds fils dans une arbre n-aire

bonsoir ,
je veux compter le nombre de noeuds fils pour chaque noeuds parent dans une arbre n-aire
comment je peut le faire ? et merci d'avance ;)