Scribd Logo
Importer

Bienvenue sur Scribd !

  • 400 vues

    Correction TD2 Arbre

    Transféré par

    Chouaib El Khaoudi
    Un arbre binaire de recherche est défini. Les parcours préfixe, infixe et postfixe sont décrits. Des exemples d'impression d'arbres binaires selon ces parcours sont donnés. Des algorithmes de recherche du minimum et maximum, d'insertion et de suppression dans un arbre binaire de recherche sont présentés.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Correction TD2 Arbre

    Transféré par

    Chouaib El Khaoudi
    400 vues4 pages
    Un arbre binaire de recherche est défini. Les parcours préfixe, infixe et postfixe sont décrits. Des exemples d'impression d'arbres binaires selon ces parcours sont donnés. Des algorithmes de recherche du minimum et maximum, d'insertion et de suppression dans un arbre binaire de recherche sont présentés.

    Description originale:

    les arbres structures

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Un arbre binaire de recherche est défini. Les parcours préfixe, infixe et postfixe sont décrits. Des exemples d'impression d'arbres binaires selon ces parcours sont donnés. Des algorithmes de recherche du minimum et maximum, d'insertion et de suppression dans un arbre binaire de recherche sont présentés.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    400 vues4 pages

    Correction TD2 Arbre

    Transféré par

    Chouaib El Khaoudi
    Un arbre binaire de recherche est défini. Les parcours préfixe, infixe et postfixe sont décrits. Des exemples d'impression d'arbres binaires selon ces parcours sont donnés. Des algorithmes de recherche du minimum et maximum, d'insertion et de suppression dans un arbre binaire de recherche sont présentés.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    Vous êtes sur la page 1sur 4

    Correction TD2

    Un arbre binaire de recherche est un arbre binaire tel que pour tout nœud N, toutes les valeurs
    du sous-arbe gauche de N sont inférieures ou égales à la valeur de N, et toutes les valeurs du
    sous-arbre droit de N sont supérieures à la valeur de N

    Dans un parcours, tous les nœuds de l’arbre sont visites.


    Déf. Dans un parcours préfixe, chaque nœud est visite avant que ses enfants soient visites.
    Déf. Dans un parcours postfixe, chaque nœud est visite après que ses enfants sont visites.
    Déf. Dans un parcours infixe, chaque nœud est visite après son ` enfant gauche mais avant son
    enfant droit.
    Un parcours infixé imprime le sous-arbre gauche, puis imprime la racine, puis le sous-arbre
    droit.

    Exercice 2 Impression Préfixe/Suffixe/Infixe d'un arbre binaire

    Préfixé : 6 4 1 3 2 58 7 13 11 10 9 12 14
    Infixé : 1 2 3 4 5 6 7 8 9 10 11 12 13 14
    Postfixé : 2 3 1 5 4 7 9 10 12 11 14 13 8 6

    Exercice 3
    void print_inorder (node* A) {
    if (A != NULL) {
    print_inorder(A->left);
    printf("%d ",A->key);
    print_inorder(A->right);
    }
    }
    Exercice 4
    1/ Recherche du minimum dans un arbre binaire de recherche
    int minimum (node* A) {
    if (A == NULL) {
    return -1;
    }
    if (A->left == NULL) {
    return A->key;
    }
    return minimum(A->left);
    }

    2/ Recherche du maximum dans un arbre binaire de recherche


    int maximum (node* A) {
    if (A == NULL) {
    return -1;
    }
    if (A->right == NULL) {
    return A->key;
    }
    return maximum(A->right);
    }

    Exercice 5 Insertion de v dans l'arbre A


    Node* insert (int v, node* A) {
    node *p, *q;
    if (A == NULL){/* arbre vide*/
    A = (node *) malloc(sizeof (node));
    A->key = v;
    A->right = NULL;
    A->left = NULL;
    return(A);
    }
    p = A;
    while (p != NULL) { /* trouver l’emplacement pour l’insertion */
    q = p; /* sauvegarder le parent avant d’aller vers les enfants */
    if (v < p->key)
    p = p->left; /* aller vers les enfants de gauche */
    else p = p ->right; /* aller les enfants de droite */
    }
    p = (node *) malloc(sizeof (node));
    p ->key = v;
    if (v < q->key)
    q->left = p; /* relier le parent référencé par q au nouvel élément comme enfant gauche*/
    else
    q->right = p; /* relier le parent référencé par q au nouvel élément comme enfant droit
    return(p);
    }
    Exercice 6 Suppression de v dans l'arbre A */

    bool supprime(int v, Arbre* A) {


    if (A == NULL) return false;
    if (v == A->key) {
    if (A->gauche == NULL) {
    Arbre* tmp = A->droite;
    free (A);
    A = tmp;
    return true;
    }
    if (A->droite == NULL) {
    Arbre* tmp = A->gauche;
    free (A);
    A = tmp;
    return true;
    }
    if (A->droite == NULL && A->gauche == NULL){
    free(A);
    return true;
    }
    int val = minimum (A->droite);\\ minimum (A->droite) retourne la plus petite valeur (min)
    dans le sous arbre droit de A qui n’a pas de fils gauche. Ex : dans l’arbre précédent, pour
    supprimer la valeur A=6, on remplace 6 par 7.

    A->key = val;
    supprime(val, A->droite);
    return true;
    }
    else
    if (v < A->key)
    return supprime(v, A->gauche);
    else
    return supprime(v, A->droite);
    }

    int minimum (node* A) {


    if (A == NULL) {
    return -1;
    }
    if (A->left == NULL) {
    return A->key;
    }
    return minimum(A->Right);
    }
    Exercice 7 :
    //méthode récursive
    int * recherche(Arbre *A, int v){
    if(A==NULL) return 0;
    else if (v == A->val) return 1;
    else{
    if(v > A->val)
    return recherche(A->droite,v);
    else
    return recherche(A->gauche,v);
    }
    }

    //méthode itérative
    int * recherche(Arbre *A, int v){
    while(A!=NULL && v!=A->val){
    if(v > A->val)
    A=A-> droite;
    else
    A=A->gauche;
    }
    if(A==NULL)
    return 0;
    else
    return 1;
    }

    Vous aimerez peut-être aussi