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

  1. #1
    Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    janvier 2019
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Drôme (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2019
    Messages : 6
    Points : 2
    Points
    2

    Par défaut Créer un arbre binaire

    Bonjour,
    je souhaite créer un arbre binaire avec et seulement un parcours préfixe et suffixe:
    prefixe: 1 2 5 6 8 9 10 11
    suffixe: 5 6 2 11 10 9 8 1
    ce que je sais:
    - la racine est le début du tableau prefixe et la fin de tableau suffixe
    - la première valeur du tableau suffixe est la valeur la plus à gauche
    - la deuxième valeur du tableau prefixe est la première valeur a droite depuis la racine
    - l'avant dernière valeur de tableau suffixe est la première valeur a gauche depuis la racine

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 265
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 265
    Points : 4 741
    Points
    4 741

    Par défaut

    Est-ce que tu sais représenter cela sous forme de dessin ?
    Personnellement, je ne sais pas le faire, parce que je ne comprends rien à tes données.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    janvier 2019
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Drôme (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2019
    Messages : 6
    Points : 2
    Points
    2

    Par défaut

    Il faut une fonction qui prend comme entrée deux tableaux: un tableau prefixe et un tableau suffixe et qui donne un arbre binaire

    Un dessin
    Prrf: 1 4 8 10 2 14 12 18 9
    Suf: 10 8 4 14 2 12 4 9 18 1
    On a arbre binaire:
    1
    --4
    ----8
    --------10
    ----2
    ------14
    -------12
    --18
    ----9

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 265
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 265
    Points : 4 741
    Points
    4 741

    Par défaut

    J'ai trouvé ça : Nom : parcours arbre.png
Affichages : 51
Taille : 75,8 Ko

    Et c'est tout de suite plus clair.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    janvier 2019
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Drôme (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2019
    Messages : 6
    Points : 2
    Points
    2

    Par défaut

    Voila, et le but c'est avec le parcours infixe et prefixe (stocké dans deux tableaux) c'est de créer un arbre binaire (qu'on aura au préalablement vérifié si c'est possible de créer un arbre binaire avec ces deux tableaux->que voici le code en c)
    Code C : 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
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    int est_binaire(int* t_pre,int* t_post)
    {
    	int i=0;
    	int j=2;
    	int racine;
    	racine=t_pre[0];
    	if(racine==t_post[7])
    	{
    		int gauche;
    		gauche=t_pre[1];	//deuxieme
     
    		int droite;
    		droite=t_post[6];	//avant dernier
     
    		//determine position de la valeur de droite dans le tableau t_pre
    		int position_droite_t_pre=0;
    		int k=0;
    		while(t_pre[k]!=droite)
    		{
    			position_droite_t_pre++;
    			k++;
    		}
     
    		//verifie branche gauche:
    		while(gauche!=t_post[i])
    		{
    			while(t_pre[j]!=t_post[i])
    			{
    				if(t_pre[j]==droite) return 0;
    				j++;
    			}
    			j=2;
    			i++;
    		}
    		i++;
    		j=position_droite_t_pre;
    		//verifie branche droite:
    		while(droite!=t_post[i])
    		{
    			while(t_pre[j]!=t_post[i])
    			{
    				if(t_pre[j]==8) return 0;
    				j++;
    			}
    			j=position_droite_t_pre;
    			i++;
    		}
    		return 1;
    	}
    	return 0;	
    }

  6. #6
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 265
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 265
    Points : 4 741
    Points
    4 741

    Par défaut

    Ce que ton prof attend de toi, ce n'est pas que tu recopies des trucs que des gens te donnent, c'est que tu fasses toi-même. Là, le problème est posé. Tu as trouvé quelque part une procédure qui vérifie si les tableaux Préfixe et Suffixe définissent un arbre binaire. Ca peut être une source d'inspiration.

    En entrée, tu as ces 2 structures. En sortie, quel type de structure tu dois avoir ?
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  7. #7
    Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    janvier 2019
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Drôme (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2019
    Messages : 6
    Points : 2
    Points
    2

    Par défaut

    En entrée j'aurai deux tableaux et en sortie un arbre binaire ?
    Je pense qu'il faut résoudre le problème de manière récursive et commencer par les sous arbre du bas pour remonter.

    Y'a beaucoup de condition j'arrive pas vraiment a simplifier le problème

  8. #8
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 265
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 265
    Points : 4 741
    Points
    4 741

    Par défaut

    Je reprends ton 1er jeu de données :
    prefixe: 1 2 5 6 8 9 10 11
    suffixe: 5 6 2 11 10 9 8 1

    1 est la racine. la chaine prefixe nous dit que 1 a un premier enfant : 2, et la chaine des suffixe nous dit que 1 a également comme enfant 8
    On a donc 2 sous arbres, qui commencent respectivement par 2 et par 8

    L'arbre qui commence par 2 :
    prefixe : 2 5 6
    suffixe : 5 6 2
    Et l'arbre qui commence par 8 :
    préfixe : 8 9 10 11
    suffixe : 11 10 9 8

    Et on recommence.
    Quand on doit recommencer le même traitement, et éventuellement recommencer plusieurs fois le même traitement, la technique qu'il faut utiliser, c'est la récursivité.
    On appelle au départ Traitement('1 2 5 6 8 9 10 11', '5 6 2 11 10 9 8 1')

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    Procédure Traitement (prefixe, suffixe)
    sous_arbre_gauche = ...   Ici, la procédure va devoir trouver que sous_arbre_gauche = (2 5 6 , 5 6 2)
    sous_arbre_droite = ...   Ici, la procédure va devoir trouver que sous_arbre_droite = ( 8 9 10 11, 11 10 9 8  )
    
    Call Traitement ( sous_arbre_gauche.prefixe, sous_arbre_gauche.suffixe )     ... ici , la procédure traitement s'appelle ell-même, avec comme paramètre un sous-arbre de l'arbre de départ.
    si sous_arbre_droite <> sous_arbre_gauche alors
       Call Traitement ( sous_arbre_droite.prefixe, sous_arbre_droite.suffixe )
    fin
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  9. #9
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 782
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 782
    Points : 4 525
    Points
    4 525

    Par défaut

    salut

    je ne comprend pas pourquoi tu as besoin des 2 tableau pour construir ton arbre

    si tu sais que le premier tableau est en prefix il suffit de reconstruire l'arbre en prefix et ensuite de le relire en sufix est de comparer
    le tableau resultant au tableau fournis
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  10. #10
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 265
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 265
    Points : 4 741
    Points
    4 741

    Par défaut

    Il y a besoin des 2 tableaux.
    Regarde l'exemple que j'ai posté ( le dessin avec les ronds jaunes), la branche en bas à gauche.

    Imaginons qu'on ait uniquement la structure prefixe.
    La séquence (4,8,9) est ambigüe.
    8 est fils de 4, c'est certain, mais 9 est-il fils de 8, ou fils de 4 et donc frère de 8 ?
    La structure Suffixe permet de lever l'ambiguïté.
    On aura dans Suffixe (9,8,4) dans un cas, et (8,9,4) dans l'autre.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  11. #11
    Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    janvier 2019
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Drôme (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2019
    Messages : 6
    Points : 2
    Points
    2

    Par défaut

    Merci pour m'avoir aidé,j'ai compris comment ca fonctionne,pour le reste je vais essayer de me débrouiller.

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

Discussions similaires

  1. [Python 3.X] Comment créer un arbre binaire à partir d'une liste en Python ?
    Par Providjek dans le forum Général Python
    Réponses: 3
    Dernier message: 17/10/2018, 19h30
  2. Créer un arbre binaire complet en C
    Par derreck dans le forum C
    Réponses: 8
    Dernier message: 28/12/2017, 00h22
  3. Créer un arbre binaire et l'afficher
    Par hellowo dans le forum Débuter
    Réponses: 9
    Dernier message: 19/03/2015, 22h38
  4. Afficher un arbre binaire avec sa structure
    Par PhoneKilleR dans le forum C
    Réponses: 7
    Dernier message: 24/04/2008, 00h24
  5. Arbre binaire
    Par Heaven dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 02/02/2004, 20h01

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