Le tri arborescent python d’arbre (Binary Search Tree) est un algorithme de tri comparatif qui utilise une structure d’arborescence de recherche binaire. Il équivaut au tri rapide, sa complexité moyenne est de Θ (n log n) en moyenne, mais Θ (n2) dans le pire des cas.
Cependant, il est moins efficace car il doit créer une structure de données complexe et le tri rapide est un tri sur place. Par conséquent, il n’est pas utilisé dans la pratique.
Référence : Website fr.wikipedia.org
Tri arborescent code python
class NoeudArbreBinaire:
def __init__(self, cle):
self.cle = cle
self.left = None
self.right = None
self.parent = None
def inserer(self, noeud):
if self.cle > noeud.cle:
if self.left is None:
self.left = noeud
noeud.parent = self
else:
self.left.inserer(noeud)
elif self.cle <= noeud.cle:
if self.right is None:
self.right = noeud
noeud.parent = self
else:
self.right.inserer(noeud)
def enOrdre(self):
if self.left is not None:
self.left.enOrdre()
print(self.cle, end=' ')
if self.right is not None:
self.right.enOrdre()
class RechercheArbreBinaire:
def __init__(self):
self.root = None
def enOrdre(self):
if self.root is not None:
self.root.enOrdre()
def ajouter(self, cle):
nouveau_noeud = NoeudArbreBinaire(cle)
if self.root is None:
self.root = nouveau_noeud
else:
self.root.inserer(nouveau_noeud)
rechercheBinaireArbre = RechercheArbreBinaire()
tableau = [11, 222, 3, 899, 24, 5, 46, 67]
print(tableau)
for x in alist:
rechercheBinaireArbre.ajouter(x)
print('tableau trié:')
rechercheBinaireArbre.enOrdre()
Aussi vous pouvez consulter sur ce site : Website fr.wikipedia.org
https://128mots.com/index.php/category/python/
