svp j'ai besoin de l'algo permettant de tranformer 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
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)
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager