1 """Este código pertenece a Diego Andrés Sanabria y es liberado bajo la licencia GPL v2.0.
   2 """
   3 class Arbol:
   4     def __init__(self, clave,izq,der):
   5         # clave es la variable donde se guarda el dato
   6         self.clave=clave
   7         # es una variable de tipo arbol que contiene el arbol de izq
   8         self.izq=izq
   9         # es una variable de tipo arbol que contiene el arbol de izq
  10         self.der=der
  11 class ArbolBinArreglo:
  12     def __init__(self):
  13         self.arreglo=[]
  14         self.arreglo.append(Arbol(None,1,None))
  15     def insertar(self, dato):
  16         if len(self.arreglo)==1:
  17             self.adiElemento(dato)
  18             self.enlazar(0,1)
  19         else:
  20             self.adiElemento(dato)
  21             self.enlazar(1,len(self.arreglo)-1)
  22     def adiElemento(self, dato):
  23         self.arreglo.append(Arbol(dato,None,None))
  24     def enlazar(self,pos,upos):
  25         if pos==0:
  26             self.arreglo[pos].izq=upos
  27         else:
  28             if self.arreglo[pos].clave>self.arreglo[upos].clave:
  29                 if self.arreglo[pos].izq==None:
  30                     self.arreglo[pos].izq=upos
  31                 else:
  32                     self.enlazar(self.arreglo[pos].izq,upos)
  33             elif self.arreglo[pos].clave<self.arreglo[upos].clave:
  34                 if self.arreglo[pos].der==None:
  35                     self.arreglo[pos].der=upos
  36                 else:
  37                     self.enlazar(self.arreglo[pos].der,upos)
  38             else:
  39                 print "El elemento "+str(self.arreglo[upos].clave)+" ya esta en el arbol."
  40                 self.arreglo.pop()
  41     def eliminar(self, dato):
  42         pass
  43     def impArreglo(self):
  44         for i in range(0,len(self.arreglo)):
  45             print "Posicion "+str(i)
  46             print "Clave: "+str(self.arreglo[i].clave)+" P. Izq: "+str(self.arreglo[i].izq)+" P. Der: "+str(self.arreglo[i].der)
  47     def buscar(self,dato,pos=1):
  48         if self.arreglo[pos].clave==dato:
  49             print "El dato: "+str(dato)+" está en la posicion "+str(pos)
  50             return pos
  51         elif self.arreglo[pos].clave<dato:
  52             if self.arreglo[pos].der==None:
  53                 print "El dato: "+str(dato)+" no esta en el arbol."
  54                 return None
  55             else:
  56                 return self.buscar(dato,self.arreglo[pos].der)
  57         elif self.arreglo[pos].clave>dato:
  58             if self.arreglo[pos].izq==None:
  59                 print "El dato: "+str(dato)+" no esta en el arbol."
  60                 return None
  61             else:
  62                 return self.buscar(dato,self.arreglo[pos].izq)
  63         else:
  64             print "Que paso?"
  65     def __repr__(self):
  66         r="("
  67         for i in range(1,len(self.arreglo)):
  68             r=r+"[ "
  69             if self.arreglo[i].clave==None:
  70                 r=r+"_"
  71             else:
  72                 r=r+str(self.arreglo[i].clave)
  73             r=r+"|"
  74             if self.arreglo[i].izq==None:
  75                 r=r+"_"
  76             else:
  77                 r=r+str(self.arreglo[i].izq)
  78             r=r+"|"
  79             if self.arreglo[i].der==None:
  80                 r=r+"_"
  81             else:
  82                 r=r+str(self.arreglo[i].der)
  83             r=r+"] "
  84         r=r+")"
  85         return r