Correction TD2 Arbre [PDF]

Zitiervorschau

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; }