1 """
   2 Implementación de Arboles Binarios Ordenados usando la representación
   3 de Hijo Izquierdo Hermano Derecho con dos listas.
   4 Autor: Diego Andrés Sanabria Martín (diegueus9)
   5 Licencia: GPL v2.0
   6 Fecha: Noviembre de 2005
   7 """
   8 class ENodos:
   9     def __init__(self):
  10         self.etiqueta=None
  11         self.encabez=None
  12 class ECeldas:
  13     def __init__(self):
  14         self.nodo=None
  15         self.sig=None
  16 class ArbolBinHijoIzqHerDer:
  17     def __init__(self):
  18         self.nodos=[]
  19         self.celdas=[]
  20     def __repr__(self):
  21         r=""
  22         for i in range(1,len(self.lista)):
  23             r=r+str(i)+"). |"
  24             if self.lista[i].hijo!=None:
  25                 r=r+str(self.lista[i].hijo)+"\t|    "
  26             else:
  27                 r=r+" * \t|"
  28             if self.lista[i].clave!=None:
  29                 r=r+str(self.lista[i].clave)+"\t|"
  30             else:
  31                 r=r+" * \t|"
  32             if self.lista[i].hermano!=None:
  33                 r=r+str(self.lista[i].hermano)+"\t|"
  34             else:
  35                 r=r+" * \t|"
  36             r=r+"\n"
  37         return r
  38     def insertar(self, dato):
  39         if len(self.lista)==0:
  40             self.adiElemento(dato)
  41         else:
  42             self.adiElemento(dato)
  43             self.enlazar(0,len(self.lista)-1)
  44     def adiElemento(self,dato):
  45         tmp=ENodos()
  46         tmp.etiqueta=dato
  47         self.nodos.append(tmp)
  48         tmp2=ECeldas()
  49         tmp2.nodo=len(self.nodos)-1
  50         self.celdas.append(tmp2)
  51     def enlazar(self,pos,upos):
  52         if self.nodos[pos].etiqueta>self.nodos[upos].etiqueta:
  53             if self.nodos[pos].encabez==None:
  54 
  55         """
  56         if pos==0:
  57             self.lista[pos].hijo=upos
  58         else:
  59             if self.lista[pos].clave>self.lista[upos].clave:
  60                 if self.lista[pos].hijo==None:
  61                     self.lista[pos].hijo=upos
  62                 else:
  63                     self.enlazar(self.lista[pos].hijo,upos)
  64             elif self.lista[pos].clave<self.lista[upos].clave:
  65                 if self.lista[pos].hijo!=None:
  66                     tmp=self.lista[pos].hijo
  67                     if self.lista[tmp].hermano==None:
  68                         self.lista[tmp].hermano=upos
  69                     else:
  70                         self.enlazar(self.lista[tmp].hermano,upos)
  71             else:
  72                 self.lista.pop()
  73         """
  74     def buscar(self,dato,pos=1):
  75         if self.arreglo[pos].clave==dato:
  76             print "El dato: "+str(dato)+" está en la posicion "+str(pos)
  77             return pos
  78         elif self.arreglo[pos].clave<dato:
  79             if self.arreglo[pos][2]==None:
  80                 print "El dato: "+str(dato)+" no esta en el arbol."
  81                 return None
  82             else:
  83                 return self.buscar(dato,self.arreglo[pos][2])
  84         elif self.arreglo[pos].clave>dato:
  85             if self.arreglo[pos][1]==None:
  86                 print "El dato: "+str(dato)+" no esta en el arbol."
  87                 return None
  88             else:
  89                 return self.buscar(dato,self.arreglo[pos][1])
  90         else:
  91             print "Que paso?"