|
Tamanho: 2499
Comentário:
|
Tamanho: 4145
Comentário:
|
| Deleções são marcadas assim. | Adições são marcadas assim. |
| Linha 4: | Linha 4: |
| #!/usr/bin/python # |
|
| Linha 19: | Linha 17: |
| # # Constructor # |
|
| Linha 28: | Linha 31: |
# # Operators Overloading # def __str__(self): return str(self.content) def __add__(self, x): if type(x) is not type(self): return (self.content + x) # normal operation. else: return (self.content + x.content) # instance operation. def __sub__(self, x): if type(x) is not type(self): return (self.content - x) # normal operation. else: return (self.content - x.content) # instance operation. def __mul__(self, x): if type(x) is not type(self): return (self.content * x) # normal operation. else: return (self.content * x.content) # instance operation. def __div__(self, x): if type(x) is not type(self): return (self.content / x) # normal operation. else: return (self.content / x.content) # instance operation. # # Methods # |
|
| Linha 91: | Linha 121: |
| level = 1 |
|
| Linha 97: | Linha 125: |
| if self.content == element: break | if self.content == element: return self self = (self.lnode, self.rnode)[self.content <= element] |
| Linha 99: | Linha 128: |
| if self.content <= element: self = self.rnode else: self = self.lnode |
def delete(self, element=None): """ Delete an element of the tree. """ if not element: return -1 |
| Linha 102: | Linha 134: |
| level += 1 | if self.search(element): while (1): if not self: return None if (not self.lnode) and (not self.rnode): return None if self.lnode and self.lnode.content == element: break if self.rnode and self.rnode.content == element: break self = (self.lnode, self.rnode)[self.content <= element] |
| Linha 104: | Linha 144: |
| return level | if self.rnode and self.rnode.content == element: del self.rnode self.rnode = 0 if self.lnode and self.lnode.content == element: del self.lnode self.lnode = 0 return element def height(self): """ Returns the height of the tree. """ ltmp, rtmp = 0, 0 if not self: return 0 if self.lnode: ltmp = self.lnode.height() if self.rnode: rtmp = self.rnode.height() return ( 1 + max(ltmp, rtmp)) |
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) # normal operation.
38 else: return (self.content + x.content) # instance operation.
39
40 def __sub__(self, x):
41 if type(x) is not type(self): return (self.content - x) # normal operation.
42 else: return (self.content - x.content) # instance operation.
43
44 def __mul__(self, x):
45 if type(x) is not type(self): return (self.content * x) # normal operation.
46 else: return (self.content * x.content) # instance operation.
47
48 def __div__(self, x):
49 if type(x) is not type(self): return (self.content / x) # normal operation.
50 else: return (self.content / x.content) # instance operation.
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))
