madamasterclass.com
-
Connexion
Connexion
Exploration des arbres binaires
Un arbre binaire est une structure de données hiérarchique composée de nœuds. Chaque nœud peut avoir jusqu'à deux nœuds enfants, généralement appelés le nœud gauche et le nœud droit. Les arbres binaires sont couramment utilisés pour représenter des structures de données telles que les arbres de recherche binaires, les arbres de syntaxe abstraite, etc.
|
|
Les principaux termes associés aux arbres binaires sont :
|
En Python, un arbre binaire peut être représenté à l'aide de classes. Voici une implémentation de base :
class Noeud:
def __init__(self, valeur):
self.valeur = valeur
self.gauche = None
self.droite = None
def arbre_en_liste(noeud):
if noeud is None:
return []
# Construction de la représentation sous forme de liste
liste = [noeud.valeur]
# Appel récursif pour le sous-arbre gauche et droit
liste.append(arbre_en_liste(noeud.gauche))
liste.append(arbre_en_liste(noeud.droite))
return liste
# Exemple d'utilisation
racine = Noeud(1)
racine.gauche = Noeud(4)
racine.droite = Noeud(5)
racine.droite.gauche = Noeud(1)
# Affichage de l'arbre sous forme de liste de listes
resultat = arbre_en_liste(racine)
print(resultat)
Il existe trois principaux types de parcours d'arbres binaires :
Voici comment implémenter ces parcours en Python :
def parcours_prefixe(noeud):
if noeud is not None:
# Affiche la valeur du nœud avant les sous-arbres
print(noeud.valeur)
parcours_prefixe(noeud.gauche)
parcours_prefixe(noeud.droit)
def parcours_infixe(noeud):
if noeud is not None:
parcours_infixe(noeud.gauche)
# Affiche la valeur du nœud entre les sous-arbres gauches et droits
print(noeud.valeur)
parcours_infixe(noeud.droit)
def parcours_postfixe(noeud):
if noeud is not None:
parcours_postfixe(noeud.gauche)
parcours_postfixe(noeud.droit)
# Affiche la valeur du nœud après les sous-arbres
print(noeud.valeur)
Supposons que nous voulions créer un arbre binaire représentant une expression mathématique simple, telle que (3 + 4) * 2. Voici comment créer cet arbre :
Éducation
# Création des nœuds
noeud_mul = Noeud('*')
noeud_plus = Noeud('+')
noeud_3 = Noeud(3)
noeud_4 = Noeud(4)
noeud_2 = Noeud(2)
# Construction de l'arbre
noeud_plus.gauche = noeud_3
noeud_plus.droit = noeud_4
noeud_mul.gauche = noeud_plus
noeud_mul.droit = noeud_2
Maintenant, nous pouvons parcourir l'arbre en utilisant l'un des parcours mentionnés précédemment :
print("Parcours préfixe :")
parcours_prefixe(noeud_mul)
print("Parcours infixe :")
parcours_infixe(noeud_mul)
print("Parcours postfixe :")
parcours_postfixe(noeud_mul) Cela affichera le résultat suivant :
Parcours préfixe :
*
+
3
4
2
Parcours infixe :
3
+
4
*
2
Parcours postfixe :
3
4
+
2
* La conversion en dictionnaire de l'arbre consiste à représenter chaque nœud de l'arbre en tant qu'entrée de dictionnaire, où la clé est le nom de l'attribut du nœud (par exemple, "valeur", "gauche", "droit") et la valeur est la valeur de cet attribut pour le nœud donné. Pour réaliser cette conversion, une fonction récursive convert_to_dict est utilisée. Cette fonction prend un nœud en entrée et renvoie son équivalent en dictionnaire. À chaque appel récursif, elle crée un dictionnaire pour le nœud actuel, où "valeur" est la valeur du nœud, et les clés "gauche" et "droit" sont respectivement les conversions récursives des sous-arbres gauche et droit.
class Noeud: def __init__(self, valeur): self.valeur = valeur self.gauche = None self.droit = None def convert_to_dict(noeud):
if noeud is None:
return None
# Construire le dictionnaire pour le nœud actuel
noeud_dict = {
"valeur": noeud.valeur,
"gauche": convert_to_dict(noeud.gauche),
"droit": convert_to_dict(noeud.droit)
}
return noeud_dict # Création des nœuds noeud_mul = Noeud('*') noeud_plus = Noeud('+') noeud_3 = Noeud(3) noeud_4 = Noeud(4) noeud_2 = Noeud(2) # Construction de l'arbre noeud_plus.gauche = noeud_3 noeud_plus.droit = noeud_4 noeud_mul.gauche = noeud_plus noeud_mul.droit = noeud_2 # Convertir en dictionnaire arbre_dict = convert_to_dict(noeud_mul) print("Arbre sous forme de dictionnaire :") print(arbre_dict)
Cela affichera le résultat suivant :
Arbre sous forme de dictionnaire :
{'valeur': '*', 'gauche': {'valeur': '+', 'gauche': {'valeur': 3, 'gauche': None, 'droit': None},
'droit': {'valeur': 4, 'gauche': None, 'droit': None}}, 'droit': {'valeur': 2, 'gauche': None, 'droit': None}} Les arbres binaires sont une structure de données essentielle en informatique. Comprendre leur fonctionnement et savoir les parcourir est important pour de nombreux problèmes et algorithmes.
Écrivez une fonction Python qui compte le nombre total de nœuds dans un arbre binaire.
Solution
La fonction compter_noeuds utilise une approche récursive pour parcourir l'arbre et compter le nombre total de nœuds. Lorsque l'arbre est vide (None), la fonction renvoie 0. Sinon, elle renvoie 1 plus la somme du nombre de nœuds dans le sous-arbre gauche et le sous-arbre droit.
class Noeud:
def __init__(self, valeur):
self.valeur = valeur
self.gauche = None
self.droite = None
def compter_noeuds(arbre):
if arbre is None:
return 0
return 1 + compter_noeuds(arbre.gauche) + compter_noeuds(arbre.droite)
# Exemple d'utilisation
arbre = Noeud(1)
arbre.gauche = Noeud(2)
arbre.droite = Noeud(3)
arbre.gauche.gauche = Noeud(4)
arbre.gauche.droite = Noeud(5)
print(compter_noeuds(arbre)) # Résultat attendu: 5
Écrivez une fonction Python qui vérifie si un arbre binaire est un arbre binaire de recherche (ABR) valide.
Solution:
La fonction est_abr_valide utilise une approche récursive pour vérifier si un arbre binaire est un arbre binaire de recherche (ABR) valide. Elle prend en compte les valeurs minimales et maximales autorisées pour chaque nœud de l'arbre. Si la valeur d'un nœud est inférieure ou égale à la valeur minimale autorisée ou supérieure ou égale à la valeur maximale autorisée, l'ABR n'est pas valide. La fonction renvoie True si toutes les sous-arbres sont des ABR valides et False sinon.
class Noeud:
def __init__(self, valeur):
self.valeur = valeur
self.gauche = None
self.droite = None
def est_abr_valide(arbre, min_val=float('-inf'), max_val=float('inf')):
if arbre is None:
return True
if arbre.valeur <= min_val or arbre.valeur >= max_val:
return False
return (est_abr_valide(arbre.gauche, min_val, arbre.valeur) and
est_abr_valide(arbre.droite, arbre.valeur, max_val))
# Exemple d'utilisation
arbre = Noeud(4)
arbre.gauche = Noeud(2)
arbre.droite = Noeud(6)
arbre.gauche.gauche = Noeud(1)
arbre.gauche.droite = Noeud(3)
arbre.droite.gauche = Noeud(5)
arbre.droite.droite = Noeud(7)
print(est_abr_valide(arbre)) # Résultat attendu: True Écrivez une fonction Python qui calcule la hauteur d'un arbre binaire.
Solution:
La fonction hauteur_arbre utilise une approche récursive pour calculer la hauteur d'un arbre binaire. La hauteur d'un arbre vide est définie comme 0, et la hauteur d'un arbre non vide est calculée comme la plus grande hauteur entre le sous-arbre gauche et le sous-arbre droit, plus 1.
class Noeud:
def __init__(self, valeur):
self.valeur = valeur
self.gauche = None
self.droite = None
def hauteur_arbre(arbre):
if arbre is None:
return 0
hauteur_gauche = hauteur_arbre(arbre.gauche)
hauteur_droite = hauteur_arbre(arbre.droite)
return max(hauteur_gauche, hauteur_droite) + 1
# Exemple d'utilisation
arbre = Noeud(1)
arbre.gauche = Noeud(2)
arbre.droite = Noeud(3)
arbre.gauche.gauche = Noeud(4)
arbre.gauche.droite = Noeud(5)
arbre.droite.droite = Noeud(6)
print(hauteur_arbre(arbre)) # Résultat attendu: 3 Écrivez une fonction Python qui effectue un parcours en profondeur préfixe d'un arbre binaire et renvoie une liste contenant les valeurs des nœuds visités.
Solution:
class Noeud:
def __init__(self, valeur):
self.valeur = valeur
self.gauche = None
self.droite = None
def parcours_prefixe(arbre):
if arbre is None:
return []
return [arbre.valeur] + parcours_prefixe(arbre.gauche) + parcours_prefixe(arbre.droite)
# Exemple d'utilisation
arbre = Noeud(1)
arbre.gauche = Noeud(2)
arbre.droite = Noeud(3)
arbre.gauche.gauche = Noeud(4)
arbre.gauche.droite = Noeud(5)
print(parcours_prefixe(arbre)) # Résultat attendu: [1, 2, 4, 5, 3] ⓘ La fonction parcours_prefixe utilise une approche récursive pour effectuer un parcours en profondeur préfixe d'un arbre binaire. L'algorithme visite d'abord la racine, puis effectue le parcours en profondeur préfixe du sous-arbre gauche, suivi du parcours en profondeur préfixe du sous-arbre droit. Les valeurs des nœuds visités sont ajoutées à une liste qui est renvoyée à la fin.
Considérez l'arbre binaire suivant :
5
/ \
3 7
/ \ / \
1 4 6 9
a) Parcourez cet arbre en utilisant le parcours préfixe (préordre).
Solution : 5, 3, 1, 4, 7, 6, 9
b) Parcourez cet arbre en utilisant le parcours infixe (inordre).
Solution : 1, 3, 4, 5, 6, 7, 9
c) Parcourez cet arbre en utilisant le parcours postfixe (postordre).
Solution : 1, 4, 3, 6, 9, 7, 5
Considérez l'arbre binaire suivant :
A
/ \
B C
/ \ / \
D E F G
a) Quel est le niveau de l'arbre où se trouve le nœud D ?
Solution : Le niveau du nœud D est 2.
b) Quels sont les nœuds frères dans cet arbre ?
Solution : Les nœuds frères sont B et C.
c) Quel est le nœud parent du nœud E ?
Solution : Le nœud parent du nœud E est B.
Créez une classe Node pour représenter un nœud dans un arbre binaire. Chaque nœud doit avoir une valeur et des références vers ses nœuds enfants gauche et droit.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = NoneImplémentez une fonction insert qui prend en paramètre un nœud root et une valeur, et insère cette valeur dans l'arbre binaire de recherche correspondant. Assurez-vous que les valeurs plus petites sont insérées à gauche et les valeurs plus grandes à droite.
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return rootImplémentez une fonction récursive preorder_traversal qui prend en paramètre un nœud root et effectue un parcours préfixe (préordre) de l'arbre en imprimant les valeurs des nœuds.
def preorder_traversal(root):
if root is not None:
print(root.value, end=" ")
preorder_traversal(root.left)
preorder_traversal(root.right)Implémentez une fonction récursive search qui prend en paramètre un nœud root et une valeur, et recherche cette valeur dans l'arbre binaire. La fonction doit renvoyer True si la valeur est présente et False sinon.
def search(root, value):
if root is None or root.value == value:
return root is not None
if value < root.value:
return search(root.left, value)
else:
return search(root.right, value)Implémentez une fonction récursive height qui prend en paramètre un nœud root et renvoie la hauteur de l'arbre binaire (le nombre maximum de niveaux).
def height(root):
if root is None:
return 0
left_height = height(root.left)
right_height = height(root.right)
return max(left_height, right_height) + 1Considérez l'arbre binaire de recherche suivant :
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13a) Parcourez cet arbre en utilisant le parcours préfixe (préordre).
Solution : 8, 3, 1, 6, 4, 7, 10, 14, 13
b) Parcourez cet arbre en utilisant le parcours infixe (inordre).
Solution : 1, 3, 4, 6, 7, 8, 10, 13, 14
c) Parcourez cet arbre en utilisant le parcours postfixe (postordre).
Solution : 1, 4, 7, 6, 3, 13, 14, 10, 8
Considérez l'arbre binaire de recherche suivant :
5
/ \
3 7
/ \ / \
2 4 6 8a) Insérez le nœud avec la valeur 9 dans cet arbre.
Solution : L'arbre après l'insertion du nœud 9 est :
5
/ \
3 7
/ \ / \
2 4 6 8
\
9b) Supprimez le nœud avec la valeur 3 de cet arbre.
Solution : L'arbre après la suppression du nœud 3 est :
5
/ \
4 7
/ / \
2 6 8
\
9Créez une classe Node pour représenter un nœud dans un arbre binaire de recherche. Chaque nœud doit avoir une valeur et des références vers ses nœuds enfants gauche et droit.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = NoneImplémentez une fonction récursive minimum qui prend en paramètre un nœud root et renvoie la valeur minimale dans l'arbre binaire de recherche.
def maximum(root):
if root.right is None:
return root.value
return maximum(root.right)Implémentez une fonction récursive maximum qui prend en paramètre un nœud root et renvoie la valeur maximale dans l'arbre binaire de recherche.
def minimum(root):
if root.left is None:
return root.value
return minimum(root.left)Implémentez une classe Node pour représenter un nœud dans un arbre binaire. Chaque nœud peut contenir soit un opérateur (+, -, *, /), soit un nombre.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = NoneImplémentez une fonction récursive build_expression_tree qui prend en paramètre une expression arithmétique sous forme de liste et renvoie un arbre binaire représentant cette expression. Par exemple, pour l'expression (3+4)*2, la liste d'entrée serait ['(', '3', '+', '4', ')', '*', '2'].
def build_expression_tree(expression):
stack = []
operators = set(['+', '-', '*', '/'])
for token in expression:
if token == '(':
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
right = stack.pop()
operator = stack.pop()
left = stack.pop()
node = Node(operator)
node.left = left
node.right = right
stack.append(node)
stack.pop() # Supprimer la parenthèse ouvrante
elif token in operators:
stack.append(token)
else:
stack.append(Node(float(token)))
return stack[0]Implémentez une fonction récursive evaluate_expression_tree qui prend en paramètre un nœud racine d'un arbre binaire et évalue l'expression arithmétique représentée par cet arbre. Assurez-vous de gérer correctement les opérations arithmétiques.
def evaluate_expression_tree(root):
if root.value == '+':
return evaluate_expression_tree(root.left) + evaluate_expression_tree(root.right)
elif root.value == '-':
return evaluate_expression_tree(root.left) - evaluate_expression_tree(root.right)
elif root.value == '*':
return evaluate_expression_tree(root.left) * evaluate_expression_tree(root.right)
elif root.value == '/':
return evaluate_expression_tree(root.left) / evaluate_expression_tree(root.right)
else:
return root.valueUtilisez les fonctions build_expression_tree et evaluate_expression_tree pour évaluer l'expression arithmétique (3+4)*2.
expression = ['(', '3', '+', '4', ')', '*', '2']
tree = build_expression_tree(expression)
result = evaluate_expression_tree(tree)
print(result) # Affiche 14.0Les mathématiques ont souvent la réputation d'être une discipline austère et difficile, mais ...
Read more.Plongez dans l'univers fascinant des suites numériques, où chaque terme révèle des patterns surprenants et des applications pratiques dans les mathématiques et au-delà.
Read more.Découvrez comment les fonctions tissent des liens entre les nombres et les concepts, transformant des idées abstraites en outils puissants pour résoudre des problèmes du quotidien.
Read more.
