|
Tamanho: 4145
Comentário:
|
Tamanho: 3972
Comentário:
|
| Deleções são marcadas assim. | Adições são marcadas assim. |
| Linha 7: | Linha 7: |
| """ Author: Danillo Souza Email: danillo012@gmail.com |
""" Author: Danillo Souza Email: danillo012@gmail.com |
| Linha 11: | Linha 11: |
| DESCRIPTION Class that implements Binary Search Tree functionality. |
DESCRIPTION Class that implements Binary Search Tree functionality. |
| Linha 14: | Linha 14: |
| TODO * improve the 'view' method to be more legible and nice; """ |
TODO * improve the 'view' method to be more legible and nice; """ |
| Linha 40: | Linha 40: |
| if type(x) is not type(self): return (self.content + x) # normal operation. else: return (self.content + x.content) # instance operation. |
if type(x) is not type(self): return (self.content + x) else: return (self.content + x.content) |
| Linha 44: | Linha 44: |
| if type(x) is not type(self): return (self.content - x) # normal operation. else: return (self.content - x.content) # instance operation. |
if type(x) is not type(self): return (self.content - x) else: return (self.content - x.content) |
| Linha 48: | Linha 48: |
| if type(x) is not type(self): return (self.content * x) # normal operation. else: return (self.content * x.content) # instance operation. |
if type(x) is not type(self): return (self.content * x) else: return (self.content * x.content) |
| Linha 52: | Linha 52: |
| if type(x) is not type(self): return (self.content / x) # normal operation. else: return (self.content / x.content) # instance operation. |
if type(x) is not type(self): return (self.content / x) else: return (self.content / x.content) |
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 DESCRIPTION
9 Class that implements Binary Search Tree functionality.
10
11 TODO
12 * improve the 'view' method to be more legible and nice;
13 """
14
15 #
16 # Constructor
17 #
18
19 def __init__(self, content=None):
20 """
21 Initialize the tree with a valid value(can't be None).
22 """
23 if not content: self.content = 0
24 else: self.content = content
25
26 self.lnode = None
27 self.rnode = None
28
29 #
30 # Operators Overloading
31 #
32
33 def __str__(self):
34 return str(self.content)
35
36 def __add__(self, x):
37 if type(x) is not type(self): return (self.content + x)
38 else: return (self.content + x.content)
39
40 def __sub__(self, x):
41 if type(x) is not type(self): return (self.content - x)
42 else: return (self.content - x.content)
43
44 def __mul__(self, x):
45 if type(x) is not type(self): return (self.content * x)
46 else: return (self.content * x.content)
47
48 def __div__(self, x):
49 if type(x) is not type(self): return (self.content / x)
50 else: return (self.content / x.content)
51
52 #
53 # Methods
54 #
55
56 def add(self, content=None):
57 """
58 Add an element to the tree. In the right if the value if is bigger than the
59 actual, and in the left if its less than the actual.
60 """
61 if not content: return -1
62
63 if content > self.content:
64 if self.rnode: self.rnode.add(content)
65 else: self.rnode = BSTree(content)
66
67 if content <= self.content:
68 if self.lnode: self.lnode.add(content)
69 else: self.lnode = BSTree(content)
70
71 def view(self, level=1):
72 """
73 Print the tree on the screen.
74 """
75 arrow = "---" * level
76 print "|%s>%s" % (arrow, self.content)
77
78 if self.rnode: self.rnode.view(level+1)
79 if self.lnode: self.lnode.view(level+1)
80
81 return
82
83 def size(self):
84 """
85 Returns the size of the tree.
86 """
87 tsize = 1
88
89 if self.rnode: tsize += self.rnode.size()
90 if self.lnode: tsize += self.lnode.size()
91
92 return tsize
93
94 def min(self):
95 """
96 Returns the minimum value of the tree.
97 """
98 while (self.lnode):
99 self = self.lnode
100
101 return self.content
102
103 def max(self):
104 """
105 Returns the maximum value of the tree.
106 """
107 while (self.rnode):
108 self = self.rnode
109
110 return self.content
111
112 def search(self, element=None):
113 """
114 Returns the level of the element on the tree.
115 """
116 if not element: return -1
117
118 while (1):
119 if not self: return -1
120 if (not self.lnode) and (not self.rnode): return -1
121
122 if self.content == element: return self
123 self = (self.lnode, self.rnode)[self.content <= element]
124
125 def delete(self, element=None):
126 """
127 Delete an element of the tree.
128 """
129 if not element: return -1
130
131 if self.search(element):
132 while (1):
133 if not self: return None
134 if (not self.lnode) and (not self.rnode): return None
135
136 if self.lnode and self.lnode.content == element: break
137 if self.rnode and self.rnode.content == element: break
138
139 self = (self.lnode, self.rnode)[self.content <= element]
140
141 if self.rnode and self.rnode.content == element:
142 del self.rnode
143 self.rnode = 0
144
145 if self.lnode and self.lnode.content == element:
146 del self.lnode
147 self.lnode = 0
148
149 return element
150
151 def height(self):
152 """
153 Returns the height of the tree.
154 """
155 ltmp, rtmp = 0, 0
156 if not self: return 0
157 if self.lnode: ltmp = self.lnode.height()
158 if self.rnode: rtmp = self.rnode.height()
159 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))
