associação pythonbrasil[11] django zope/plone planet Início Logado como (Entrar)

ArvoreDeBuscaBinaria

Classe que implementa de maneira simples uma Árvore de Busca Binária.

   1 # BSTree.py
   2 
   3 class BSTree:
   4         """
   5         Author: Danillo Souza
   6         Email: danillo012@gmail.com
   7         """
   8         
   9         #
  10         # Constructor
  11         #
  12 
  13         def __init__(self, content=None):
  14                 """
  15                 Initialize the tree with a valid value(can't be None).
  16                 """
  17                 if not content:
  18                         self.content = 0
  19                 else:
  20                         self.content = content
  21                 
  22                 self.lnode = None
  23                 self.rnode = None
  24 
  25         #
  26         # Operators Overloading
  27         #
  28 
  29         def __str__(self):
  30                 return str(self.content)
  31         
  32         
  33         def __add__(self, x):
  34                 if type(x) is not type(self):
  35                         return (self.content + x)
  36                 else: 
  37                         return (self.content + x.content)                                       
  38 
  39                         
  40         def __sub__(self, x):
  41                 if type(x) is not type(self):
  42                         return (self.content - x)
  43                 else:
  44                         return (self.content - x.content)                                       
  45 
  46                         
  47         def __mul__(self, x):
  48                 if type(x) is not type(self):
  49                         return (self.content * x)
  50                 else:
  51                         return (self.content * x.content)                                       
  52 
  53                         
  54         def __div__(self, x):
  55                 if type(x) is not type(self):
  56                         return (self.content / x)
  57                 else:
  58                         return (self.content / x.content)                               
  59 
  60         #
  61         # Methods
  62         #
  63 
  64         def add(self, content=None):
  65                 """
  66                 Add an element to the tree. In the right if the value if is bigger than the
  67                 actual, and in the left if its less than the actual.
  68                 """
  69                 if not content:
  70                         return -1
  71 
  72                 if content > self.content:
  73                         if self.rnode:
  74                                 self.rnode.add(content)
  75                         else:
  76                                 self.rnode = BSTree(content)
  77 
  78                 if content <= self.content:
  79                         if self.lnode:
  80                                 self.lnode.add(content)
  81                         else: 
  82                                 self.lnode = BSTree(content)
  83 
  84                                 
  85         def view(self, level=1):
  86                 """
  87                 Print the tree on the screen.
  88                 """
  89                 arrow = "---" * level
  90                 print "|%s>%s" % (arrow, self.content)
  91 
  92                 if self.rnode:
  93                         self.rnode.view(level+1)
  94                 if self.lnode:
  95                         self.lnode.view(level+1)
  96 
  97                 return
  98 
  99                 
 100         def size(self):
 101                 """
 102                 Returns the size of the tree.
 103                 """
 104                 tsize = 1
 105 
 106                 if self.rnode:
 107                         tsize += self.rnode.size()
 108                 if self.lnode:
 109                         tsize += self.lnode.size()
 110 
 111                 return tsize
 112 
 113                 
 114         def min(self):
 115                 """
 116                 Returns the minimum value of the tree.
 117                 """
 118                 while (self.lnode):
 119                         self = self.lnode
 120                 
 121                 return self.content
 122 
 123                 
 124         def max(self):
 125                 """
 126                 Returns the maximum value of the tree.
 127                 """
 128                 while (self.rnode):
 129                         self = self.rnode
 130                 
 131                 return self.content
 132 
 133                 
 134         def search(self, element=None):
 135                 """
 136                 Returns the level of the element on the tree.
 137                 """
 138                 if not element: return -1
 139 
 140                 while (1):
 141                         if not self:
 142                                 return -1
 143                         if (not self.lnode) and (not self.rnode):
 144                                 return -1
 145 
 146                         if self.content == element:
 147                                 return self
 148                         
 149                         self = (self.lnode, self.rnode)[self.content <= element]
 150 
 151                         
 152         def delete(self, element=None):
 153                 """
 154                 Delete an element of the tree.
 155                 """
 156                 if not element: return -1
 157 
 158                 if self.search(element):
 159                         while (1):
 160                                 if not self:
 161                                         return None
 162                                 if (not self.lnode) and (not self.rnode):
 163                                         return None
 164         
 165                                 if self.lnode and self.lnode.content == element:
 166                                         break
 167                                 if self.rnode and self.rnode.content == element:
 168                                         break
 169                                 
 170                                 self = (self.lnode, self.rnode)[self.content <= element]
 171 
 172                         if self.rnode and self.rnode.content == element: 
 173                                 del self.rnode
 174                                 self.rnode = 0
 175                         
 176                         if self.lnode and self.lnode.content == element:
 177                                 del self.lnode
 178                                 self.lnode = 0
 179                         
 180                         return element
 181 
 182                         
 183         def height(self):
 184                 """
 185                 Returns the height of the tree.
 186                 """
 187                 ltmp, rtmp = 0, 0
 188                 if not self:
 189                         return 0
 190                 if self.lnode:
 191                         ltmp = self.lnode.height()
 192                 if self.rnode:
 193                         rtmp = self.rnode.height()
 194                 return ( 1 + max(ltmp, rtmp))

Exemplo de funcionamento:

   1 #!/usr/bin/python
   2 import BSTree
   3 from random import randint
   4 
   5 tree = BSTree(50)
   6 for i in range(100):
   7         tree.add(randint(1, 100))
   8 tree.view()
   9 
  10 print '=' * 25
  11 print "Min: %d" % tree.min()
  12 print "Max: %d" % tree.max()
  13 
  14 sort = randint(1, 100)
  15 print "%d found in %d level." % (sort, tree.search(sort))

Danillo Souza <danillo012@gmail.com>