Qu’est-ce qu’une feuille dans un arbre binaire ?

Réponse courte

Une feuille est un nœud sans enfant. Dans un arbre binaire représenté avec des liens gauche et droit, ses deux sous-arbres sont vides ; elle peut se trouver à n’importe quelle profondeur.

Comprendre

Définition dans l’arbre

Chaque nœud d’un arbre possède zéro, un ou plusieurs enfants selon la structure considérée. Dans un arbre binaire, il peut avoir au plus deux places d’enfant, gauche et droite. Une feuille est précisément un nœud qui n’a aucun enfant : aucune branche ne part de lui vers un nœud plus bas. Un nœud avec un seul enfant n’est donc pas une feuille, même si son autre place est vide.

Repérer les feuilles

Dans l’arbre A dont les enfants sont B et C, si B a les enfants D et E et que C n’a pas d’enfant, les feuilles sont D, E et C. A et B sont des nœuds internes, car ils possèdent au moins un enfant. La racine peut elle-même être une feuille : c’est le cas de l’arbre formé d’un unique nœud.

Ne pas se fier au dessin seul

La feuille se reconnaît à la structure des liens, pas à sa position visuelle ni au fait qu’elle soit « en bas » de la page. Un sous-arbre absent n’est pas un nœud feuille supplémentaire : il n’y a alors aucun nœud à compter. En représentation Python, une feuille a généralement None pour ses liens gauche et droit, tandis qu’un nœud ayant seulement un enfant conserve une référence non vide d’un côté.

Exemples

  • Dans A avec enfants B et C, où B a D comme enfant gauche : C et D sont feuilles ; A et B ne le sont pas.
  • Un arbre réduit au nœud R a une feuille, R, même si R est aussi sa racine.

Pièges fréquents

  • Appeler feuille tout nœud placé au dernier niveau du schéma : seul compte le fait qu’il n’ait aucun enfant.
  • Compter un emplacement vide comme une feuille : une place gauche None n’est pas un nœud de l’arbre.

Et maintenant ?

Questions proches

← Toutes les questions-réponses