IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

saisir elements arbre binaire dans un tableau


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Profil pro
    Étudiant
    Inscrit en
    Octobre 2006
    Messages
    77
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2006
    Messages : 77
    Par défaut saisir elements arbre binaire dans un tableau
    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

  2. #2
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Par défaut
    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 ?

  3. #3
    Membre confirmé
    Profil pro
    Étudiant
    Inscrit en
    Octobre 2006
    Messages
    77
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2006
    Messages : 77
    Par défaut
    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

  4. #4
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Par défaut
    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.

  5. #5
    Membre confirmé
    Profil pro
    Étudiant
    Inscrit en
    Octobre 2006
    Messages
    77
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2006
    Messages : 77
    Par défaut
    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

  6. #6
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Par défaut
    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.

Discussions similaires

  1. Un arbre dans un tableau
    Par Oberown dans le forum Général JavaScript
    Réponses: 3
    Dernier message: 01/08/2006, 10h12
  2. Insertion dans un arbre binaire
    Par mikedavem dans le forum C
    Réponses: 3
    Dernier message: 08/06/2006, 07h50
  3. Le type Arbre binaire dans les bibliothèques standards ?
    Par sam69 dans le forum API standards et tierces
    Réponses: 6
    Dernier message: 10/05/2006, 13h50
  4. Choisir un élément au hasard dans un tableau
    Par ousunas dans le forum Langage
    Réponses: 1
    Dernier message: 25/02/2006, 19h50
  5. [langage] Compter des éléments dans un tableau
    Par helene22500 dans le forum Langage
    Réponses: 29
    Dernier message: 23/05/2005, 11h38

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo