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>
