Select Git revision
listes-fusion.py
Forked from
Vuillemot Romain / INF-TC1
Source project has a limited visibility.
-
Romain Vuillemot authoredRomain Vuillemot authored
arbre-tuple.py 1.15 KiB
import sys
class Noeud:
def __init__(self, v, c = []):
self.v = v
self.c = c
def parcours_affiche(arbre):
for c in arbre.c:
parcours_affiche(c)
print(arbre.v)
def parcours_recherche(arbre, valeur):
if arbre is None:
return False
stack = arbre.c
if valeur > arbre.v:
return False
if valeur == arbre.v:
return True
prev = sys.maxsize
while len(stack) > 0:
children = stack.pop(0)
if valeur == children.v:
return True
if valeur > prev and valeur < children.v:
stack = children.c
prev = stack[0].v
else:
prev = children.v
return False
if __name__=="__main__":
racine = Noeud(13, [Noeud(4, [Noeud(1), Noeud(2), Noeud(3)]), Noeud(8, \
[Noeud(5), Noeud(6), Noeud(7)]), Noeud(12, [Noeud(9), Noeud(10), Noeud(11)])])
print(parcours_affiche(racine))
# renvoie False pour un arbre vide
parcours_recherche(None, -1)
# 11 est dans l'arbre
assert parcours_recherche(racine, 11) == True
# 12 n'est pas dans l'arbre
assert parcours_recherche(racine, 12) == False