Soutenez-nous

Les meilleures sources algorithmesConsultez toutes les sources

Nombre d'auteurs : 1, nombre de sources : 15, dernière mise à jour : 4 janvier 2007 

 
OuvrirSommaireAlgorithmes sur les arbres

Entrée:

 
Sélectionnez

T : un arbre binaire de recherche a trois champs : 
    -> Data, la donnée contenu dans le noeud. 
	-> Left , le sous arbre gauche du noeud. 
	-> Right , le sous arbre droit du noeud. 
X : un élément à chercher.

Sortie:

 
Sélectionnez

vrai si X existe dans l'arbre binaire de recherche T. faux sinon.

Pseudo-Code :

 
Sélectionnez

EXIST( T : T_Tree ; X : T_ELT ) 
 
SI T est l'arbre vide ALORS 
    RENVOYER faux. 
SINON 
	SI T->Data = X ALORS 
		RENVOYER vrai. 
	SINON 
		SI T->Data > X ALORS 
			RENVOYER EXIST( T->Left , X ) 
		SINON 
			RENVOYER EXIST( T->Right , X ) 
		FIN SI 
	FIN SI 
FIN SI

Complexité :

 
Sélectionnez

Si n est le nombre de noeud de l'arbre. 
Dans le meilleur des cas : O(1) 
Dans le pire des cas : O(n) 
En moyenne : O(ln n)
Créé le 17 décembre 2006  par Romuald Perrot

Entrée:

 
Sélectionnez

T : un arbre binaire.

Sortie:

 
Sélectionnez

A priori rien.

Pseudo-Code :

 
Sélectionnez

PARCOURS( T : T_Tree ) 
 
SI T n'est pas l'arbre vide ALORS 
    -- Si parcours prefixe, on fait une operation ici 
PARCOURS( T->Left ) 
-- Si parcours infixe, on fait une opération ici 
PARCOURS( T->Right ) 
-- Si parcours suffixe, on fait une opération ici 
FIN SI

Complexité :

 
Sélectionnez

Si n est le nombre de noeud de l'arbre. -> O(n)
Créé le 17 décembre 2006  par Romuald Perrot

Entrée:

 
Sélectionnez

T : un arbre binaire à trois champs : 
	-> Root : la donnée contenu dans le sommet de cet arbre. 
	-> Left : le sous arbre gauche de l'arbre. 
	-> Right : le sous arbre droit de l'arbre.

Sortie:

 
Sélectionnez

A priori rien.

Pseudo-Code :

 
Sélectionnez

BFS( T : T_Tree ) 
 
	F : File SI T different de l'arbre vide ALORS 
		F.Ajouter( T ) 
	FIN SI 
 
	TANT QUE F est non vide FAIRE 
		X <- F.Extraire() 
		-- On peut effectuer une action sur X ici. 
 
		Si X.Left() est différent de l'arbre vide ALORS 
			F.Ajouter( X.Left() )
		FIN SI 
		SI X.Right() est différent de l'arbre vide ALORS 
			F.Ajouter( X.Right() ) 
		FIN SI 
	FIN TANT QUE

Complexité :

 
Sélectionnez

En considérant que les opérations sur la file s'effectuent en O(1) : 
O(n) où n est le nombre de noeuds de l'arbre.
Créé le 17 décembre 2006  par Romuald Perrot
  

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2006 Developpez Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.