1 """
   2 Funcionalidad: Representación de Arboles como Lista de Hijos.
   3 Autor: Diego Andrés Sanabria
   4 Licencia: GPL v2.0
   5 Fecha: Noviembre de 2005
   6 """
   7 class ArbolBinListaHijos:
   8     def __init__(self):
   9         self.lista=[]
  10         tmp=[]
  11         tmp.append(None)
  12         tmp.append(1)
  13         tmp.append(None)
  14         self.lista.append(tmp)
  15     def __repr__(self):
  16         r=""
  17         for i in range(1,len(self.lista)):
  18             r=r+str(i)+"). \t"+str(self.lista[i][0])+"\t"
  19             if self.lista[i][1]==None and self.lista[i][2]!=None:
  20                 r=r+"\t <- "+" 0 "+"\t <- "+str(self.lista[i][2])
  21             elif self.lista[i][1]!=None and self.lista[i][2]!=None:
  22                 r=r+"\t <- "+str(self.lista[i][1])+"\t <- "+str(self.lista[i][2])+"\t"
  23             elif self.lista[i][1]!=None and self.lista[i][2]==None:
  24                 r=r+"\t <- "+str(self.lista[i][1])+"\t"
  25             r=r+"\n"
  26         return r
  27     def insertar(self, dato):
  28         if len(self.lista)==1:
  29             self.adiElemento(dato)
  30             self.enlazar(0,1)
  31         else:
  32             self.adiElemento(dato)
  33             self.enlazar(1,len(self.lista)-1)
  34     def adiElemento(self,dato):
  35         listatmp=[]
  36         listatmp.append(dato)
  37         listatmp.append(None)
  38         listatmp.append(None)
  39         self.lista.append(listatmp)
  40     def enlazar(self,pos,upos):
  41         if pos==0:
  42             self.lista[pos][1]=upos
  43         else:
  44             if self.lista[pos][0]>self.lista[upos][0]:
  45                 if self.lista[pos][1]==None:
  46                     self.lista[pos][1]=upos
  47                 else:
  48                     self.enlazar(self.lista[pos][1],upos)
  49             elif self.lista[pos][0]<self.lista[upos][0]:
  50                 if self.lista[pos][2]==None:
  51                     self.lista[pos][2]=upos
  52                 else:
  53                     self.enlazar(self.lista[pos][2],upos)
  54             else:
  55                 self.lista.pop()
  56     def buscar(self,dato,pos=1):
  57         if self.lista[pos][0]==dato:
  58             print "El dato: "+str(dato)+" está en la posicion "+str(pos)
  59             return pos
  60         elif self.lista[pos][0]<dato:
  61             if self.lista[pos][2]==None:
  62                 print "El dato: "+str(dato)+" no esta en el arbol."
  63                 return None
  64             else:
  65                 return self.buscar(dato,self.lista[pos][2])
  66         elif self.lista[pos][0]>dato:
  67             if self.lista[pos][1]==None:
  68                 print "El dato: "+str(dato)+" no esta en el arbol."
  69                 return None
  70             else:
  71                 return self.buscar(dato,self.lista[pos][1])
  72         else:
  73             print "Que paso?"
  74     def menor(self,pos=1):
  75         if self.lista[pos][1]==None and self.lista[pos][2]==None:
  76             return pos;
  77         elif self.lista[pos][1]==None and self.lista[pos][2]!=None:
  78             return pos;
  79         else:
  80             return self.menor(self.lista[pos][1])