#//////////////////////////////////////////////////////////////////////////////////
/////////////
Modulo [Link]
#//////////////////////////////////////////////////////////////////////////////////
/////////////
# Paquete [Link]
# jue oct 12 13:26:46 ART 2017
# Algoritmos y Estructuaras de datos I
# Funciones de carga de valores
import copy
def input_int( str ):
try:
ingreso=int(float(input( str )))
except:
ingreso=0
return ingreso
def input_real( str ):
try:
ingreso=float(input( str ))
except:
ingreso=0.0
return ingreso
def input_str( str ):
try:
ingreso=input( str )
except:
ingreso=""
return ingreso
# Clase arreglos
class Array:
data=[]
def __init__(self,size=None,init_value=0):
if size == None:
[Link]=0
else:
[Link]=size
if type(init_value)!=Array:
[Link]= [[Link](None) for i in range(0,size)]
else:
[Link]= [[Link](init_value) for i in range(0,size)]
[Link] = type(init_value)
def __getitem__(self,index):
if index > [Link]:
print ("IndexError: index Out of bounds")
else:
return [Link][index]
def __setitem__(self,index,value):
if index > [Link]:
print ("IndexError: index Out of bounds")
elif type(value) != [Link] and value!=None:
print ("TypeError: value error")
else:
[Link][index]=value
def __str__(self):
return str([[Link][i] for i in range(0,len([Link]))])
def __len__(self):
return([Link])
class String:
def __init__(self,string):
[Link]=Array(len(string),'c')
[Link]=string
def __getitem__(self,index):
return [Link][index]
def __setitem__(self,index,value):
[Link][index]=value
def __str__(self):
return str([Link])
def __len__(self):
return len([Link])
def substr(t,start,end):
return String(''.join([t[i] for i in range(start,end)] ))
# O(t+1). Donde t es la cantidad de caracteres que matchearon y 1 es para el caso
de t=0
def strcmp(t,p):
for i in range(0,len(p)):
if t[i] != p[i]:
return False
return True
def concat(s,c):
return String([Link]+c)
#//////////////////////////////////////////////////////////////////////////////////
/////////////
Modulo [Link]
#//////////////////////////////////////////////////////////////////////////////////
/////////////
"""
add(LinkedList, element)
------------------------
Descripción: Agrega un elemento al comienzo de L, siendo L una LinkedList
que representa el TAD secuencia.
Entrada: La Lista sobre la cual se quiere agregar el elemento
(LinkedList) y el valor del elemento (element) a agregar.
Salida: No hay salida definida
search(LinkedList, element)
---------------------------
Descripción: Busca un elemento de la lista que representa el TAD
secuencia.
Entrada: la lista sobre el cual se quiere realizar la búsqueda
(Linkedlist) y el valor del elemento (element) a buscar.
Salida: Devuelve la posición donde se encuentra la primera instancia
del elemento. Devuelve None si el elemento no se encuentra
insert(LinkedList, element, position)
-------------------------------------
Descripción: Inserta un elemento en una posición determinada de la
lista que representa el TAD secuencia.
Entrada: la lista sobre el cual se quiere realizar la inserción
(Linkedlist) y el valor del elemento (element) a insertar y la
posición (position) donde se quiere insertar.
Salida: Si pudo insertar con éxito devuelve la posición donde se
inserta el elemento. En caso contrario devuelve None. Devuelve None si
la posición a insertar es mayor que el número de elementos en la
lista.
delete(LinkedList, element)
---------------------------
Descripción: Elimina un elemento de la lista que representa el TAD
secuencia.
Poscondición: Se debe desvincular el Node a eliminar.
Entrada: la lista sobre el cual se quiere realizar la eliminación
(Linkedlist) y el valor del elemento (element) a eliminar.
Salida: Devuelve la posición donde se encuentra el elemento a
eliminar. Devuelve None si el elemento a eliminar no se encuentra.
length(LinkedList)
------------------
Descripción: Calcula el número de elementos de la lista que representa
el TAD secuencia.
Entrada: La lista sobre la cual se quiere calcular el número de
elementos.
Salida: Devuelve el número de elementos
access(LinkedList, position)
----------------------------
Descripción: Permite acceder a un elemento de la lista en una posición
determinada.
Entrada: La lista (LinkedList) y la position del elemento al cual se
quiere acceder.
Salida: Devuelve el valor de un elemento en una position de la lista,
devuelve None si no existe elemento para dicha posición
update(LinkedList, element, position)
-------------------------------------
Descripción: Permite cambiar el valor de un elemento de la lista en
una posición determinada.
Entrada: La lista (LinkedList) y la position sobre la cual se quiere
asignar el valor de element.
Salida: Devuelve None si no existe elementopara dicha posición. Caso
contrario devuelve la posición donde pudo hacer el update.
printList(LinkedList)
---------------------
Descripcion: Muestra en forma consecutiva los elementos
de una lista (LinkedList) pasada por parámetro
revert(LinkedList)
------------------
Descripcion: invierte el orden de una lista.
Entrada: la lista linkedlist a la que se le quiere invertir el orden.
Salida: una lista con los elementos de la lista de entrada en orden invertido.
reverseList(LinkedList)
----------------------
Descripcion: invierte el orden de una lista.
Entrada: la lista linkedlist a la que se le quiere invertir el orden.
Salida: No definida.
copyLinkedList(LinkedList)
--------------------------
Descripción: copia una LinkedList.
Entrada: La lista LinkedList a copiar.
Salida: Devuelve una copia de la lista de entrada.
"""
from algo1 import *
# A partir de una estructura LinkedList definida de la siguiente manera:
class LinkedList:
head = None
class Node:
value = None
nextNode = None
# Crear un modulo de nombre [Link] que implemente las siguientes
especificaciones de las
# operaciones elementales para el TAD secuencia utilizando el TAD lista.
def add(L,element):
"""add(L, element)
Descripción: Agrega un elemento al comienzo de L, siendo L una LinkedList
que representa el TAD secuencia.
Entrada: La Lista sobre la cual se quiere agregar el elemento
(LinkedList) y el valor del elemento (element) a agregar.
Salida: No hay salida definida"""
node = Node()
[Link] = element
if [Link] == None:
[Link] = node
else:
[Link] = [Link]
[Link] = node
#------------------------------------------------------------------
"""
def printList(L):
if [Link]:
node = [Link]
while node:
print([Link])"""
def printList(L):
"""Descripcion: Muestra en forma consecutiva los elementos
de una lista (LinkedList) pasada por parámetro"""
if [Link] == None:
print("[]")
else:
node = [Link]
while node != None:
if [Link] != None:
print([Link],end=" --> ")
else:
print([Link])
node = [Link]
#------------------------------------------------------------------
def search(L, element):
"""Descripción: Busca un elemento de la lista que representa el TAD
secuencia.
Entrada: la lista sobre el cual se quiere realizar la búsqueda
(Linkedlist) y el valor del elemento (element) a buscar.
Salida: Devuelve la posición donde se encuentra la primera instancia
del elemento. Devuelve None si el elemento no se encuentra"""
node = [Link]
cont = 0
while node != None:
if [Link] == element:
return cont
cont += 1
node = [Link]
#------------------------------------------------------------------
def insert(L,element,position):
"""insert(L, element, position)
Descripción: Inserta un elemento en una posición determinada de la
lista que representa el TAD secuencia.
Entrada: la lista sobre el cual se quiere realizar la inserción
(Linkedlist) y el valor del elemento (element) a insertar y la
posición (position) donde se quiere insertar.
Salida: Si pudo insertar con éxito devuelve la posición donde se
inserta el elemento. En caso contrario devuelve None. Devuelve None si
la posición a insertar es mayor que el número de elementos en la
lista. """
if position == 0:
add(L, element)
return 0
else:
node = [Link] # cargo node con el primer nodo
cont = 0
while node is not None: # mientras no llegue al final de la lista
if cont == position -1:
newNode = Node()
[Link] = element
[Link] = [Link]
[Link] = newNode
return position
cont += 1
node = [Link]
#------------------------------------------------------------------
def delete(L,element):
"""delete(L, element)
Descripción: Elimina un elemento de la lista que representa el TAD
secuencia.
Poscondición: Se debe desvincular el Node a eliminar.
Entrada: la lista sobre el cual se quiere realizar la eliminación
(Linkedlist) y el valor del elemento (element) a eliminar.
Salida: Devuelve la posición donde se encuentra el elemento a
eliminar. Devuelve None si el elemento a eliminar no se encuentra."""
if [Link] != None:
if [Link] == element:
[Link] = [Link]
return 0
node = [Link]
cont = 0
while [Link] != None:
if [Link] == element:
[Link] = [Link]
return cont + 1
cont += 1
node = [Link]
#------------------------------------------------------------------
def length(L):
"""Descripción: Calcula el número de elementos de la lista que representa
el TAD secuencia.
Entrada: La lista sobre la cual se quiere calcular el número de
elementos.
Salida: Devuelve el número de elementos"""
cont = 0
if [Link] != None:
node = [Link]
while node != None:
cont += 1
node = [Link]
return cont
#------------------------------------------------------------------
def access(L, position):
"""Descripción: Permite acceder a un elemento de la lista en una posición
determinada.
Entrada: La lista (LinkedList) y la position del elemento al cual se
quiere acceder.
Salida: Devuelve el valor de un elemento en una position de la lista,
devuelve None si no existe elemento para dicha posición."""
if [Link] != None:
node = [Link]
cont = 0
while node != None:
if cont == position:
return [Link]
cont += 1
node = [Link]
#------------------------------------------------------------------
def update(L,element,position):
"""update(L, element, position)
Descripción: Permite cambiar el valor de un elemento de la lista en
una posición determinada.
Entrada: La lista (LinkedList) y la position sobre la cual se quiere
asignar el valor de element.
Salida: Devuelve None si no existe elementopara dicha posición. Caso
contrario devuelve la posición donde pudo hacer el update."""
if [Link]:
node = [Link]
cont = 0
while node:
if cont == position:
[Link] = element
return position
cont += 1
node = [Link]
#------------------------------------------------------------------
def revert(L):
"""Descripcion: invierte el orden de una lista.
Entrada: la lista linkedlist a la que se le quiere invertir el orden.
Salida: una lista con los elementos de la lista de entrada en orden
invertido."""
if [Link]:
Reverted_list = LinkedList()
node = [Link]
while node != None:
add(Reverted_list, [Link])
node = [Link]
return Reverted_list
#------------------------------------------------------------------
def reverseList(L):
"""Descripcion: invierte el orden en la misma lista.
Entrada: la lista linkedlist a la que se le quiere invertir el orden.
Salida: No definida."""
prev = None
current = [Link]
while current is not None:
if [Link] is None:
[Link] = prev
[Link] = current
return
next = [Link]
[Link] = prev
prev = current
current = next
#------------------------------------------------------------------
def copyLinkedList(L):
"""Descripción: copia una LinkedList.
Entrada: La lista LinkedList a copiar.
Salida: Devuelve una copia de la lista de entrada."""
if [Link] == None:
return
copyList = LinkedList()
currentNode = [Link]
while currentNode != None:
add(copyList, [Link])
currentNode = [Link]
return revert(copyList)
"""
P = LinkedList()
print("insert(P,77,7):",insert(P,77,7))
print("insert(P,11,1):",insert(P,11,1))
print("insert(P,00,0):",insert(P,00,0))
add(P,22)
add(P,44)
add(P,66)
add(P,11)
add(P,55)
add(P,77)
printList(P)
print("search(P,99):",search(P,99))
print("search(P,22):",search(P,22))
print("search(P,44):",search(P,44))
print("search(P,11):",search(P,11))
print("search(P,55):",search(P,55))
print("search(P,77):",search(P,77))
print("length(P):",length(P))
print("access(P,0):",access(P,0))
print("access(P,1):",access(P,1))
print("access(P,2):",access(P,2))
print("access(P,3):",access(P,3))
print("access(P,4):",access(P,4))
print("access(P,5):",access(P,5))
print("access(P,6):",access(P,6))
print("update(P,33,0):",update(P,33,0))
print("update(P,99,2):",update(P,99,2))
print("update(P,88,5):",update(P,88,5))
print("update(P,99,6):",update(P,99,6))
print("access(P,0):",access(P,0))
print("access(P,2):",access(P,2))
print("access(P,5):",access(P,5))
print("access(P,6):",access(P,6))
printList(P)
print("insert(P,77,3):",insert(P,77,3))
printList(P)
print("insert(P,11,1):",insert(P,11,1))
printList(P)
print("delete(P,99):",delete(P,99))
printList(P)
print("delete(P,88):",delete(P,88))
printList(P)
print("delete(P,99):",delete(P,99))
printList(P)
print("delete(P,11):",delete(P,11))
printList(P)
print("delete(P,33):",delete(P,33))
printList(P)
print("delete(P,99):",delete(P,99))
reverseList(P)
printList(P)"""
#//////////////////////////////////////////////////////////////////////////////////
/////////////
[Link]
#//////////////////////////////////////////////////////////////////////////////////
/////////////
"""
enqueue(Q,element)
------------------
Descripción: Agrega un elemento al comienzo de Q, siendo Q una
estructura de tipo LinkedList.
Entrada: La cola Q (LinkedList) sobre la cual se quiere agregar
el elemento y el valor del elemento (element) a agregar.
Salida: No hay salida definida.
dequeue(Q)
----------
Descripción: extrae el último elemento de la cola Q, siendo Q
una estructura de tipo LinkedList.
Poscondición: Se debe desvincular el Node a eliminar.
Entrada: la cola Q (Linkedlist) sobre el cual se quiere realizar
la eliminación.
Salida: Devuelve el elemento de la cola. Devuelve None si la
cola está vacía.
"""
from algo1 import *
from linkedlist import add
"""Ejercicio 2
Crear un módulo de nombre [Link] que implemente las siguientes especificaciones
de
las operaciones elementales para un TAD Cola utilizando el TAD Lista. Recordar que
una
Cola puede implementarse también sobre una estructura LinkedList donde, el primer
elemento en ingresar a la lista es el primero en salir (FIFO)."""
def enqueue(Q,element):
"""enqueue(Q,element)
Descripción: Agrega un elemento al comienzo de Q, siendo Q una
estructura de tipo LinkedList.
Entrada: La cola Q (LinkedList) sobre la cual se quiere agregar
el elemento y el valor del elemento (element) a agregar.
Salida: No hay salida definida."""
add(Q,element)
def dequeue(Q):
"""dequeue(Q)
Descripción: extrae el último elemento de la cola Q, siendo Q
una estructura de tipo LinkedList.
Poscondición: Se debe desvincular el Node a eliminar.
Entrada: la cola Q (Linkedlist) sobre el cual se quiere realizar
la eliminación.
Salida: Devuelve el elemento de la cola. Devuelve None si la
cola está vacía.
"""
if [Link] == None:
return None
currentNode = [Link]
if [Link] == None:
[Link] = None
return [Link]
while [Link] != None:
currentNode = [Link]
element = [Link]
[Link] = None
return element
#//////////////////////////////////////////////////////////////////////////////////
/////////////
[Link]
#//////////////////////////////////////////////////////////////////////////////////
/////////////
"""
enqueue_priority(Q, element, priority)
--------------------------------------
Descripción: Agrega un elemento a Q con la prioridad priority
(entero), siendo Q una estructura de tipo PriorityQueue
Entrada: La cola Q sobre la cual se quiere agregar el elemento
(PriorityQueue), el valor del elemento (element) a agregar y un
número que indica la prioridad.
Salida: Devuelve la posición donde se inserto el elemento.
dequeue_priority(Q)
-------------------
Descripción: extrae el primer elemento de la cola Q con la mayor
prioridad (un valor mayor del campo priority, indica una mayor
prioridad), siendo Q una estructura de tipo PriorityQueue.
Poscondición: Se debe desvincular el Node a eliminar.
Entrada: la cola sobre el cual se quiere realizar la eliminación
(PriorityQueue)
Salida: Devuelve el elemento con mayor prioridad. Devuelve None
si la cola está vacía.
"""
"""Ejercicio 3
A partir de las estructuras definidas como:
class PriorityQueue:
head=None
class PriorityNode:
value=None
nextNode=None
priority=None
Crear un módulo de nombre [Link] que implemente una cola con prioridad.
Una cola con prioridad es un TAD similar a una cola en la que los elementos tienen
adicionalmente, una prioridad asignada. En una cola de prioridades un elemento con
mayor
prioridad será encolado antes que un elemento de menor prioridad. Si dos elementos
tienen
la misma prioridad, se desencolarán siguiendo el orden de cola."""
from algo1 import *
from linkedlist import add
class PriorityQueue:
head = None
class PriorityNode:
value = None
priority = None
nextNode = None
def enqueue_priority(Q, element, priority):
"""enqueue_priority(Q, element, priority)
Descripción: Agrega un elemento a Q con la prioridad priority
(entero), siendo Q una estructura de tipo PriorityQueue
Entrada: La cola Q sobre la cual se quiere agregar el elemento
(PriorityQueue), el valor del elemento (element) a agregar y un
número que indica la prioridad.
Salida: Devuelve la posición donde se inserto el elemento."""
newNode = PriorityNode()
[Link] = element
[Link] = priority
if [Link] == None:
[Link] = newNode
return 0
if [Link] > [Link]:
[Link] = [Link]
[Link] = newNode
return 0
currentNode = [Link]
cont = 0
while currentNode != None and [Link] >= [Link]:
previousNode = currentNode
currentNode = [Link]
cont += 1
[Link] = currentNode
[Link] = newNode
return cont
def dequeue_priority(Q):
"""dequeue_priority(Q)
Descripción: extrae el primer elemento de la cola Q con la mayor
prioridad (un valor mayor del campo priority, indica una mayor
prioridad), siendo Q una estructura de tipo PriorityQueue.
Poscondición: Se debe desvincular el Node a eliminar.
Entrada: la cola sobre el cual se quiere realizar la eliminación
(PriorityQueue)
Salida: Devuelve el elemento con mayor prioridad. Devuelve None
si la cola está vacía."""
if [Link] != None:
element = [Link]
[Link] = [Link]
return element
#//////////////////////////////////////////////////////////////////////////////////
/////////////
[Link]
#//////////////////////////////////////////////////////////////////////////////////
/////////////
"""
search(BinaryTree, element)
-----------------
Descripción: Busca un elemento en el TAD árbol binario.
Entrada: el árbol binario B en el cual se quiere realizar la búsqueda
(BinaryTree) y el valor del elemento (element) a buscar.
Salida: Devuelve la key asociada a la primera instancia del elemento.
Devuelve None si el elemento no se encuentra.
insert(BinaryTree, element, key)
---------------------
Descripción: Inserta un elemento con una clave determinada del TAD
árbol binario.
Entrada: el árbol B sobre el cual se quiere realizar la inserción
(BinaryTree), el valor del elemento (element) a insertar y la clave
(key) con la que se lo quiere insertar.
Salida: Si pudo insertar con éxito devuelve la key donde se inserta el
elemento. En caso contrario devuelve None.
delete(BinaryTree, element)
-----------------
Descripción: Elimina un elemento del TAD árbol binario.
Poscondición: Se debe desvincular el Node a eliminar.
Entrada: el árbol binario B sobre el cual se quiere realizar la
eliminación (BinaryTree) y el valor del elemento (element) a eliminar.
Salida: Devuelve clave (key) del elemento a eliminar. Devuelve None si
el elemento a eliminar no se encuentra.
deleteKey(BinaryTree, key)
----------------
Descripción: Elimina una clave del TAD árbol binario.
Poscondición: Se debe desvincular el Node a eliminar.
Entrada: el árbol binario B sobre el cual se quiere realizar la
eliminación (BinaryTree) y el valor de la clave (key) a eliminar.
Salida: Devuelve clave (key) a eliminar. Devuelve None si el elemento
a eliminar no se encuentra.
access(BinaryTree, key)
-------------
Descripción: Permite acceder a un elemento del árbol binario con una
clave determinada.
Entrada: El árbol binario (BinaryTree) y la key del elemento al cual
se quiere acceder.
Salida: Devuelve el valor de un elemento con una key del árbol.
binario, devuelve None si no existe elemento con dicha clave.
update(BinaryTree, element, key)
---------------------
Descripción: Permite cambiar el valor de un elemento del árbol binario
con una clave determinada.
Entrada: El árbol binario (BinaryTree) y la clave (key) sobre la cual
se quiere asignar el valor de element.
Salida: Devuelve None si no existe elemento para dicha clave. Caso
contrario devuelve la clave del nodo donde se hizo el update.
traverseInOrder(BinaryTree)
------------------
Descripción: Recorre un árbol binario en orden.
Entrada: El árbol binario (BinaryTree).
Salida: Devuelve una lista (LinkedList) con los elementos del árbol en
orden. Devuelve None si el árbol está vacío.
traverseInPostOrder(BinaryTree)
----------------------
Descripción: Recorre un árbol binario en post-orden.
Entrada: El árbol binario (BinaryTree).
Salida: Devuelve una lista (LinkedList) con los elementos del árbol en
post-orden. Devuelve None si el árbol está vacío.
traverseInPreOrder(BinaryTree)
---------------------
Descripción: Recorre un árbol binario en pre-orden.
Entrada: El árbol binario (BinaryTree).
Salida: Devuelve una lista (LinkedList) con los elementos del árbol en
pre-orden. Devuelve None si el árbol está vacío.
traverseBreadthFirst(BinaryTree)
-----------------------
Descripción: Recorre un árbol binario en modo primero anchura/amplitud.
Entrada: El árbol binario (BinaryTree).
Salida: Devuelve una lista (LinkedList) con los elementos del árbol
ordenados de acuerdo al modo primero en amplitud. Devuelve None si el
árbol está vacío."""
"""A partir de una estructura BinaryTree definida como:
class BinaryTree:
root=None
Y una estructura BinaryTreeNode definida de la siguiente manera:
class BinaryTreeNode:
key=None
value=None
leftnode=None
rightnode=None
parent=None
EJERCICIO 1
Crear un módulo de nombre [Link] que implemente las siguientes
especificaciones de las
operaciones elementales para el TAD árbol binario.
search(B,element)
Descripción: Busca un elemento en el TAD árbol binario.
Entrada: el árbol binario B en el cual se quiere realizar la búsqueda
(BinaryTree) y el valor del elemento (element) a buscar.
Salida: Devuelve la key asociada a la primera instancia del elemento.
Devuelve None si el elemento no se encuentra.
insert(B,element,key)
Descripción: Inserta un elemento con una clave determinada del TAD
árbol binario.
Entrada: el árbol B sobre el cual se quiere realizar la inserción
(BinaryTree), el valor del elemento (element) a insertar y la clave
(key) con la que se lo quiere insertar.
Salida: Si pudo insertar con éxito devuelve la key donde se inserta el
elemento. En caso contrario devuelve None.
delete(B,element)
Descripción: Elimina un elemento del TAD árbol binario.
Poscondición: Se debe desvincular el Node a eliminar.
Entrada: el árbol binario B sobre el cual se quiere realizar la
eliminación (BinaryTree) y el valor del elemento (element) a eliminar.
Salida: Devuelve clave (key) del elemento a eliminar. Devuelve None si
el elemento a eliminar no se encuentra.
deleteKey(B,key)
Descripción: Elimina una clave del TAD árbol binario.
Poscondición: Se debe desvincular el Node a eliminar.
Entrada: el árbol binario B sobre el cual se quiere realizar la
eliminación (BinaryTree) y el valor de la clave (key) a eliminar.
Salida: Devuelve clave (key) a eliminar. Devuelve None si el elemento
a eliminar no se encuentra.
access(B,key)
Descripción: Permite acceder a un elemento del árbol binario con una
clave determinada.
Entrada: El árbol binario (BinaryTree) y la key del elemento al cual
se quiere acceder.
Salida: Devuelve el valor de un elemento con una key del árbol
binario, devuelve None si no existe elemento con dicha clave.
update(B,element,key)
Descripción: Permite cambiar el valor de un elemento del árbol binario
con una clave determinada.
Entrada: El árbol binario (BinaryTree) y la clave (key) sobre la cual
se quiere asignar el valor de element.
Salida: Devuelve None si no existe elemento para dicha clave. Caso
contrario devuelve la clave del nodo donde se hizo el update.
"""
from algo1 import *
class BinaryTree:
root = None
class BinaryTreeNode:
key = None
value = None
leftNode = None
rightNode = None
parent = None
def search(B, element):
"""Descripción: Busca un elemento en el TAD árbol binario.
Entrada: el árbol binario B en el cual se quiere realizar la búsqueda
(BinaryTree) y el valor del elemento (element) a buscar.
Salida: Devuelve la key asociada a la primera instancia del elemento.
Devuelve None si el elemento no se encuentra."""
return searchR([Link], element)
def searchR(node, element):
if node:
if [Link] == element:
return [Link]
else:
key = searchR([Link], element)
if key != None:
return key
else:
return searchR([Link], element)
"""# otra forma es la siguiente
def search(B, element):
if [Link] == None:
return None
else:
return searchR([Link], element)
def searchR(node, element):
if [Link] == element:
return [Link]
def searchR(currentNode, element):
if [Link] == element:
return [Link]
else:
if [Link] != None:
key = searchR([Link], element)
if key != None:
return key
if [Link] != None:
key = searchR([Link], element)
if key != None:
return key
"""
def insert(B,element,key): # defino una funcion wrapper (envoltorio)
"""Descripción: Inserta un elemento con una clave determinada del TAD
árbol binario.
Entrada: el árbol B sobre el cual se quiere realizar la inserción
(BinaryTree), el valor del elemento (element) a insertar y la clave
(key) con la que se lo quiere insertar.
Salida: Si pudo insertar con éxito devuelve la key donde se inserta el
elemento. En caso contrario devuelve None."""
newNode = BinaryTreeNode()
[Link] = key
[Link] = element
if [Link] == None:
[Link] = newNode
return [Link]
else:
return insertR(newNode, [Link])
def insertR(newNode, currentNode): # defino una funcion insert Recursiva
if [Link] > [Link]:
if [Link] == None:
[Link] = currentNode
[Link] = newNode
return [Link]
else:
return insertR(newNode, [Link])
else:
if [Link] == None:
[Link] = currentNode
[Link] = newNode
return [Link]
else:
return insertR(newNode, [Link])
def delete(B, element):
""" Descripción: Elimina un elemento del TAD árbol binario.
Poscondición: Se debe desvincular el Node a eliminar.
Entrada: el árbol binario B sobre el cual se quiere realizar la
eliminación (BinaryTree) y el valor del elemento (element) a eliminar.
Salida: Devuelve clave (key) del elemento a eliminar. Devuelve None si
el elemento a eliminar no se encuentra."""
"""def delete(B, element):
node = findNodeByElement([Link], element)
if node is None:
return None
key = [Link]
deleteNode(B, node)
return key
def findNodeByElement(currentNode, element):
if currentNode is None:
return None
if [Link] == element:
return currentNode
node = findNodeByElement([Link], element)
if node is not None:
return node
return findNodeByElement([Link], element)"""
def transplant(B, u, v):
if [Link] is None:
[Link] = v
elif u == [Link]:
[Link] = v
else:
[Link] = v
if v is not None:
[Link] = [Link]
def minimum(node):
while [Link] is not None:
node = [Link]
return node
def deleteNode(B, node):
if [Link] is None:
transplant(B, node, [Link])
elif [Link] is None:
transplant(B, node, [Link])
else: # luego, el nodo a eliminar tiene dos hijos
successor = minimum([Link]) # el nodo a poner en el lugar del
eliminado es el menor de los mayores
if [Link] != node:
transplant(B, successor, [Link])
[Link] = [Link]
if [Link] is not None:
[Link] = successor
transplant(B, node, successor)
[Link] = [Link]
if [Link] is not None:
[Link] = successor
def deleteR(B, currentNode, key):
if currentNode != None:
if [Link] == key:
deleteNode(B, currentNode)
return currentNode
node = deleteR(B, [Link], key)
if node != None:
return node
return deleteR(B, [Link], key)
def delete(B, key):
if [Link] != None:
node = deleteR(B, [Link], key)
if node != None:
return [Link]
def deleteKey(B, key):
"""Descripción: Elimina una clave del TAD árbol binario.
Poscondición: Se debe desvincular el Node a eliminar.
Entrada: el árbol binario B sobre el cual se quiere realizar la
eliminación (BinaryTree) y el valor de la clave (key) a eliminar.
Salida: Devuelve clave (key) a eliminar. Devuelve None si el elemento
a eliminar no se encuentra."""
node = findNodeByKey([Link], key)
if node:
return deleteNode(B, node)
def findNodeByKey(currentNode, key):
if currentNode:
if [Link] == key:
return currentNode
node = findNodeByKey([Link], key)
if node:
return node
return findNodeByKey([Link], key)
def access(B, key):
"""Descripción: Permite acceder a un elemento del árbol binario con una
clave determinada.
Entrada: El árbol binario (BinaryTree) y la key del elemento al cual
se quiere acceder.
Salida: Devuelve el valor de un elemento con una key del árbol binario,
devuelve None si no existe elemento con dicha clave."""
node = accessR([Link], key)
if node == None: return
else: return [Link]
def accessR(currentNode, key):
if currentNode == None: return
else:
if [Link] == key:
return currentNode
else:
node = accessR([Link], key)
if node == None:
node = accessR([Link], key)
return node
def updateR(node, element, key):
if node: # if node is trully
if [Link] == key:
[Link] = element
return node
else:
aux_node = updateR([Link], element, key)
if aux_node:
return aux_node
else:
return updateR([Link], element, key)
def update(B, element, key):
"""Descripción: Permite cambiar el valor de un elemento del árbol binario
con una clave determinada.
Entrada: El árbol binario (BinaryTree) y la clave (key) sobre la cual
se quiere asignar el valor de element.
Salida: Devuelve None si no existe elemento para dicha clave. Caso
contrario devuelve la clave del nodo donde se hizo el update."""
node = updateR([Link], element, key)
if node:
return key
"""def update(B, element, key):
node = updateR([Link], element, key)
if node is None: return
else: return [Link]
def updateR(currentNode, element, key):
if currentNode == None: return
else:
if [Link] == key:
[Link] = element
return currentNode
else:
node = updateR([Link], element, key)
if node == None:
node = updateR([Link], element, key)
return node"""
arb = BinaryTree()
insert(arb,44,4)
insert(arb,77,8)
insert(arb,22,2)
print([Link])
print("search(arb,88):",search(arb,88))
print("access(arb, 8):",access(arb, 8))
print("update(arb, 77, 8):",update(arb, 88, 8))
print("search(arb,88):",search(arb,88))
print("search(arb,77):",search(arb,77))
print("access(arb, 8):",access(arb, 8))
print("delete(arb, 8):",delete(arb, 8))
print("access(arb, 8):",access(arb, 8))
"""EJERCICIO 2
Implementar las siguientes especificaciones de las operaciones para recorrer un
TAD árbol
binario. Incluir las implementaciones en el modulo [Link]
traverseInOrder(B)
Descripción: Recorre un árbol binario en orden
Entrada: El árbol binario (BinaryTree)
Salida: Devuelve una lista (LinkedList) con los elementos del árbol en
orden. Devuelve None si el árbol está vacío.
traverseInPostOrder(B)
Descripción: Recorre un árbol binario en post-orden
Entrada: El árbol binario (BinaryTree)
Salida: Devuelve una lista (LinkedList) con los elementos del árbol en
post-orden. Devuelve None si el árbol está vacío.
traverseInPreOrder(B)
Descripción: Recorre un árbol binario en pre-orden
Entrada: El árbol binario (BinaryTree)
Salida: Devuelve una lista (LinkedList) con los elementos del árbol en
pre-orden. Devuelve None si el árbol está vacío.
traverseBreadthFirst(B)
Descripción: Recorre un árbol binario en modo primero anchura/amplitud
Entrada: El árbol binario (BinaryTree)
Salida: Devuelve una lista (LinkedList) con los elementos del árbol
ordenados de acuerdo al modo primero en amplitud. Devuelve None si el
árbol está vacío.
A tener en cuenta:
1. Cada operación básica debe ser implementada como una función.
Ejemplo:
def insert(B,key,element):
Aca va el código que implementa la operación insert
2. Las operaciones deben respetar la especificación propuesta. Es decir sólo
incluir los
parámetros mencionados en la definición de la operación.
3. Usar lápiz y papel primero.
4. No se puede utilizar otra biblioteca/módulo que los desarrollados en clase:
a. [Link]
b. [Link]
c. [Link]
d. queue, stack
e. etc"""
from linkedlist import LinkedList, add, revert
def traverseInOrder(B):
""" Descripción: Recorre un árbol binario en orden
Entrada: El árbol binario (BinaryTree)
Salida: Devuelve una lista (LinkedList) con los elementos del árbol en
orden. Devuelve None si el árbol está vacío."""
List = LinkedList()
traverseInOrderR([Link], List)
return revert(List)
def traverseInOrderR(currentNode, List):
if currentNode == None:
return None
else:
traverseInOrderR([Link], List)
add(List, [Link])
traverseInOrderR([Link], List)
def traverseInPostOrder(B):
"""Descripción: Recorre un árbol binario en post-orden
Entrada: El árbol binario (BinaryTree)
Salida: Devuelve una lista (LinkedList) con los elementos del árbol en
post-orden. Devuelve None si el árbol está vacío."""
List = LinkedList()
traverseInPostOrderR([Link], List)
return revert(List)
def traverseInPostOrderR(currentNode, List):
if currentNode != None:
traverseInPostOrderR([Link], List)
traverseInPostOrderR([Link], List)
add(List, [Link])
def traverseInPreOrder(B):
"""Descripción: Recorre un árbol binario en pre-orden
Entrada: El árbol binario (BinaryTree)
Salida: Devuelve una lista (LinkedList) con los elementos del árbol en
pre-orden. Devuelve None si el árbol está vacío."""
if [Link]:
List = LinkedList()
traverseInPreOrderR([Link], List)
return revert(List)
def traverseInPreOrderR(currentNode, List):
if currentNode:
add(List, [Link])
traverseInPreOrderR([Link], List)
traverseInPreOrderR([Link], List)
from myqueue import enqueue, dequeue
def traverseBreadthFirst(B):
"""Descripción: Recorre un árbol binario en modo primero anchura/amplitud
Entrada: El árbol binario (BinaryTree)
Salida: Devuelve una lista (LinkedList) con los elementos del árbol
ordenados de acuerdo al modo primero en amplitud. Devuelve None si el
árbol está vacío."""
if [Link] is None:
return None
# Cola auxiliar para recorrer el árbol por niveles
queue = LinkedList()
enqueue(queue, [Link])
# Lista resultado donde almacenaremos los valores por nivel
result = LinkedList()
# Bucle principal: procesamos cada nodo y encolamos sus hijos
while [Link] is not None:
node = dequeue(queue)
add(result, [Link])
if [Link] is not None:
enqueue(queue, [Link])
if [Link] is not None:
enqueue(queue, [Link])
return revert(result)