Scribd
Importer
73 vues1 page

TP Arbres

Ce TP porte sur l'implémentation d'arbres binaires en Python, en utilisant des listes pour représenter les arbres. Il comprend des exercices sur le calcul de la hauteur, du nombre de nœuds et de feuilles d'un arbre, ainsi que sur la construction et la manipulation d'arbres binaires de recherche (ABR). Les questions incluent l'insertion d'éléments, la construction d'un ABR à partir d'une liste, et le tri d'une liste d'entiers en utilisant des ABR.

Transféré par

rimlahrech05
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
73 vues1 page

TP Arbres

Ce TP porte sur l'implémentation d'arbres binaires en Python, en utilisant des listes pour représenter les arbres. Il comprend des exercices sur le calcul de la hauteur, du nombre de nœuds et de feuilles d'un arbre, ainsi que sur la construction et la manipulation d'arbres binaires de recherche (ABR). Les questions incluent l'insertion d'éléments, la construction d'un ABR à partir d'une liste, et le tri d'une liste d'entiers en utilisant des ABR.

Transféré par

rimlahrech05
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

TP : Les Arbres

Exercice 1 :
Dans ce TP, nous allons implémenter des arbres binaires en Python. On choisit de représenter l’arbre vide
par la liste vide, et un arbre de racine étiquetée par « e » et fils « fg » et « fd » par la liste [e, fg, fd] Dans
ces exercices, nous allons travailler sur cet arbre :

A = [40, [14, [5, [], []], [4, [], [8, [], []]]] , [6, [], []]]

Question 1
Ecrire une fonction calculant la hauteur d’un arbre.

Question 2
Ecrire une fonction calculant le nombre de nœuds d’un arbre binaire.

Question 3
Ecrire une fonction calculant le nombre de feuilles d’un arbre binaire.

Exercice 2 :
Un arbre binaire de recherche est un arbre défini comme suit :
• Les étiquettes des nœuds sont appelées des clés.
• Les clés de tous les nœuds d’un sous-arbre gauche d’un nœud X sont inférieures ou égales à la clé de X.
• Les clés de tous les nœuds d’un sous-arbre droit d’un nœud X sont strictement supérieures
à la clé de X.

Question 1
Ecrire une fonction inserer(A, x) qui fait insérer un élément x dans un ABR A.

Question 2
Ecrire une fonction construireABR(L) qui prend une liste L et retourne un ABR avec les éléments de la liste
L.

Question 3
Construire un arbre A en utilisant les éléments de la Liste suivante : L= [59, 18, 44, 8, 57, 36, 52, 61].

Question 4
Ecrire deux fonctions minABR(A) et maxABR(A) qui prend en paramètre un ABR A et retourne l’élément
minimal et l’élément maximal respectivement.

Question 5
Ecrire une fonction infixe(A, P) qui prend en paramètre un arbre A et une liste vide P et remplit cette liste
avec le parcours infixe de l’arbre A.

Question 6
Ecrire une fonction triABR(L) qui prend en paramètre une liste L d’entier et qui retourne une liste triée
des éléments de L, en utilisant les ABR et le parcours infixe.

Vous aimerez peut-être aussi