Discussion :

[geforce]

Bonjour à tous,
J'ai déjà mon arbre N-aire (Résultat d'un autre algorithme) cet arbre a juste des noms de nœud (donc: pas moyenne de trié l'arbre).

Je veux savoir quels sont les algorithmes que l'on peut utiliser pour trouver le nœud que l'on veut trouver dans cet arbre ? Sachant que l'on connaît le nœud racine de l'arbre et le nœud a recherché.

Grand merci d'avance pour vos indications.

[Invité]

salut,

ben t'en a pas 50000, vu que ton arbre est pas trié et si tu peux rien intuiter sur tes noeuds, c'est graphe: parcours en profondeur et parcours en largeur
t'as juste pas besoin de vérifier les cycles

[geforce]

salut,

ben t'en a pas 50000, vu que ton arbre est pas trié et si tu peux rien intuiter sur tes noeuds, c'est graphe: parcours en profondeur et parcours en largeur
t'as juste pas besoin de vérifier les cycles

Devrait ne pas avoir de cycle puisque c'est un arbre (pas un graphe) ?

Dit moi si les algorithmes de 'parcours en profondeur et parcours en largeur' fonctionnent bien avec des cas d'arbre avec des nœuds N-aire ?

Merci

[dourouc05]

Par définition (du moins celle que j'ai sous les yeux), un arbre est un graphe acyclique connexe.

Nommer les recherches en profondeur et en largeur "algorithmes" est un peu usurpé, ce sont plutôt des stratégies de parcours d'un arbre (ou un graphe, mais ça ne semble pas le cas ici). À ce niveau d'abstraction, pas de différence selon le nombre de fils d'un nœud. D'ailleurs, Wikipédia explique ces stratégies pour des graphes bien plus généraux que des arbres binaires.

[geforce]

Bonjour sur Wikipedia j'ai trouvé que ça : http://fr.wikipedia.org/wiki/Algorit..._en_profondeur

je cherche un code JAVA qui permet de faire le parcours en profondeur d'un arbre N-aire ?


NB: sur le net je ne trouve que pour des arbre binaire (c'est ce que je cherche)
NB: j'ai trouvé ça aussi sur developpez mais pour des arbre binaire : http://rperrot.developpez.com/articl...arbres/#LVII-C

[yahiko]

Il n'y a quasiment aucune différence entre le parcours (longueur ou profondeur) d'un arbre binaire et celui d'un arbre n-aire.
La modification dans l'algorithme est minime.

[geforce]

Il n'y a quasiment aucune différence entre le parcours (longueur ou profondeur) d'un arbre binaire et celui d'un arbre n-aire.
La modification dans l'algorithme est minime.

OK, mais la quel ? Entre arbre binaire et N-aire

J’ai cet algorithme récursif suivant :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
fonction Existe(src : arbre, elt : TElement) renvoie un booléen
 
	si EstVide(src)
		renvoyer faux
	sinon
		si src->value = elt alors
			renvoyer vrai
		sinon
			renvoyer Existe(FilsGauche(src),elt ) ou Existe(FilsDroit(src), elt);
		fin si
	sin si

Source : http://rperrot.developpez.com/articl...arbres/#LVII-C

Ici y notion de "FilsGauche" et "FilsDroit" qui dans un arbre N-aire je n'ai pas que ça, je peux avoir une infinité !! Comment je faire l'algorithme dans ce cas ? y t'il des exemple sur le .net

Merci

[dinobogan]

Un arbre binaire est un arbre 2-aire. Qu'il y ai filsGauche et filsDroit ou un tableau de fils à 2 éléments, c'est la même chose.
Maintenant, implémente un parcours en profondeur pour un arbre 2-aire dont le parcours des fils est dans une boucle "for" et tu étends simplement ce parcours à ton arbre N-aire. Chaque noeud connait son nombre de fils donc la modification de 2-aire vers N-aire devient triviale.

[Flodelarab]

Bonjour,

je peux avoir une infinité

Merci geforce d'élever le débat. L'infini et les sciences.

L'infini est une notion purement mathématique. En physique, le maximum est de l'ordre de 10⁵⁷. Un mathématicien rétorquera que ce n'est pas le maximum car il existe 10⁵⁷+1. Argument auquel le physicien répondra que rien dans le monde ne peut être désigné par cette quantité; ni la fortune de Bill Gates, ni la taille de l'univers en angstroms, etc.

Et l'informaticien, lui, regarde l'infini comme une autruche qui a trouvé une fourchette. Rien est infini en informatique. On ne peut même pas modéliser les nombres réels. Le maximum que sait manipuler un ordi, ce sont les nombres rationnels.

Bref. Si ton arbre a un grand nombre de branches (plus précisément, un noeud, de fils), tu peux quand même le parcourir (par une boucle par exemple).

[sambia39]

Bonjours,

Et si on essayait de résoudre le problème sous un autre angle ?
Tout d'abord c'est quoi un arbre binaire et un arbre N-aire ?.
De manière générale les arbres binaire sont des arbres ordonnés tels que tout noeud à au plus deux fils ce qui veut dire, qu'elle est définie comme un ensemble fini qui est vide ou composer d'une racine et de deux sous-arbres dits sous-arbres gauches, sous-arbre droit.
Quant à un arbre n-aire en peut la définir mathématiquement comme un cas particulier de graphe. Une définition récurrente ça va de soi, mais suffisante pour la définir comme un ensemble non vide dont un des éléments est défini comme la racine de nôtres arbres et de ce fait il existe une répartition des autres éléments restants s'il en existe dont, chaque élément est lui-même un arbre ( sous arbres ).

En résumé un arbre binaire à deux successeurs ordonnés et un arbre n-aires a 'n' successeur ( fils 1, ....., fils n , des notions de fils aîné, frère, descendance directe donc -> l’ensemble des successeurs immédiats d’un sommet) et ton objectif à toi, est de trouver un noeud précis dans un arbre n-aire et comme un arbre n-aire est défini mathématiquement comme un cas particulier de graphe sachant également que ton graphe à juste des noms de noeuds, techniquement où par supposition l'arbre a forcément une représentation donc une possibilité de parcourir l'arbre et donc un accès aux noeuds.
En vue de cette déduction (bizarre) en peut théoriquement et voir techniquement trouver le noeud X en question exemple: soit l'arbre n-aires suivant (A (B (F) (G) ) (C) (D) (E (H) (I) (J) ) ) on pourra la représenter et connaître les successeurs dont la racine ici est A donc; il suffit de parcourir notre arbre on spécifient les conditions de recherche préalablement.
Exemple (trouver le noeud C qui est un frère) il nous suffira de faire par exemple: si le noeud actuel est un fils aîné et c'est le noeud que l'on recherche alors on n'a trouver le noeud X si ce n'est pas le cas, on recherche un noeud qui est frères de l'aîné s'il en existe et si il est le noeud X alors en à trouver X . voilà une approche bizare à toi de voir.....

[worm83]

Merci geforce d'élever le débat. L'infini et les sciences.

L'infini est une notion purement mathématique. En physique, le maximum est de l'ordre de 10⁵⁷. Un mathématicien rétorquera que ce n'est pas le maximum car il existe 10⁵⁷+1. Argument auquel le physicien répondra que rien dans le monde ne peut être désigné par cette quantité; ni la fortune de Bill Gates, ni la taille de l'univers en angstroms, etc.

Et l'informaticien, lui, regarde l'infini comme une autruche qui a trouvé une fourchette. Rien est infini en informatique. On ne peut même pas modéliser les nombres réels. Le maximum que sait manipuler un ordi, ce sont les nombres rationnels.

HS :

Pourtant par exemple le nombre de partie du jeu de GO est de l'ordre de 10¹⁷². Et le nombre d'atome dans l'univers serais d'environ 10⁹⁰, il y a très peu de choses que l'on peut quantifié par ces nombres, certes, mais il y en a.
Mais il est vrai que l'infini est une notion purement mathématique.

(exemples http://yoda.guillaume.pagesperso-ora...P100.htm#echec)

[MABROUKI]

bonjour

OK, mais la quel ? Entre arbre binaire et N-aire

J’ai cet algorithme récursif suivant :

Cet algo que tu as trouve pour les arbres binaires sur dev.net n'est autre qu'une "Depth-first traversal" ou "Rech.en Profondeur d'Abord" soit une visite systematique de tous les noeuds d'un arbre....
Il est valable pour N-Ary Tree (arbre ou chaque noeud a un nbre -N constant - d'enfants)
Exemple : un 4-Ary Tree :chque noeud a 4 enfants....

code (version pre-order):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
bool found = false
node = Root  (racine)
nodeToSearch  =....  'noeud à rechercher     
 
PreOrder(node,found,nodeToSearch)
  if node == null then  return
  if node == odeToSearch then found=true        
            return
  visit(node)   'imprime le noeud
  pour chaque childNode dans node.ChildNodes   
          PreOrder(childNode,found,nodeToSearch)

code (version post-order):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
bool found = false
node = Root  (racine)
nodeToSearch  =....  'noeud à rechercher      
 
PostOrder(node,found,nodeToSearch)
  if node == null then return
  if node == nodeToSearch then found=true        
            return
 
 pour chaque childNode dans  node.ChildNodes   
         PostOrder(childNode,found,nodeToSearch)  
 
 visit(node)  'imprime le noeud

Tu noteras que le Visit(left) et Visit(Right) a ete remplace par simplement l'iteration sur les enfants du node ....
bon code....