Les trois parcours, et ce que chacun révèle

Les trois parcours, mesurés :

Ce que chaque ligne dit. Le préfixe commence par la racine : c'est le seul des trois dont on lit la racine d'un coup d'œil. Le postfixe la termine. L'infixe la place au milieu — à la cinquième position ici, ce qui signifie que le sous-arbre gauche compte quatre nœuds.

Aucun des trois ne donne la hauteur, et c'est le point de la question. Un parcours produit une liste : il aplatit la structure. Les trois parcours de $\text{Nœud}(\text{Vide},1,\text{Nœud}(\text{Vide},2,\text{Vide}))$, de hauteur $1$, et ceux d'un arbre de hauteur $5$ à deux nœuds bien choisis, peuvent coïncider. La hauteur se calcule, elle ne se lit pas dans une liste — il faut une fonction récursive qui remonte l'information, ce que hauteur fait avec son max.

Le postfixe est l'ordre de libération. En C, detruire doit libérer les fils avant le père :

/* Libere tout l'arbre. Parcours POSTFIXE : les fils AVANT le pere. */
void detruire(noeud* a) {
    if (a == NULL) { return; }
    detruire(a->gauche);
    detruire(a->droit);
    free(a);                    /* le pere en DERNIER */
}

Libérer le père d'abord serait la faute : après free(a), lire a->gauche est une utilisation après libération, et les deux sous-arbres deviennent inaccessibles — une fuite de mémoire doublée d'un pointeur fou. L'ordre postfixe n'est donc pas ici un choix esthétique : c'est le seul correct, et il découle du fait qu'un fils doit être atteint avant que son père ne disparaisse.

Symétriquement, une copie d'arbre se fait naturellement en préfixe : on crée le nœud, puis on lui accroche des fils déjà construits. Chaque parcours a son emploi, et il est dicté par la dépendance des données, jamais par le goût.

Vérification : la version C, compilée avec -Wall -Wextra, affiche taille = 7, hauteur = 3, feuilles = 3 et infixe = 1 3 4 6 8 7 9, et le contrôleur de fuites rapporte 0 leaks for 0 total leaked bytes.