Discussion :

[Dundruma]

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
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 ?