IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Autres IDE Pascal Discussion :

Insertion dans un arbre AVL [GNU Pascal]


Sujet :

Autres IDE Pascal

  1. #1
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    Octobre 2011
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2011
    Messages : 12
    Points : 15
    Points
    15
    Par défaut Insertion dans un arbre AVL
    Bonjour,
    Je suis étudiant en science informatique et dans le cadre d'un projet nous sommes amenés à créer des procédures de gestion capable d'insérer / supprimer des éléments contenus dans un arbre binaire de type AVL.

    Je viens de taper mon code mais j'obtiens des erreurs de segmentation, je crois que le passage de pointeurs avec la récursivité ne fait pas bon ménage...

    En fait, ce qui me pose problème ce n'est qu'une seule procédure : celle qui permet de calculer le nombre d'équilibre d'un élément. Il s'agit de déterminer la différence entre la hauteur de son fils droit et de sont fils gauche .

    Je vous joint ici bas le code nécessaire à la compréhension du problème :

    1. Procédure atomique utilisées dans la procédure principale :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    	(* Ensemble des procedures / fonctions  atomiques *)
    		FUNCTION is_empty (head : tree) : boolean;
    			BEGIN
    			IF head = NIL THEN
    				is_empty := true
    			ELSE
    				is_empty := false;
    			END;
     
    		FUNCTION is_a_leaf (head : tree) : boolean;
    			BEGIN
    			IF (head^.r_s = NIL) AND (head^.l_s = NIL)  THEN
    				is_a_leaf := true
    			ELSE
    				is_a_leaf := false;
    			END;
     
    		FUNCTION left_son (head : tree) : tree;
    			BEGIN
    				IF is_empty (head) THEN
    					left_son := NIL
    			        ELSE
    				        left_son := head^.l_s;
    			END;
     
    		FUNCTION right_son (head : tree) : tree;
    			BEGIN
    				IF is_empty (head) THEN
    					right_son := NIL
    				ELSE
    					right_son := head^.r_s;
    			END;
     
    	(* *)
    2. Code de la procédure proprement dite :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
     
    	(* Nombre d'équilibre *)
    		FUNCTION balanced_nbr (head : tree) : integer;
    			VAR jumper : tree;
     
    			(* Hauteur d'un arbre *)
    				FUNCTION height (head : tree) : integer;
    					VAR jumper : tree;
     
    						FUNCTION max (a, b : integer) : integer;
    							BEGIN
    							IF a > b THEN
    								max := a
    							ELSE
    								max := b;
    							END;
    					BEGIN
    					new (jumper);
    					jumper := head;
    					IF is_a_leaf (jumper) OR is_empty (jumper) THEN
    						height := 0
    					ELSE
    						height := 1 + max ( height (left_son (jumper)) , height (right_son (jumper)));
     
    					END;			
    			BEGIN
    			new (jumper);
    			jumper := head;
    			balanced_nbr := height (right_son (jumper)) - height (left_son (jumper));
     
    			END;
     
    	(* *)
    Le code posant problème se situe aux ligne 23 et 29 je pense. mais je ne vois pas comment résoudre cette impasse.

    Vous remarquerez aussi qu'il s'agit d'un code structuré en langage impératif, il n'est pas encore question de POO.
    Merci d'avance.

    PS : Je suis preneur de commentaires et suggestions constructives : N'hésitez pas !

  2. #2
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    Octobre 2011
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2011
    Messages : 12
    Points : 15
    Points
    15
    Par défaut
    Après quelques mois d’inactivité, je dépoussière le topique pour donner les sources fonctionnelles que j'ai pondu sur ce problème pour ceux qui en aurait besoin.

    Si vous avez besoin du rapport explicatif qui va avec ce code, merci de me le faire savoir, je le mettrai alors en ligne.

    Bonne journée,
    Dorian.
    Fichiers attachés Fichiers attachés

  3. #3
    Rédacteur/Modérateur

    Avatar de Roland Chastain
    Homme Profil pro
    Enseignant
    Inscrit en
    Décembre 2011
    Messages
    4 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Décembre 2011
    Messages : 4 062
    Points : 15 353
    Points
    15 353
    Billets dans le blog
    9
    Par défaut
    Citation Envoyé par dorian100 Voir le message
    Si vous avez besoin du rapport explicatif qui va avec ce code, merci de me le faire savoir, je le mettrai alors en ligne.
    Oui, c'est une bonne idée. Pour ma part je ne sais ni ce qu'est une "procédure atomique" ni un arbre "de type AVL".
    Mon site personnel consacré à MSEide+MSEgui : msegui.net

  4. #4
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    Octobre 2011
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2011
    Messages : 12
    Points : 15
    Points
    15
    Par défaut
    Pour définir simplement ce qu'est un arbre AVL, le plus simple est de consulter la page wikipedia à ce sujet :
    ICI
    ou encore ceci :
    ICI
    Et ensuite, pour bien comprendre le mode de fonctionnement du programme, voici la documentation qui va avec.
    Je tiens à préciser qu'il s'agissait d'un de mes premiers projet de programmation, les choses ayant quelque peu changées depuis.

    Voilà donc les liens vers la doc en pièce jointe.
    Images attachées Images attachées

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Insertion dans un arbre b
    Par miloko dans le forum Oracle
    Réponses: 1
    Dernier message: 12/12/2013, 12h11
  2. Insertion dans un arbre (algo tri de l'arbre)
    Par Self-Mao dans le forum Lisp
    Réponses: 9
    Dernier message: 30/07/2013, 14h55
  3. Insertion dans un arbre binaire Rouge-Noir (Red-Black Tree)
    Par monsieurouxx dans le forum Algorithmes et structures de données
    Réponses: 14
    Dernier message: 25/06/2010, 19h29
  4. Insertion dans un arbre binaire
    Par mikedavem dans le forum C
    Réponses: 3
    Dernier message: 08/06/2006, 08h50
  5. Insertion d'une occurence dans un arbre
    Par Gryzzly dans le forum Algorithmes et structures de données
    Réponses: 13
    Dernier message: 19/12/2005, 16h52

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo