-
-
Save willamesoares/1af6f807bc6953c4c680 to your computer and use it in GitHub Desktop.
BSTNode.py - Binary Search Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- encoding:utf-8 -*- | |
#from __future__ import print_function | |
class BSTNode(object): | |
def __init__(self, key, value=None, left=None, right=None): | |
self.key = key | |
self.value = value | |
self.left = left | |
self.right = right | |
def get(self, key): | |
"""Retorna uma referência ao nó de chave key | |
""" | |
if self.key == key: | |
return self | |
node = self.left if key < self.key else self.right | |
if node is not None: | |
return node.get(key) | |
def add(self, key): | |
"""Adiciona elemento à subárvore | |
""" | |
side = 'left' if key < self.key else 'right' | |
node = getattr(self, side) | |
if node is None: | |
setattr(self, side, BSTNode(key)) | |
else: | |
node.add(key) | |
def remove(self, key): | |
"""Remove da árvore o elemento de chave key | |
""" | |
if key < self.key: | |
self.left = self.left.remove(key) | |
elif key > self.key: | |
self.right = self.right.remove(key) | |
else: | |
if self.right is None: | |
return self.left | |
if self.left is None: | |
return self.right | |
t = self.right._min() | |
self.key, self.value = t.key, t.value | |
self.right._deleteMin() | |
return self | |
def _min(self): | |
"""Retorna o menor elemento da subárvore | |
""" | |
if self.left is None: | |
return self | |
else: | |
return self.left._min() | |
def _deleteMin(self): | |
"""Remove da subárvore o menor elemento | |
""" | |
if self.left is None: # encontrou o min, daí pode rearranjar | |
return self.right | |
self.left = self.left._deleteMin() | |
return self | |
def traverse(self, order='pre'): | |
"""Percorre a árvore na ordem fornecida como parâmetro (pre, pos ou in) | |
visitando os nós com a função visit() recebida como parâmetro. | |
""" | |
if order == 'pre': | |
print self.key | |
if self.left is not None: | |
self.left.traverse(order) | |
if order == 'in': | |
print self.key | |
if self.right is not None: | |
self.right.traverse(order) | |
if order == 'post': | |
print self.key | |
""" | |
def print(self, order='pre'): | |
self.traverse(print, order) | |
""" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
O repositório foi clonado com o propósito de ser levemente alterado para que então possa ser aplicado em um caso específico, uma vez que eu encontrei dificuldades em utilizar o método
print()
definido, com Python 2.7.Obs.: O código original foi apenas comentado e não removido.