#algorithme #code

Les Binary Tree sont une structure de données où chaque node contient deux sous branches (appelés left et right). L’origine du Binary Tree est appelé root

Un Binary Tree peut avoir plusieurs propriétés : - balalanced, si tous les étages du tree sont remplis (sauf le dernier, qui peut être rempli que partiellement) - completed, si il est balanced et que les nodes du dernier étage sont le plus a gauche possible - full (proper ou plane ou strict), si chaque node a 0 ou 2 enfants (pas 1 seul enfant) - perfect, si il est complètement rempli, jusqu’à un certain étage - degenerated, si tous les nodes n’ont qu’un seul enfant. Dans ce cas, le Binary Free se comporte comme une Linked List

Avec h la hauteur du tree (la plus grande distance entre le root et leaf le plus éloigné) - Un perfect Binary Tree possède 2^(h+1) - 1 nodes - Un tree avec seulement le root a une hauteur de 0