Sujet Précédent Sujet Suivant

[C/Algo]Créer un arbre récursivement

Résolu/Fermé
Minautaure - 13 nov. 2006 à 23:38
 thanx - 28 sept. 2008 à 20:12
Salut,

j'aurais besoin d'aide pour écrire l'algo pour la création de l'arbre, ainsi que pour le parcours de l'arbre.

Merci 

Exercice 1 Création du quad-tree
   1. Charger les fichiers d’entrée.
L’image décrivant l’altitude est carrée et admet comme nombre de pixels coté un exposant de 2. Charger cette image.
Interprétez le fichier de description pour récupérer les paramètres qui y sont stockés.

  2. Construction du Quad-tree
A partir de l’image, construire un quad-tree sur le principe suivant :
- On associe à la racine de l’arbre l’image entière.
- Si la partie de l’image d’altitude associée à un noeud admet des variations fortes (différence d’altitude
maxi > valeur indiquée dans le fichier de description), alors il faut subdiviser.
- Subdiviser consiste à découper la zone en 4 quartiers (NW,NE,SW,SE). Le noeud subdivisé admet
donc 4 fils à chacun desquels est associé un quartier de l’image (cf. figure)
+-------+-------+
|       |       |
|  NW   |   NE  |
|       |       |
+-------+-------+
|       |       |
|  SW   |   SE  |
|       |       |
+-------+-------+

Une fois ce quad-tree généré, chaque feuille est associée à une zone de l’image, on peut donc calculer une altitude
moyenne et une densité de végétation moyenne associée à cette feuille.


Exercice 2 Création du modèle géométrique du sol
   1. Vertex-Array du sol
Réalisez une fonction qui construit un Vertex-Array stockant la géométrie du sol à partir des
altitudes stockées dans les feuilles du quad-tree. La construction des tableaux de description
de la géométrie pourront être réalisés en plusieurs étapes : un premier parcours de l’arbre pour
mémoriser les sommets (en évitant les doublons) et un second parcours pour définir les faces
du maillage constituant le sol.

   2. Les problèmes de noeuds en T
Pour éviter les problèmes générés par les noeuds en T , la
fonction construira une liste de triangles énumérant tous les triangles formé par le centre de la facette carré et admettant pour autres sommets, deux sommets consécutifs du bord de la
facette (les triangles de couleurs sur la figure).
A voir également:

7 réponses

Réponse 1 / 7
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 7 749
14 nov. 2006 à 00:18
Bon je n'ai pas lu l'exercice dans le détail mais voici déjà les bases pour construire un arbre. Ici je fais un arbre binaire (fils gauche fils droit) pour que ce soit plus simple et ensuite tu adaptes à ton exercice : 

#include <stdlib.h>
#include <stdio.h>

struct noeud{
  struct noeud * fils_gauche;
  struct noeud * fils_droit;
  int data; // je stocke un entier dans chaque noeud de l'arbre
};

typedef noeud * arbre;

void ajouter_fils_gauche(noeud * r,int x){
  r->fils_gauche = (struct noeud *)malloc(sizeof(struct noeud));
  r->fils_gauche->data = x;
}

void ajouter_fils_droit(noeud * r,int x){
  r->fils_droit = (struct noeud *)malloc(sizeof(struct noeud));
  r->fils_droit->data = x;
}

void afficher_arbre(arbre a){
  printf("%d\n",x)
  afficher_arbre(a->fils_gauche);
  afficher_arbre(a->fils_droit);
}

Bonne chance
8
Réponse 2 / 7
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 7 749
14 nov. 2006 à 16:47
Correction de mon premier post 
void ajouter_fils_gauche(noeud * r,int x){
  r->fils_gauche = (struct noeud *)calloc(1,sizeof(struct noeud));
  r->fils_gauche->data = x;
}

void ajouter_fils_droit(noeud * r,int x){
  r->fils_droit = (struct noeud *)calloc(1,sizeof(struct noeud));
  r->fils_droit->data = x;
}

void afficher_arbre(arbre a){
  printf("%d\n",x)
  if (a->fis_grauche) afficher_arbre(a->fils_gauche);
  if (a->fils_droit) afficher_arbre(a->fils_droit);
}

Dans ton cas tu as 4 fils au lieu de 2 mais c'est le même principe. La fonction afficher_arbre fait un parcours de l'arbre. Les fonction ajouter fils servent à rajouter/remplacer un noeud fils d'un noeud r de l'arbre.

Bonne chance
3
Réponse 3 / 7
Minautaure
14 nov. 2006 à 07:22
Salut mamiemando;

Voici ma structure :
http://cjoint.com/data/lnoIhCHFtO.htm

le code qui devrait créer l'arbre :
http://cjoint.com/data/lnoNvKVllB.htm

PS : je n'ai mis que la partie de mon code qui pose problème et des printf un peu partout pour voir le déroulement

La fonction de création de l'arbre est mauvaise car elle ne fait pas ce qu'il faut.
L'image est chargée plusieurs fois alors qu'elle ne doit l'être qu'une fois et donc que les valeurs qui doivent être différentes pour chaque noeud de l'arbre sont toujours les mêmes

Je ne sais pas comment faire pour apporter des modifs au code pour que ça fasse ce qu'il faut et aurait donc besoin d'aide pour écrire un algo correct

Merci d'avance
1
Réponse 4 / 7
Minautaure
14 nov. 2006 à 10:01
J'ai pas compris comment faire ce que tu proposes.
Pourrais tu me donner un exemple ?
De plus, comment gérer le fait que l'image ne doit être chargée qu'une seule fois et pour faire le test de la condition sur chaque portion de l'image ainsi découpée

Merci
1

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 7
thanx
28 sept. 2008 à 20:12
i want thanx you
1
Réponse 6 / 7
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 7 749
14 nov. 2006 à 09:23
Ton createQuadTree doit comporter un noeud auquel raccrocher le nouveau sous arbre (en général ce noeud est une feuille de l'arbre courant), et le sous-arbre à raddorcher (éventuellement composé juste d'un noeud). Mais sinon ce que tu as fait est dans l'idée...

Bonne chance
0
Réponse 7 / 7
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 7 749
14 nov. 2006 à 16:43
Cf les fonction ajouter_fils_droit et ajouter_fils_grauche, c'est le même principe sauf que toi tu en as 4 au lieu de 2.
-1

Discussions similaires

créer une adresse gmail pour une autre personne
Emma33000 -
Emma33000 -

2 réponses