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.

[babylone_59]

Cet algo affiche les valeurs de mon arbre dans un tableau?J'aurai dans la premiere casse de mon tableau la valeur ab par exemple?
Il n'est pas necessaire d'utiliser une boucle pour afficher toutes les valeurs?
En fait mon arbre affiche une valeur dans le tableau que lorsque le pointeur affiche 0?

[millie]

Il n'est pas necessaire d'utiliser une boucle pour afficher toutes les valeurs?

C'est un algorithme récursif, donc pas de boucle...

Ca transforme un arbre comme le tableau présenté à mon deuxième post.

[babylone_59]

ok jusque la ça va!
Maintenant d'aprés ce tableau , il faut que je range mes valeurs de façona obtenir mes differents termes, et je mets c valeurs dans un autre tableau?

[ptipoutche]

Il faut que tu passe par la simplification de DE MORGAN et ensuite tu fait Karnaugh. Après c tous simple