1 """
   2 Implementación de Arboles Binarios Ordenados usando la representación
   3 de Hijo Izquierdo Hermano Derecho con una sola lista.
   4 Autor: Diego Andrés Sanabria Martín (diegueus9)
   5 Licencia: GPL v2.0
   6 Fecha: Noviembre de 2005
   7 """
   8 class Arbol:
   9     def __init__(self,hijo=None,clave=None,hermano=None):
  10         self.hijo=hijo
  11         self.clave=clave
  12         self.hermano=hermano
  13 class ArbolBinHijoIzqHerDer:
  14     def __init__(self):
  15         self.lista=[]
  16         tmp=Arbol()
  17         self.lista.append(tmp)
  18     def __repr__(self):
  19         r=""
  20         for i in range(1,len(self.lista)):
  21             r=r+str(i)+"). |"
  22             if self.lista[i].hijo!=None:
  23                 r=r+str(self.lista[i].hijo)+"\t|    "
  24             else:
  25                 r=r+" * \t|"
  26             if self.lista[i].clave!=None:
  27                 r=r+str(self.lista[i].clave)+"\t|"
  28             else:
  29                 r=r+" * \t|"
  30             if self.lista[i].hermano!=None:
  31                 r=r+str(self.lista[i].hermano)+"\t|"
  32             else:
  33                 r=r+" * \t|"
  34             r=r+"\n"
  35         return r
  36     def insertar(self, dato):
  37         if len(self.lista)==1:
  38             self.adiElemento(dato)
  39             self.enlazar(0,1)
  40         else:
  41             self.adiElemento(dato)
  42             self.enlazar(1,len(self.lista)-1)
  43     def adiElemento(self,dato):
  44         listatmp=Arbol(None,dato,None)
  45         self.lista.append(listatmp)
  46     def enlazar(self,pos,upos):
  47         if pos==0:
  48             self.lista[pos].hijo=upos
  49         else:
  50             if self.lista[pos].clave>self.lista[upos].clave:
  51                 if self.lista[pos].hijo==None:
  52                     self.lista[pos].hijo=upos
  53                 else:
  54                     self.enlazar(self.lista[pos].hijo,upos)
  55             elif self.lista[pos].clave<self.lista[upos].clave:
  56                 if self.lista[pos].hijo!=None:
  57                     tmp=self.lista[pos].hijo
  58                     if self.lista[tmp].hermano==None:
  59                         self.lista[tmp].hermano=upos
  60                     else:
  61                         self.enlazar(self.lista[tmp].hermano,upos)
  62             else:
  63                 self.lista.pop()