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 :

Transformation d'un arbre binaire en arbre binaire de recherche


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2019
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Cameroun

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : janvier 2019
    Messages : 1
    Points : 1
    Points
    1
    Par défaut Transformation d'un arbre binaire en arbre binaire de recherche
    svp j'ai besoin de l'algo permettant de tranformer un arbre binaire en arbre binaire de recherche

  2. #2
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    juillet 2018
    Messages
    46
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Tarn (Midi Pyrénées)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : juillet 2018
    Messages : 46
    Points : 71
    Points
    71
    Par défaut
    Bonjour,

    Lors de la transformation, tu ne sembles pas vouloir utiliser le lien parent-fils présent dans l'arbre de départ. Le problème se ramènerait donc à créer un ABR avec un ensemble de valeur donnée.
    Alors je pense que le moyen le plus simple est de trier ces valeurs puis:
    - si tu l'équilibrage de l'ABR ne t'intéresse pas, tu peux juste considérer l'arbre "linéaire" dont la racine est le plus grand et chaque fils gauche est l'élément juste en dessous (pas de fils droit).
    - si tu veux un ABR équilibré, une fonction récursive fait très bien l'affaire: Ta fonction F coupes ta liste de taille N triée en trois morceaux de tailles (dans l'ordre) (N-1)//2, 1 et (N-1)-(N-1)//2, et tu retournes l'arbre avec: pour racine le morceau de taille 1; pour fil gauche F(morceau de taille (N-1)//2); pour fil droit F(morceau de taille (N-1)-(N-1)//2). Et le cas de base se présente si la taille est de 1 ou 0 (on peut même considérer seulement 0)

Discussions similaires

  1. Suppression dans un arbre binaire de recherche
    Par zeine77 dans le forum Langage
    Réponses: 1
    Dernier message: 11/05/2007, 21h40
  2. Transformation en un arbre binaire
    Par lylia SI dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 27/09/2006, 20h03
  3. Réponses: 3
    Dernier message: 31/12/2005, 13h30
  4. Réponses: 11
    Dernier message: 07/04/2004, 14h06
  5. [Arbre binaire de Recherche]
    Par Giovanny Temgoua dans le forum Algorithmes et structures de données
    Réponses: 11
    Dernier message: 06/02/2004, 12h45

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