Classes d'arbres (binaire , binaire de recherche, avl , bicolore ...) + interface graphique

Soyez le premier à donner votre avis sur cette source.

Vue 27 458 fois - Téléchargée 4 872 fois

Description

Dans le zip il y a les différentes classes d'arbres :
- Binaire
- Binaire de Recherche
- H-équilibrés
- AVL
- Bicolores
Les fonctions pour les arbres :
- ajouter (élément)
- supprimer (élément)
- rotations (gauche, droite , gauche-droite, droite-gauche)
- recherches ( préfixée, infixée, postfixée, pour les arbres de recherche)
- ...
Interface Graphique :
- Gestion de tous les arbres et de 2 types de données ( entier et chaine de caractère)
- Affichage de l'arbre
- Création, Modification d'un arbre
- Recherche avec affichage du parcours
- Sauvegarde et Chargement d'arbre par sa forme textuelle
- Forme Programme et Applet

Conclusion :


Si vous trouvez des bug n'hésitez pas à me contacter.
Le seul probème connu à se jour est lors du chargement d'un arbre bicolore, l'arbre est bien chargé mais on pert l'information du type de noeud (fils, frère)

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_FireDraGon
Messages postés
21
Date d'inscription
mardi 23 avril 2002
Statut
Membre
Dernière intervention
12 juillet 2004
-
1ere mise à jour :
Correction de 2 bugs
verdy_p
Messages postés
203
Date d'inscription
vendredi 27 janvier 2006
Statut
Membre
Dernière intervention
29 janvier 2019
-
A quoi sert de stocker dans chaque noeud le type de noeud, alors que le valeur stockée dans chaque noeud peut être consultée directement pour en obtenir la classe.
D'autre part, Arbre.java contient des champs inutiles pour certains types d'arbres. Comme les arbres sépcialisés définissent des méthodes, ne pourraient-ils pas directement définir les champs supplémentaires qu'ils requièrent? par exemple le champ "frere" est inutile si on n'a pas d'arbe bicolore, et ce source ne permet pas de transformer un type d'arbre dans un autre car il n'y a pas de fonction de rééquilibrage adaptée à chaque type d'arbre.
A la base, tous ces arbres sont binaires, seul le critère d'équilibrage change. On pourrait s'attendre à pouvoir gérer des arbes quelconques de degré supérieur à 2.
De façon générale, ce type de classe est surtout ditactique, mais dans ce cas autant faire simple, car la hoérarchie de classes Java n'est pas utilisée de façon optimale. Autant utiliser les collections standards de Java où on a un conteneur "SortedTree" pour faire la même chose de façon plus générale avec des valeurs stockées pouvant aussi être des objets quelconques et un sous-classement possible pour le le critère d'ordonnancement des valeurs dans l'arbre (en implémentant un Comparator dans la sous-classe conteneur): par exemple un HashedTree n'est rien d'autre qu'un arbre trié dans lequel les valeurs stockées sont triées par leur valeur (int) de hachage, et maintenu équilibré en hauteur (avec une tolérance heuristique locale ou globale).
Note: les opérations d'équilibrage sont couteuses car cela consiste à caluler ou maintenir en cache la hauteur de l'arbre. Généralement on stocke dans chaque noeud la hauteur maximale de l'arbre porté par ce noeud, et l'équilibrage tente de maintenir égales les hauteurs des sous-abres gacuhe et droite quand ils existent, et s'assurer qu'un noeud parent porte au moins 3 descendants; cela suffit pour un équilibrage partiel mais efficace et suffisant la plupart du temps dans le cas d'arbres binaires au contenu très souvent modifié; il suffit de maintenir aussi le nombre total de noeud dans l'arbre au sein de chaque feuille pour ne pas avoir à parcourir chaque fois tout l'arbre pour les compter. Mais on peut aussi ne maintenir dans chaque noeud que la différence entre le nomnbre de noeuds descendants à droite et le nombre de nouds descendants à gauche, cette différence devant rester dans un petit intervalle de +/-N; dès que cette différence dépasse, on applique un rééquilibrage global de ce sous-arbre, ou partiel (par exemple réduire cette différence de moitié, plus rapide à réaliser si l'arbre subit de fréquentes mises à jour). Le critère à utiliser peut même être dynamique en comptant le nombre de recherches dans l'arbre depuis la dernière mise à jour: si ce nombre de recherche dépasse un seuil de réorganisation, on réduit ce seuil; on compte aussi le nombre d'ajouts ou suppressions depuis un la dernière recherche, et si ce nombre dépasse un seuil on augmente ce seuil de réorganisation.
Pour les réorganisations d'équilibrage, on utilise les primitives de rotation de valeurs.
psycared
Messages postés
4
Date d'inscription
lundi 22 novembre 2010
Statut
Membre
Dernière intervention
2 décembre 2011
-
il ma plut

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.