Bonjour,

j'ai codé le code qui suit pour faire une recherche dans un arbre bianire qui n'est pas triée, mais j'ai été obligé d'utiliser une variable globale extérieure à la fonction pour enregistrer les résultats des chemins qui mènent à la valeur de feuille recherchée (il peut y avoir plusieurs fois la valeur recherchée). Voyez-vous un moyen de faire pour avoir ce résultat retournée par la fonction (et None s'il n'y en pas).

Voici ce que j'ai fait :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# -*- coding: utf-8 -*-
 
arbre = ['+', ['+', ['*', 4, ['*', 4, 2]], 2], ['*', ['*', 4, 2], 2]]# 
 
def arbre_gauche(arbre) :
    return arbre[1]
 
def arbre_droit(arbre) :
    return arbre[2]
 
def est_vide(arbre) :
    if arbre == [] : #???
        return True
    else :
        return False
 
#print arbre_gauche(arbre)
 
 
Res = []
 
#retourne le chemin pour mener à la feuille si elle a été trouvée,False sinon
def recherche(feuille, arbre, chemin = []) :
    global Res
    if est_vide(arbre) :
        return 
    if isinstance(arbre_gauche(arbre), list) :
        recherche(feuille, arbre_gauche(arbre), chemin + [1])
    if isinstance(arbre_droit(arbre), list) :
        recherche(feuille, arbre_droit(arbre), chemin + [2])  
    if arbre_gauche(arbre) == feuille :
        chemin += [1]
        Res += [chemin]
        return 
    if arbre_droit(arbre) == feuille :
        chemin += [2]
        Res += [chemin]
        return
 
 
recherche(12, arbre)
print Res
Merci d'avance pour vos réponses!