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

Exercices Python Discussion :

Calculer la longueur d'un arbre binaire


Sujet :

Exercices Python

  1. #1
    Futur Membre du Club
    Homme Profil pro
    Directeur technique
    Inscrit en
    avril 2020
    Messages
    5
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 59
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Directeur technique
    Secteur : Enseignement

    Informations forums :
    Inscription : avril 2020
    Messages : 5
    Points : 5
    Points
    5
    Par défaut Calculer la longueur d'un arbre binaire
    Bonjour,
    J'ai un TD à rendre sur le tri d'une liste d'entiers selon le procédé "tri par tas" ==> heap sort
    Bien sur j'ai plusieurs exercices à faire, voici le premier :

    1)° On définit, la hauteur p de l'arbre comme la longueur maximale des branches.
    Un arbre réduit à un unique élément (c'est à dire sa racine) est considérée de hauteur p = 0
    Exprimer p en fonction de n en utilisant la fonction log (logarithme en base 2) et des fonctions Nom : td_liste_python_1.JPG
Affichages : 102
Taille : 9,1 Ko
    Indication : commencer par encadrer n en fonction de p.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    ## import modules
    from math import log2
     
    # # Définir la hauteur p de l'arbre
    # Un arbre de nœuds binaire
    class Node:
        # Constructeur pour créer les racines : père, fils gauche et fils droit
        def __init__(self, data):
            self.data = data
            self.p = None
            self.l = None
            self.r = None
     
    # Calculer "maxDepth" de l'arbre -- Le nbre de noeud
    def maxDepth(node):
        if node is None:
            return -1
        else:
            # Calcule la hauteur de chaque sous famille
            lDepth = maxDepth(node.l)
            rDepth = maxDepth(node.r)
     
            # Utilisation de la largeur
            if (lDepth > rDepth):
                return lDepth + 1
            else:
                return rDepth + 1
     
     
    # Test
    root = Node(1)
    root.l = Node(2)
    root.r = Node(3)
    root.l.l = Node(4)
    root.l.r = Node(5)
    root.r.l = Node(6)
    root.r.r = Node(7)
    root.l.l.l = Node(8)
    root.l.l.r = Node(9)
    root.l.l.l = Node(10)
    root.l.l.r = Node(11)
    root.r.l.l = Node(12)
    J'obtiens bien le nombre 3 (pour 4 étages).

    Mais je n'ai pas utilisé la méthode demandée dans le TD, donc je voulais savoir comment je devais m'y prendre après avoir importé log2 ?

  2. #2
    Expert éminent sénior
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    juin 2008
    Messages
    17 532
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : juin 2008
    Messages : 17 532
    Points : 30 251
    Points
    30 251
    Par défaut
    Salut,

    Citation Envoyé par Dundruma Voir le message
    donc je voulais savoir comment je devais m'y prendre après avoir importé log2 ?
    Avant de programmer, il faut savoir ce qu'on veut.

    Cherchez un peu sur Internet ou griffonnez une feuille de papier pour le démontrer, vous trouverez cette relation entre hauteur de l'arbre et nombre de nœuds: 2h-1 <= n <= 2h - 1.

    Ce qui devrait vous donner des idées pour sortir la hauteur en fonction de log2(n).

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

Discussions similaires

  1. Calcul nombre de feuille dans un arbre binaire
    Par Etoile_ dans le forum Débuter avec Java
    Réponses: 4
    Dernier message: 08/02/2012, 23h07
  2. Arbre binaire et longueur d'une ligne
    Par ALIAS200 dans le forum Débuter
    Réponses: 7
    Dernier message: 09/05/2008, 16h02
  3. Afficher un arbre binaire avec sa structure
    Par PhoneKilleR dans le forum C
    Réponses: 7
    Dernier message: 23/04/2008, 23h24
  4. Arbre binaire
    Par Heaven dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 02/02/2004, 19h01
  5. [LG]probleme de creation arbre binaire
    Par jsaviola dans le forum Langage
    Réponses: 2
    Dernier message: 06/01/2004, 20h57

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