Discussion :

[MABB]

Bonjour

Je cherche à calculer le nombre de cellules d'un arbre construit comme suit:
soit A1->A2, B1->B2, C1->C3 trois suites de 2 cellules.
A1 est la première cellule de l'arbre
ensuite les filles de A1 sont A2, B1, C1
- les filles de A2 sont B1 et C1
- les filles de B1 sont A2 et C1
ainsi de suite.

J'espère que vous comprenez le principe. On obtient au début
A1
A2 B1 C1
B1 C1 A2 B2 C1 A2 B1 C2
.....

Connaissez-vous des liens ou des livres qui compte le nombre de cellules d'arbres binaires ou non-binaires ?
Avez-vous des pistes pour ce genre de calcul ?

Merci pour vos réponses

PS: est-ce le bon forum de developpez.com ?

[MABB]

Les espaces ont disparus dans l'arbre !!!!
---- A1
A2 -- B1 --- C1
B1 C1 -- A2 B2 C1 ---- A2 B1 C2

[Faiche]

Dans la mesure ou il y a des boucles, c'est un graphe et non un arbre.

Ensuite, pour compter, tu parcours le graphe et tu ajoutes 1 à chaque fois.

[MABB]

Avant de le parcourir et de compter combien j'ai de cellules, je voudrais le quatifier.
Histoire de voir si je ne me suis pas trompé et si ma méthode est convenable au niveau performance

[SpiceGuid]

• un parcours en profondeur te permet de traverser toutes les cellules accessibles depuis la racine
• pour chaque cellule traversée tu incrémentes un compteur (initialisé à 0 avant la traversé de la cellule racine)

[oniric]

ce n'est pas un arbre, mais un graphe en effet vu qu'il y a des boucles dedans. L'algo pour compter le nombre de nœud est surement aussi dans l'un des nombreux tutoriaux ici. Le principe est quasiment le meme que pour un arbre sauf qu'il faut eviter que ton algo rentre dans une boucle infini genre A2 -> B1 -> A2 ... pour cela tu te gardes une table des nœuds que tu as deja visité et tu arretes ta recursion si tu as deja visité tous les fils du nœuds courant.

[MABB]

Escusez-moi pour le terme d'arbre, car vous avez raison c'est un graphe.
Vous ne comprennez pas ma question. Je me suis peut-être mal exprimé.

J'arrive à compter le nombre de noeuds à la consturction du graphe.
Or pour savoir si ma méthode de construction est la bonne , je recherche une formule mathématique.

N'ayez pas peur d'apporter de la doc anglaise ou des formules barbares. J'ai l'habitude.

Merci pour vos réponses