Une classe pour représenter un arbre

On utilise une classe pour représenter un arbre binaire avec pour objectif de pouvoir afficher cet arbre, de calculer la profondeur maximale ou moyenne, de compter le nombre de chemin, d’itérer sur tous les noeuds.

Premier jet

class Noeud:
    def __init__(self, v):
        self.v = v
        self.left = None
        self.right = None


na = Noeud("A")
na.left = Noeud("B")
na.left.left = Noeud("C")
na.left.right = Noeud("D")
na.right = Noeud("E")

Afficher l’arbre

C’est toujours très utile pour vérifier que l’arbre qu’on a implémenté est bien celui qu’on avait en tête. Il faut donc parcourir tous les noeuds.

import textwrap


def graph():
    na = Noeud("A")
    na.left = Noeud("B")
    na.left.left = Noeud("C")
    na.left.right = Noeud("D")
    na.right = Noeud("E")
    return na


class Noeud:
    def __init__(self, v):
        self.v = v
        self.left = None
        self.right = None

    def __str__(self):
        rows = [str(self.v)]
        if self.left is not None:
            rows.append("+-" + textwrap.indent(str(self.left), "  ")[2:])
        if self.right is not None:
            rows.append("+-" + textwrap.indent(str(self.right), "  ")[2:])
        return "\n".join(rows)


na = graph()
print(na)

A
+-B
  +-C
  +-D
+-E

Profondeur maximale : le plus grand chemin depuis la racine jusqu’aux feuilles

class Noeud:
    def __init__(self, v):
        self.v = v
        self.left = None
        self.right = None

    def __str__(self):
        rows = [str(self.v)]
        if self.left is not None:
            rows.append("+-" + textwrap.indent(str(self.left), "  ")[2:])
        if self.right is not None:
            rows.append("+-" + textwrap.indent(str(self.right), "  ")[2:])
        return "\n".join(rows)

    def profondeur_maximale(self):
        pleft = 0 if self.left is None else self.left.profondeur_maximale() + 1
        pright = 0 if self.right is None else self.right.profondeur_maximale() + 1
        return max(pleft, pright)


na = graph()
print(na.profondeur_maximale())

2

Profondeur moyenne ?

L’astuce est souvent la même : il faut calculer la moyenne au dernier moment et jusqu’à ce moment-là, on conserve la somme et le compte. On divise les deux à la fin. Il reste une ambiguïté, est-ce qu’un noeud ayant une feuille à gauche ou droite mais une seul feuille est-il considéré comme une feuille également ? Une demi-feuille ? C’est une convention à choisir en fonction de l’usage qui est fait de cette moyenne. Certaines expressions n’existent pas en mathématique comme , est-ce que cela vaut 0, 1, ou ? Ce choix vous est laissé. Dans le cas, présent, l’implémentation de la fonction fait qu’un noeud n’ayant qu’un fils est une demi-feuille.

import textwrap


def graph():
    na = Noeud("A")
    na.left = Noeud("B")
    na.left.left = Noeud("C")
    na.left.right = Noeud("D")
    na.right = Noeud("E")
    return na


class Noeud:
    def __init__(self, v):
        self.v = v
        self.left = None
        self.right = None

    def __str__(self):
        rows = [str(self.v)]
        if self.left is not None:
            rows.append("+-" + textwrap.indent(str(self.left), "  ")[2:])
        if self.right is not None:
            rows.append("+-" + textwrap.indent(str(self.right), "  ")[2:])
        return "\n".join(rows)

    def profondeur_maximale(self):
        pleft = 0 if self.left is None else self.left.profondeur_maximale() + 1
        pright = 0 if self.right is None else self.right.profondeur_maximale() + 1
        return max(pleft, pright)

    def profondeur_somme_count(self):
        somme = 0
        count = 0
        if self.left is None:
            count += 0.5
        else:
            sleft, cleft = self.left.profondeur_somme_count()
            somme += sleft + cleft
            count += cleft
        if self.right is None:
            count += 0.5
        else:
            sright, cright = self.right.profondeur_somme_count()
            somme += sright + cright
            count += cright
        return somme, count


na = graph()
somme, count = na.profondeur_somme_count()
print(somme, count, somme / count)

5.0 3.0 1.6666666666666667

Intermède : is ou == ?

class bizarre:
    def __eq__(self, a):
        return False


b = bizarre()
print(b is b, b == b)

True False

---

Notebook on github