Construire un Arbre Binaire à partir de Parcours Préordre et Inordre – Question d’Entretien Python
Introduction
Un arbre binaire est une structure de données essentielle où chaque nœud a au plus deux enfants, appelés le sous-arbre gauche et le sous-arbre droit. Les arbres binaires sont cruciaux en programmation et dans les structures de données, car ils permettent d’organiser et de stocker des informations de manière hiérarchique et efficace.
Cet article se concentre sur le problème de la reconstruction d’un arbre binaire à partir de ses parcours en préordre et en inordre, une question fréquente dans les entretiens techniques. Comprendre ce problème améliore non seulement vos compétences algorithmique mais aussi votre compréhension des arbres binaires en général.
Les termes préordre et inordre font référence aux différentes méthodes de parcours d’un arbre binaire. En parcours préordre, on visite la racine en premier, puis le sous-arbre gauche, et enfin le sous-arbre droit. En parcours inordre, on visite d’abord le sous-arbre gauche, puis la racine, et enfin le sous-arbre droit.
L’objectif de cet article est de vous guider à travers le processus de reconstruction d’un arbre binaire en utilisant ces deux listes de parcours, en fournissant une implémentation complète en Python.
Compréhension des Parcours d’Arbres Binaires
Explication du parcours préordre
Le parcours préordre d’un arbre binaire consiste à :
- Visiter la racine.
- Traverser le sous-arbre gauche.
- Traverser le sous-arbre droit.
Exemple visuel :
Considérons un arbre simple.
A
/ \
B C
/ \
D E
Le parcours préordre de cet arbre serait : A, B, D, E, C
.
Explication du parcours inordre
Le parcours inordre, quant à lui, consiste à :
- Traverser le sous-arbre gauche.
- Visiter la racine.
- Traverser le sous-arbre droit.
Pour le même arbre ci-dessus, le parcours inordre serait : D, B, E, A, C
.
Comparaison entre parcours préordre et inordre
En parcourant un arbre en préordre, nous visitons la racine avant d’explorer ses sous-arbres, ce qui nous permet de déterminer facilement la hiérarchie de l’arbre. En inordre, nous visitons les nœuds de gauche en premier, ce qui peut aider à retrouver l’ordre naturel des éléments, notamment d’un point de vue linéaire.
Importance de Reconstruire un Arbre Binaire
La capacité de reconstruire un arbre binaire à partir de ses parcours est souvent testée lors des entretiens techniques, car il met à l’épreuve la compréhension des structures de données et des arbres binaires. Ce problème a aussi des applications pratiques, comme l’exploitation d’arbres syntaxiques en compilation ou dans les bases de données pour l’optimisation des requêtes.
L’analyse de la complexité de cet algorithme révèle qu’il a une complexité temporelle de O(n)
et une complexité spatiale également de O(n)
, où n
est le nombre de nœuds de l’arbre, car chaque nœud est traité une seule fois.
Approche pour Construire l’Arbre Binaire
Présentation de la méthode générale
Le processus de reconstruction utilise les propriétés uniques des listes préordre et inordre. En préordre, le premier élément est toujours la racine de l’arbre ou sous-arbre. En inordre, nous pouvons diviser la liste autour de la racine pour séparer les sous-arbres gauche et droit.
Algorithme sous-jacent
Pour construire l’arbre :
- Utilisez le premier élément du parcours préordre comme racine.
- Trouvez cet élément dans le parcours inordre pour identifier les sous-arbres.
- Répétez ce processus récursivement pour les sous-arbres gauche et droit.
Étape 1: Comprendre les Listes de Parcours
Le premier élément du parcours préordre (A
dans notre exemple) est la racine. Une fois la racine identifiée, recherchez son index dans la liste inordre pour déterminer quels éléments composent les sous-arbres gauche (avant l’index) et droit (après l’index).
Étape 2: Diviser pour Régner
En utilisant l’index trouvé, divisez les listes de parcours en sous-parties correspondantes et appliquez récursivement les mêmes étapes aux sous-listes.
Implémentation en Python
Voici une implémentation Python pour reconstruire l’arbre binaire :
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
# Le premier élément de parcours préordre est la racine
root_value = preorder[0]
root = Node(root_value)
# Trouver l'index de la racine dans le parcours inordre
root_index_inorder = inorder.index(root_value)
# Construire le sous-arbre gauche et droit en récursif
root.left = buildTree(preorder[1:1 + root_index_inorder], inorder[:root_index_inorder])
root.right = buildTree(preorder[1 + root_index_inorder:], inorder[root_index_inorder + 1:])
return root
Explication de l’Implémentation
- Classe Node : Représente chaque nœud de l’arbre avec une valeur et des pointeurs vers ses enfants gauche et droit.
- Fonction buildTree : Prend en entrée deux listes,
preorder
etinorder
. Elle crée le nœud racine, divise les listes en sous-parties qui correspondent aux sous-arbres gauche et droit, et utilise la récursivité pour construire l’arbre entier.
Tests et Vérification
Il est crucial de tester cette implémentation pour vérifier la construction correcte de l’arbre. Voici quelques cas de tests pertinents :
def printInOrder(node):
if node:
printInOrder(node.left)
print(node.value, end=' ')
printInOrder(node.right)
# Test de l'arbre de l'exemple
preorder = ['A', 'B', 'D', 'E', 'C']
inorder = ['D', 'B', 'E', 'A', 'C']
root = buildTree(preorder, inorder)
print("Inorder du nouvel arbre :")
printInOrder(root) # Devrait imprimer : D B E A C
L’impression de l’arbre reconstruit en parcours inordre devrait correspondre à la liste inorder
d’origine.
Optimisation et Meilleures Pratiques
- Optimisation de la mémoire : Évitez de créer des sous-listes à chaque appel récursif pour économiser de la mémoire.
- Amélioration de l’efficacité : Utilisez un dictionnaire pour stocker les index des valeurs de
inorder
pour accélérer la recherche.
Problèmes Connexes et Pratiques supplémentaires
Pour renforcer votre compréhension, vous pouvez essayer de reconstruire un arbre binaire à partir des parcours inorder
et postorder
, ou explorer des variantes comme les arbres binaires de recherche (BST). Voici quelques ressources pour continuer la pratique :
- LeetCode : « Construct Binary Tree from Inorder and Postorder Traversal ».
- Exercices sur HackerRank sur les arbres binaires.
Conclusion
Nous avons parcouru les étapes clés pour reconstruire un arbre binaire à partir des parcours préordre et inordre, une compétence précieuse pour les entretiens techniques. Une pratique régulière et la compréhension de l’optimisation de code sont essentielles pour maîtriser cette technique. Continuez à explorer et à pratiquer pour améliorer vos compétences algorithmiques et structurelles.