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: self.content = 0
  18                 else: self.content = content
  19                 
  20                 self.lnode = None
  21                 self.rnode = None
  22 
  23         #
  24         # Operators Overloading
  25         #
  26 
  27         def __str__(self):
  28                 return str(self.content)
  29         
  30         def __add__(self, x):
  31                 if type(x) is not type(self): return (self.content + x)
  32                 else: return (self.content + x.content)                                 
  33 
  34         def __sub__(self, x):
  35                 if type(x) is not type(self): return (self.content - x)
  36                 else: return (self.content - x.content)                                 
  37 
  38         def __mul__(self, x):
  39                 if type(x) is not type(self): return (self.content * x)
  40                 else: return (self.content * x.content)                                 
  41 
  42         def __div__(self, x):
  43                 if type(x) is not type(self): return (self.content / x)
  44                 else: return (self.content / x.content)                         
  45 
  46         #
  47         # Methods
  48         #
  49 
  50         def add(self, content=None):
  51                 """
  52                 Add an element to the tree. In the right if the value if is bigger than the
  53                 actual, and in the left if its less than the actual.
  54                 """
  55                 if not content: return -1
  56 
  57                 if content > self.content:
  58                         if self.rnode: self.rnode.add(content)
  59                         else: self.rnode = BSTree(content)
  60 
  61                 if content <= self.content:
  62                         if self.lnode: self.lnode.add(content)
  63                         else: self.lnode = BSTree(content)
  64 
  65         def view(self, level=1):
  66                 """
  67                 Print the tree on the screen.
  68                 """
  69                 arrow = "---" * level
  70                 print "|%s>%s" % (arrow, self.content)
  71 
  72                 if self.rnode: self.rnode.view(level+1)
  73                 if self.lnode: self.lnode.view(level+1)
  74 
  75                 return
  76 
  77         def size(self):
  78                 """
  79                 Returns the size of the tree.
  80                 """
  81                 tsize = 1
  82 
  83                 if self.rnode: tsize += self.rnode.size()
  84                 if self.lnode: tsize += self.lnode.size()
  85 
  86                 return tsize
  87 
  88         def min(self):
  89                 """
  90                 Returns the minimum value of the tree.
  91                 """
  92                 while (self.lnode):
  93                         self = self.lnode
  94                 
  95                 return self.content
  96 
  97         def max(self):
  98                 """
  99                 Returns the maximum value of the tree.
 100                 """
 101                 while (self.rnode):
 102                         self = self.rnode
 103                 
 104                 return self.content
 105 
 106         def search(self, element=None):
 107                 """
 108                 Returns the level of the element on the tree.
 109                 """
 110                 if not element: return -1
 111 
 112                 while (1):
 113                         if not self: return -1
 114                         if (not self.lnode) and (not self.rnode): return -1
 115 
 116                         if self.content == element: return self
 117                         self = (self.lnode, self.rnode)[self.content <= element]
 118 
 119         def delete(self, element=None):
 120                 """
 121                 Delete an element of the tree.
 122                 """
 123                 if not element: return -1
 124 
 125                 if self.search(element):
 126                         while (1):
 127                                 if not self: return None
 128                                 if (not self.lnode) and (not self.rnode):
 129                                         return None
 130         
 131                                 if self.lnode and self.lnode.content == element:
 132                                         break
 133                                 if self.rnode and self.rnode.content == element:
 134                                         break
 135                                 
 136                                 self = (self.lnode, self.rnode)[self.content <= element]
 137 
 138                         if self.rnode and self.rnode.content == element: 
 139                                 del self.rnode
 140                                 self.rnode = 0
 141                         
 142                         if self.lnode and self.lnode.content == element:
 143                                 del self.lnode
 144                                 self.lnode = 0
 145                         
 146                         return element
 147 
 148         def height(self):
 149                 """
 150                 Returns the height of the tree.
 151                 """
 152                 ltmp, rtmp = 0, 0
 153                 if not self: return 0
 154                 if self.lnode: ltmp = self.lnode.height()
 155                 if self.rnode: rtmp = self.rnode.height()
 156                 return ( 1 + max(ltmp, rtmp))

   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))