TD Arbre dichotomique de recherche
TD : TD Arbre dichotomique de recherche. Recherche parmi 298 000+ dissertationsPar Loïc Jurgawczynski • 21 Février 2018 • TD • 1 398 Mots (6 Pages) • 702 Vues
//
// main.c
// TP3_SD
//
// Created by JURGAWCZYNSKI on 17/05/2017.
// Copyright © 2017 JURGAWCZYNSKI. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
#define N 9;
typedef struct _produit {
int val, eq; // valeur stockée et constante d'équilibre
struct _produit *fg, *fd; // pointeurs vers les noeuds fils
} PRODUIT, * AVL;
// Question 2 \\
AVL creerProduit(int n) {
AVL arbre = (AVL)malloc(sizeof(PRODUIT));
arbre->val = n;
arbre->eq = 0;
arbre->fg = NULL;
arbre->fd = NULL;
return arbre;
}
// Question 3 \\
AVL ajouterValeur(int n, AVL arbre) { // ajout sans rééquilibrage
if(arbre == NULL) {
// printf("%d ajouté\n", n);
return creerProduit(n);
}
if(arbre->val > n)
arbre->fg = ajouterValeur(n, arbre->fg);
else
arbre->fd = ajouterValeur(n, arbre->fd);
return arbre;
}
// Question 4 \\
void afficher(AVL arbre, int p) {
int i;
if(arbre != NULL) {
afficher(arbre->fd, p+1);
for(i=1 ; i<p; i++)
printf("--");
printf("%d", arbre->val);
printf(" (%d)\n", arbre->eq);
afficher(arbre->fg, p+1);
}
}
// Question 5 \\
int hauteurArbre(AVL arbre) {
if(arbre == NULL)
return 0;
int gauche = 1 + hauteurArbre(arbre->fg);
int droite = 1 + hauteurArbre(arbre->fd);
if(gauche > droite)
return gauche;
else
return droite;
}
// Question 6 \\
void maj_eq(AVL arbre) {
if(arbre != NULL) {
maj_eq(arbre->fg);
maj_eq(arbre->fd);
arbre->eq = hauteurArbre(arbre->fg)-hauteurArbre(arbre->fd);
}
}
// Question 7 \\
AVL rotationDroite(AVL arbre) {
AVL pFg=NULL, pFdFg=NULL;
if (arbre!=NULL) {
pFg = arbre->fg;
if(pFg!=NULL) {
pFdFg = pFg->fd;
pFg->fd = arbre;
}
}
arbre->fg = pFdFg;
return pFg;
}
// Question 8 \\
AVL rotationGauche(AVL arbre) {
AVL pFd=NULL, pFgFd=NULL;
if (arbre!=NULL) {
pFd = arbre->fd;
if(pFd!=NULL) {
pFgFd = pFd->fg;
pFd->fg = arbre;
}
}
arbre->fd = pFgFd;
return pFd;
}
// Question 9 \\
AVL rgd(AVL arbre) {
arbre->fg = rotationGauche(arbre->fg);
arbre = rotationDroite(arbre);
return arbre;
}
AVL rdg(AVL arbre) {
arbre->fd = rotationDroite(arbre->fd);
arbre = rotationGauche(arbre);
return arbre;
}
AVL
...