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 ?

[wiztricks]

Salut,

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: 2^h-1 <= n <= 2^h - 1.

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

- W