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

Question

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).

mamiemando · Accepted Answer

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

Minautaure · Answer

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

mamiemando · Answer

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

Minautaure · Answer

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

mamiemando · Answer

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.

mamiemando · Answer

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
",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

thanx · Answer

i want thanx you

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

7 réponses

Newsletters