Salut, arbre binaire localement complet, ça veut bien dire que les noeuds sont tous de degré 3 ou 1 ?

Par récurrence ça me semble bien. Tu pars d'un ABLC non trivial et tu remplaces
un noeud "support" c'est à dire un noeud dont les deux fils sont des feuilles et tu supprimes ses fils.

x             x
x x  --->    

Regarde l'évolution du nb de noeuds internes / feuilles et applique l'hypothèse de récurrence.

Merci !
Pour moi, un ABLC c'est un arbre dont chaque nœuds a soit deux fils, soit 0, donc je pense qu'on a la même définition.

Mon soucis avec la récurrence, c'est que je ne sais pas sur quel paramètre la faire !

            x          
       x           x

   x      x

        x   x

est un ABLC si je ne m'abuse (petit effort pour se le représenter proprement), et je ne vois pas comment faire une récurrence là dessus...

Merci !

Récurrence sur le nombre de noeuds internes par exemple.

Considère un ABLC avec n noeuds internes, n >=1  et montre qu'il y a un noeud interne ayant deux fils qui sont des feuilles.
Supprime ces deux feuilles : ça donne un nouvel arbre, plus petit, avec n-1 noeuds interne. Montre qu'il s'agit d'un ABLC. Donc tu peux lui appliquer l'hypothèse de récurrence : il a n-1 noeuds internes et n feuilles. En déduire le résultat pour l'arbre de départ.
Allez, assez d'explications, au boulot !

Merci beaucoup !

Bonne journée !