Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
implementación de un Árbol binario de búsqueda
from __future__ import print_function
# Declaramos la clase "Node"
class Node:
def __init__(self, label, parent):
self.label = label
self.left = None
self.right = None
self.parent = parent
# Métodos para asignar nodos
def getLabel(self):
return self.label
def setLabel(self, label):
self.label = label
def getLeft(self):
return self.left
def setLeft(self, left):
self.left = left
def getRight(self):
return self.right
def setRight(self, right):
self.right = right
def getParent(self):
return self.parent
def setParent(self, parent):
self.parent = parent
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, label):
# Creamos un nuevo nodo
new_node = Node(label, None)
# Si el árbol esta vacio
if self.empty():
self.root = new_node
else:
# Si el árbol no esta vacio
curr_node = self.root
while curr_node is not None:
parent_node = curr_node
if new_node.getLabel() < curr_node.getLabel():
curr_node = curr_node.getLeft()
else:
curr_node = curr_node.getRight()
if new_node.getLabel() < parent_node.getLabel():
parent_node.setLeft(new_node)
else:
parent_node.setRight(new_node)
new_node.setParent(parent_node)
# Operación de borrado
def delete(self, label):
if (not self.empty()):
node = self.getNode(label)
if(node is not None):
if(node.getLeft() is None and node.getRight() is None):
self.__reassignNodes(node, None)
node = None
elif(node.getLeft() is None and node.getRight() is not None):
self.__reassignNodes(node, node.getRight())
elif(node.getLeft() is not None and node.getRight() is None):
self.__reassignNodes(node, node.getLeft())
else:
tmpNode = self.getMax(node.getLeft())
self.delete(tmpNode.getLabel())
node.setLabel(tmpNode.getLabel())
def getNode(self, label):
curr_node = None
if(not self.empty()):
curr_node = self.getRoot()
while curr_node is not None and curr_node.getLabel() is not label:
if label < curr_node.getLabel():
curr_node = curr_node.getLeft()
else:
curr_node = curr_node.getRight()
return curr_node
def getMax(self, root = None):
if(root is not None):
curr_node = root
else:
curr_node = self.getRoot()
if(not self.empty()):
while(curr_node.getRight() is not None):
curr_node = curr_node.getRight()
return curr_node
def getMin(self, root = None):
if(root is not None):
curr_node = root
else:
curr_node = self.getRoot()
if(not self.empty()):
curr_node = self.getRoot()
while(curr_node.getLeft() is not None):
curr_node = curr_node.getLeft()
return curr_node
def empty(self):
if self.root is None:
return True
return False
def __InOrderTraversal(self, curr_node):
nodeList = []
if curr_node is not None:
nodeList.insert(0, curr_node)
nodeList = nodeList + self.__InOrderTraversal(curr_node.getLeft())
nodeList = nodeList + self.__InOrderTraversal(curr_node.getRight())
return nodeList
def getRoot(self):
return self.root
def __isRightChildren(self, node):
if(node == node.getParent().getRight()):
return True
return False
def __reassignNodes(self, node, newChildren):
if(newChildren is not None):
newChildren.setParent(node.getParent())
if(node.getParent() is not None):
if(self.__isRightChildren(node)):
node.getParent().setRight(newChildren)
else:
node.getParent().setLeft(newChildren)
def traversalTree(self, traversalFunction = None, root = None):
if(traversalFunction is None):
return self.__InOrderTraversal(self.root)
else:
return traversalFunction(self.root)
def __str__(self):
list = self.__InOrderTraversal(self.root)
str = ""
for x in list:
str = str + " " + x.getLabel().__str__()
return str
def InPreOrder(curr_node):
nodeList = []
if curr_node is not None:
nodeList = nodeList + InPreOrder(curr_node.getLeft())
nodeList.insert(0, curr_node.getLabel())
nodeList = nodeList + InPreOrder(curr_node.getRight())
return nodeList
# Función para probar las clases
def testBinarySearchTree():
'''
Ejemplo
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
'''
'''
Ejemplo luego del borrado
7
/ \
1 4
'''
# Instancia del árbol binario de búsqueda
t = BinarySearchTree()
#Insertamos los elementos
t.insert(8)
t.insert(3)
t.insert(6)
t.insert(1)
t.insert(10)
t.insert(14)
t.insert(13)
t.insert(4)
t.insert(7)
print(t.__str__())
if(t.getNode(6) is not None):
print("El elemento 6 existe")
else:
print("El elemento 6 no existe")
if(t.getNode(-1) is not None):
print("El elemento -1 existe")
else:
print("El elemento -1 no existe")
if(not t.empty()):
print(("Valor Max: ", t.getMax().getLabel()))
print(("Valor Min: ", t.getMin().getLabel()))
t.delete(13)
t.delete(10)
t.delete(8)
t.delete(3)
t.delete(6)
t.delete(14)
# Obtenemos todos los elementos del árbol en preorden
list = t.traversalTree(InPreOrder, t.root)
for x in list:
print(x)
if __name__ == "__main__":
testBinarySearchTree()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.