Discussion :

[babylone_59]

Bonjour a tous!
J'aimerai dresser un algorithme qui saisi les élements d'un arbre binaire(sous la somme d'une somme de produit) ,dans un tableau.
Comment faire?
Aidez moi SVP!
merci d'avance

[millie]

J'ai pas compris !

- Tu veux implémenter une arbre binaire par un tableau ?
- Ou tu disposes d'un arbre binaire (avec les feuilles = chiffre et les autres noeuds des opérations) et tu souhaites le transformer en une chaine de caractère ?

[babylone_59]

je possede un arbre binaire(avec des pointeurs)est j'aimerai mettre les elements de cette arbre dasns un tableau
Voici a quoi ressemble mon arbre

---+---
l l
. .
l l
--- ---
a b a c
et j'aimerai mettre ab et ac dans un tableau

[millie]

Tirer de Wikipedia : (avec comme recherche : implémentation d'un arbre binaire par un tableau)

Les arbres binaires peuvent aussi être rangés dans des tableaux, et si l'arbre est un arbre binaire complet, cette méthode ne gaspille pas de place, et la donnée structurée résultante est appelée un tas. Dans cet arrangement compact, un nœud a un indice i, et (le tableau étant basé sur des zéros) ses fils se trouvent aux indices 2i+1 et 2i+2, tandis que son père se trouve (s'il existe) à l'indice floor((i-1)/2). Cette méthode permet de bénéficier d'un encombrement moindre, et d'un meilleur référençage, en particulier durant un parcours préfixe. Toutefois, elle requiert une mémoire contigüe, elle est coûteuse s'il s'agit d'étendre l'arbre et l'espace perdu (dans le cas d'un arbre binaire non complet) est proportionnel à 2h - n pour un arbre de profondeur h avec n nœuds.



Edit Indente ton arbre en utilisant la balise CODE, car je suis pas sûr que ce soit ça que tu souhaites. Mais je pense que si.

[babylone_59]

En fait je possede un arbre binaire composé de pointeur et je recherche un algorithme permettant de mettre les différents termes de cet arbre dans un tableau.
Je n'arrive pas a dresser l'algo pour cette étape.
Merci de votre aide

[millie]

Lis bien ce que j'ai écrit :

un nœud a un indice i, et (le tableau étant basé sur des zéros) ses fils se trouvent aux indices 2i+1 et 2i+2

Il suffit de parcourir ton arbre, et à chaque noeud que tu rencontres, tu peux mettre ses fils dans le tableau grâce à la formule précédente. Ceci récursivement.

Tu utilises une fonction du type :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
Procédure ecrireNoeud(Arbre n (sous arbre), Entier numeroNoeud)
 
 T[numeroNoeud] <- racine(n);
 
 Si n n'est pas une feuille
   | fg <- arbreGauche(n);
   | fd <- arbreDroit(n);
   | ecrireNoeud(fg, 2*numeroNoeud+1);
   | ecrireNoeud(fd, 2*numeroNoeud+2);

Je t'ai fait une version simplifiée avec un arbre binaire parfait, et je n'ai pas écrit la fonction d'initialisation histoire de ne pas te faire tout le boulot et te laisser un peu réflechir.