Qu'est-ce qu'un arbre binaire?

Un arbre binaire est une structure de données en forme d’arbre dans laquelle chaque nœud a au plus deux descendants : gauche et droit.

Propriétés principales :

• Racine (Root) : Le nœud supérieur de l’arbre.
• Nœud (Node) : Élément de l’arbre contenant des données et des liens vers ses descendants.
• Enfant (Child) : Nœud situé directement sous un autre nœud (parent).
• Parent (Parent) : Nœud ayant un ou plusieurs descendants directement en dessous.
• Feuille (Leaf) : Nœud sans descendants.
• Rameau (Branch) : Chemin de la racine à une feuille.
• Sous-arbre (Subtree) : Arbre composé d’un nœud et de tous ses descendants.

Différents types d’arbres binaires :

• Arbre binaire complet (Full Binary Tree) : Chaque nœud a 0 ou 2 descendants.
• Arbre binaire parfait (Perfect Binary Tree) : Tous les niveaux, sauf le dernier, sont complètement remplis, et au dernier niveau, tous les nœuds sont aussi à gauche que possible.
• Arbre binaire équilibré (Balanced Binary Tree) : La hauteur des sous-arbres gauche et droit de tout nœud diffère de pas plus de 1. Exemple : arbre AVL, arbre rouge-noir.
• Arbre binaire dégénéré (Degenerate Binary Tree) : Chaque nœud a au plus un descendant. Essentiellement, c’est une liste chaînée.

Utilisé dans divers algorithmes et structures de données, tels que les arbres de recherche binaires, les tas, les arbres syntaxiques.