Parcours d’arbres binaires

Avec une fonction (l’argument peut être None = « arbre vide ») :

def hauteur(noeud):
    if noeud is None: # le noeud n'existe pas ...
        return -1     # on retire le 1 déja compté !
    else:
        return 1 + max(hauteur(noeud.g), hauteur(noeud.d))

ou bien, si on n’accepte pas l’argument None :

def hauteur(noeud):
    g = d = 0
    if noeud.g is not None:
        g = hauteur(noeud.g)
    if noeud.d is not None:
        d = hauteur(noeud.d)
    return 1+ max(g, d)

Avec une méthode de Noeud (l’argument self ne peut pas être None !) :

def hauteur(self):
    """ Renvoie la hauteur de la branche de racine self
        (méthode récursive)
    """
    if self.est_feuille():
        return 0
    elif self.g is None:
        return self.d.hauteur()
    elif self.d is None:
        return self.g.hauteur()
    else:
        return 1 + max(self.g.hauteur(), self.d.hauteur())

class Arbre:
    def __init__(self, racine = None):
        self.racine = racine # type : Noeud

    def __repr__(self):
        """ Affiche les valeurs des noeuds sous forme arborescente
        """
        lines = _build_tree_string(self.racine, 0, False, '-')[0]
        return '\n' + '\n'.join((line.rstrip() for line in lines))

# Source : https://github.com/joowani/binarytree/blob/22fc4b72c3be23d08016a2c863e6268f8ad49068/binarytree/__init__.py#L160
def _build_tree_string(root, curr_index, index=False, delimiter='-'):
    """Recursively walk down the binary tree and build a pretty-print string.
    In each recursive call, a "box" of characters visually representing the
    current (sub)tree is constructed line by line. Each line is padded with
    whitespaces to ensure all lines in the box have the same length. Then the
    box, its width, and start-end positions of its root node value repr string
    (required for drawing branches) are sent up to the parent call. The parent
    call then combines its left and right sub-boxes to build a larger box etc.
    :param root: Root node of the binary tree.
    :type root: binarytree.Node
    :param curr_index: Level-order_ index of the current node (root node is 0).
    :type curr_index: int
    :param index: If set to True, include the level-order_ node indexes using
        the following format: ``{index}{delimiter}{value}`` (default: False).
    :type index: bool
    :param delimiter: Delimiter character between the node index and the node
        value (default: '-').
    :type delimiter:
    :return: Box of characters visually representing the current subtree, width
        of the box, and start-end positions of the repr string of the new root
        node value.
    :rtype: ([str], int, int, int)
    .. _Level-order:
        https://en.wikipedia.org/wiki/Tree_traversal#Breadth-first_search
    """
    if root is None:
        return [], 0, 0, 0

    line1 = []
    line2 = []
    if index:
        node_repr = '{}{}{}'.format(curr_index, delimiter, root.v)
    else:
        node_repr = str(root.v)

    new_root_width = gap_size = len(node_repr)

    # Get the left and right sub-boxes, their widths, and root repr positions
    l_box, l_box_width, l_root_start, l_root_end = \
        _build_tree_string(root.g, 2 * curr_index + 1, index, delimiter)
    r_box, r_box_width, r_root_start, r_root_end = \
        _build_tree_string(root.d, 2 * curr_index + 2, index, delimiter)

    # Draw the branch connecting the current root node to the left sub-box
    # Pad the line with whitespaces where necessary
    if l_box_width > 0:
        l_root = (l_root_start + l_root_end) // 2 + 1
        line1.append(' ' * (l_root + 1))
        line1.append('_' * (l_box_width - l_root))
        line2.append(' ' * l_root + '/')
        line2.append(' ' * (l_box_width - l_root))
        new_root_start = l_box_width + 1
        gap_size += 1
    else:
        new_root_start = 0

    # Draw the representation of the current root node
    line1.append(node_repr)
    line2.append(' ' * new_root_width)

    # Draw the branch connecting the current root node to the right sub-box
    # Pad the line with whitespaces where necessary
    if r_box_width > 0:
        r_root = (r_root_start + r_root_end) // 2
        line1.append('_' * r_root)
        line1.append(' ' * (r_box_width - r_root + 1))
        line2.append(' ' * r_root + '\\')
        line2.append(' ' * (r_box_width - r_root))
        gap_size += 1
    new_root_end = new_root_start + new_root_width - 1

    # Combine the left and right sub-boxes with the branches drawn above
    gap = ' ' * gap_size
    new_box = [''.join(line1), ''.join(line2)]
    for i in range(max(len(l_box), len(r_box))):
        l_line = l_box[i] if i < len(l_box) else ' ' * l_box_width
        r_line = r_box[i] if i < len(r_box) else ' ' * r_box_width
        new_box.append(l_line + gap + r_line)

    # Return the new box, its width and its root repr positions
    return new_box, len(new_box[0]), new_root_start, new_root_end