Quelques fonctions utiles sur les arbres.

6.5. Quelques fonctions utiles sur les arbres.#

Dans tout le document, on considère l’arbre suivant

from binarytree import build
# Build a tree from list representation
values = [ 7 , 3 , 2 , 6 , 9 , None , 1 , 5 , None ,
10 , 8 , None , None , 11 , None , 12 , 13 , None , None ,14 ]
arbre = build(values)
print(arbre)

            __________7
           /           \
          3______       2___
         /       \          \
     ___6        _9         _1
    /           /  \       /
  _5          _10   8     11
 /  \        /
12   13     14

On considère que la profondeur de la racine est de 0.

  1. Donner la profondeur des nœuds

    1. 7

    2. 9

    3. 14

  2. Donner la hauteur de l’arbre

  3. Donner la taille de l’arbre

6.5.1. Écriture des fonctions#

Écrire une fonction permettant de trouver la profondeur d’un nœud[1].

Écrire une fonction récursive permettant de déterminer la hauteur d’un arbre.

Hide code cell content 
def hauteur(arbre):
    if arbre is not None:
        return 1 + max(hauteur(arbre.left), hauteur(arbre.right))
    else:
        return 0

On doit obtenir

hauteur(arbre)

5

Écrire une fonction récursive permettant de déterminer la taille d’un arbre.

Hide code cell content 
def taille(arbre):
    if arbre is not None:
        return 1 + taille(arbre.left) + taille(arbre.right)
    else:
        return 0

On doit obtenir

taille(arbre)

13
Contenu