Skip to content
Snippets Groups Projects
Select Git revision
  • de4633a696fc354871eecfa58585e2679f1a7715
  • master default protected
2 results

viz.py

Blame
  • 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