Représentation d’un arbre binaire
Les arbres binaires sont une structure de données fondamentale très utilisée en informatique. Ils sont particulièrement utiles pour concevoir des algorithmes performants pour la recherche, le tri ou encore la traversée de données.
Les arbres binaires sont composés de nœuds, où chaque nœud possède au maximum deux enfants : un enfant gauche et un enfant droit. Chacun de ces enfants peut lui-même avoir son propre enfant gauche et droit, et cette structure se poursuit jusqu’à ce qu’il n’y ait plus de nœuds dans l’arbre.
Le nœud situé tout en haut de l’arbre est appelé la racine, tandis que les nœuds situés tout en bas sont appelés les feuilles.
Cette idée simple permet de représenter un grand nombre de types de données de manière efficace et reste facile à mettre en œuvre dans différents langages de programmation :
class Node: # Objet Node pour stocker les données de chaque nœud
def __init__(self, value): # La valeur que l'on conserve dans chaque nœud (peut être n'importe quoi)
self.left = None # Au départ, left et right sont None
self.right = None
self.value = value # Stocke la valeur dans un objet
# Créer manuellement tous les nœuds
root = Node(1)
root.left, root.right = Node(2), Node(3)
root.left.left, root.left.right = Node(4), Node(5)
root.left.right.left, root.left.right.right = Node(7), Node(8)
root.right.right = Node(6)
# On peut ensuite parcourir l’arbre binaire de manière récursive
# Calculons la somme de tous les nœuds
def treesum(node: Node | None) -> int:
if node is None:
return 0
# Renvoyer la somme du sous-arbre gauche, du sous-arbre droit et du nœud courant
return treesum(node.left) + treesum(node.right) + node.value
print(treesum(root)) # Affiche 36Dans cet exemple, nous parcourons tous les nœuds en partant de la
root. Si le nœud courant est None, cela signifie que nous sommes arrivés à la fin du sous-arbre dans cette direction, et nous pouvons donc retourner 0 comme somme. Sinon, nous calculons la somme du sous-arbre gauche, du sous-arbre droit et du nœud courant, puis nous les additionnons.Défi : Créer un arbre binaire manuellement
Étant donné l’arbre binaire figurant sur l’image, vous devez le créer manuellement.
Écrivez un code qui permettra de créer cet arbre binaire. Vous n’avez pas besoin d’afficher quoi que ce soit ; cette partie est déjà gérée automatiquement.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB