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