6.7. Arbres binaires de recheche#
6.7.1. Définition#
Definition 6.1 (arbre binaire de recherche)
Un arbre binaire de recherche est un arbre binaire dans lequel, on a la
propriété suivante pour tout nœud e :
tous les nœuds du sous arbre gauche ont une valeur inférieure à la valeur de
etous les nœuds du sous arbre droite ont une valeur supérieure ou égale à la valeur de
e
sont des arbres binaires de recherche. En revanche
n’en est pas un.
Exercise 6.1
Donner tous les arbres binaires de recherche à 3 éléments
6.7.2. Recherche dans un ABR#
Écrire une fonction appartient qui permet de chercher dans un ABR
def appartient(x,abr):
pass
Le code suivant
appartient(8,abr)
renvoie , alors que le code
appartient(7,abr)
renvoie .