Discussion :

[drake84450]

Bonjour a tous.

Pour le besoin d'un projet je dois réaliser un arbre n aire de hauteur x et où chaque nœud possèdent n fils.
Je souhaite realiser un arbre de ce genre (x=3, n=2)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
1->2
|  |
|  |->1->2
|     |  |
|     |  |->1->2
|     |
|     |->1->2
|
|->1->2
   |  |
   |  |->1->2
   |
   |->1->2

Voila ma structure nœud:

Code :

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

1
2
3
4
5
6
7
 
struct noeud
{
		int info;
	        noeud * frere;
		noeud * fils;
};

Donc j'essaie de faire un algo capable de construire un tel arbre en fonction x et n mais je n'y arrive vraiment pas, je vous remercie par avance de votre aide

[koala01]

Salut,

De manière générale, un arbre Naire peut, parfaitement, être considéré comme un arbre binaire dans le sens où il "suffit" de considérer que le noeud que l'on appellerait "left" est le noeud "frere" (comprend: le noeud suivant pour un niveau donné) et le noeud que l'on appellerait "right" est en fait le noeud enfant (comprend: le premier noeud de niveau N+1).

Dés lors, tu pourrais très bien avoir une structure Node proche de

Code :

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

1
2
3
4
5
stuct Node{
    UnType data; // la donnée propre au noeud (du type qui te convient ;) )
    Node * next; // le noeud suivant de même niveau
    Node * child; // le premier noeud enfant
};

Pour le reste, l'algorithme qu'il te faudra mettre en place a de bonnes chances de devoir être récursif (ce sera sans doute la manière la plus facile de procéder ), surtout si tu sais à la base le nombre d'enfant que tu veux que chaque noeud contienne ainsi que le niveau maximal à atteindre, et d'avantage encore si chaque noeud doit avoir le même nombre d'enfants .

Seulement, tu devras sans doute travailler sur deux plans :

• l'ajout d'un enfant d'une part et
• l'ajout d'un frere d'autre part

et la récursivité devra sans doute travailler sur les deux tableaux (le Nième enfant d'un noeud étant le frère de son enfant N-1 )

Je crois t'avoir donné toutes les informations qui devraient te permettre de résoudre par toi meme ton problème, je vais donc te laisser réfléchir un peu à ton aise car autrement tu n'apprendras pas grand chose

Mais n'hésites pas à venir demander des conseils ou de l'aide si tu coinces quelque part

NOTA On pourrait aussi envisager d'utiliser une collection (std::vector<Node*> ) d'objets pour représenter les enfant, mais on perdrait "assez facilement" la liaison entre deux frères.

Ce pourrait ne pas être un problème en fonction des algorithmes (récursifs eux aussi) que tu mettrais en place pour le parcours de ton arbre, et / ou de la manière dont tu veux pouvoir les parcourir.

J'ai choisi une solution parmi d'autres qui n'est, à mon sens, ni forcément meilleure ni forcément pire que les autres étant donné que nous ne savons pas exactement ce que tu veux faire de ton arbre une fois qu'il a été généré

[drake84450]

ok merci je vais essayer de continuer. Par contre je sais pas pourquoi j'ai mis fg et fd dans ce post alors que sur mon code j'avais bien mis frere et fils. Je vais mettre cela sur le coup de la fatigue Je vais corriger le post, j'ai pris la structure de mon arbre binaire ...

[koala01]

Le fait est que, comme je te l'ai indiqué, on peut parfaitement considérer de manière "naïve" qu'un arbre Naire n'est qu'un arbre binaire pour lequel une sémantique différente est associée aux différentes relations

Il n'est donc pas "faux" en soi de travailler avec un arbre binaire, la seule chose, c'est qu'il y a alors intérêt à veiller à encapsuler correctement tout cela pour éviter la confusion du genre "tiens, pourquoi vient il me parler de gauche et de droite alors que je penserais à frere et enfant "

Mais ce n'est vraiment qu'un moyen d'éviter à des gens fatigués / distraits d'avoir à se poser des questions

[drake84450]

Au départ j'étais parti sur un arbre binaire où chaque nœud contenait une liste chaînée de nœuds mais cela compliquait grandement le travail et je me serai sûrement perdu dans mon propre code. Donc j'ai abandonné pour un arbre n aire où se sera plus simple de travailler.