1er Aporte Creacion de un Arbol de Busqueda en Python

Hola a todos por aquí..

Esta es mi primera aportación al blog, es un articulo que escribí hace ya algún tiempo en el sitio http://www.linuxsc.net y es sobre la manera en como construir un árbol de búsqueda con ciertas características especiales y que me hacia falta para terminar el programa que estaba escribiendo en ese entonces….

El problema:

Debía construir un árbol de búsqueda con ciertas características que no se apegan a los códigos que encontré en el internet ( solo hay códigos de arboles B, B+, Balanceados) lo cual no me servía, lo que necesitaba es un árbol al cual le pudiera ingresar nodos no importando la posición, siempre y cuando tuvieran un padre, además el dato almacenado en los nodos no importa.

Se podría tener un árbol con la siguiente descripción por ejemplo:


Fijándonos un poco en el valor de los nodos nos damos cuenta de que no esta ordenado, ni tampoco balanceado, se necesita que pueda ingresar cualquier valor en cualquier momento, siempre y cuando tenga padre y también espacio ya sea a la derecha o a la izquierda

Así que este es el resultado del código….

#===============================================================
# Arbol.py
# Programa para la creación de arboles que no forzosamente tienen
# que estar balanceados, además que no forzosamente deben comenzar las
# inserciones de nodos por la raíz
#
# Autor: Faustino Vasquez limon
#
#================================================================

class Arbol:
def __init__(self,valor):
self.valor = valor
self.izquierda = None
self.derecha = None

#Metodo para agregar nodos a la izquierda del arbol, no importando que nodo
#del arbol queremos como padre de este
def AgregaIzquierda(self,padre,dato):
if self.valor != padre:
if self.izquierda != None:
self.izquierda.AgregaIzquierda(padre,dato)
if self.derecha!=None:
self.derecha.AgregaIzquierda(padre,dato)
else:
self.izquierda=Arbol(dato)

#Metodo para agregar nodos a la derecha, no importando que nodo del arbol
#queremos como padre de este
def AgregaDerecha(self,padre,dato):
if self.valor != padre:
if self.izquierda != None:
self.izquierda.AgregaDerecha(padre,dato)
if self.derecha!=None:
self.derecha.AgregaDerecha(padre,dato)
else:
self.derecha = Arbol(dato)

#Metodo que nos permite buscar un elemento en forma recursiva
def BuscaNodo(self,dato):
if self.valor != dato:
if self.izquierda!=None:
return self.izquierda.BuscaNodo(dato)
if self.derecha!=None:
return self.derecha.BuscaNodo(dato)
else:
return self.valor

#Metodo para impresion del arbol comenzando Primero Izquierda usando #recursividad
def ImprimeArbolIzq(self):
if self.valor!=None:
print self.valor
if self.izquierda!=None:
self.izquierda.ImprimeArbolIzq()
if self.derecha!=None:
self.derecha.ImprimeArbolIzq()

#Metodo para impresion del arbol comenzando primero por la derecha usando #recursividad
def ImprimeArbolDer(self):
if self.valor!=None:
print self.valor
if self.derecha!=None:
self.derecha.ImprimeArbolDer()
if self.izquierda!=None:
self.izquierda.ImprimeArbolDer()

# …………………….. 9
# ………………..23……61
# …………..64………………81
# ……….7…….44….. 26
# ………………………………55
# Crearemos la anterior estructura de en la forma primero izquierda y luego
# derecha es decir que antes de crear un nodo derecho para la raíz
# tendremos que
crear un nodo derecho para el 64, de hecho se puede
# ingresar un nodo en cualquier
momento la única condición es que
# exista un padre para este nuevo nodo


arbol= Arbol(9)

# AgregaIzquierda(padre,dato)

arbol.AgregaIzquierda(9,23)
arbol.AgregaIzquierda(23,64)
arbol.AgregaIzquierda(64,7)
arbol.AgregaDerecha(64,44)
arbol.AgregaDerecha(9,61)
arbol.AgregaDerecha(61,81)
arbol.AgregaIzquierda(81,26)
arbol.AgregaDerecha(26,55)

print
print ‘Impresion del arbol comenzando por la izquierda’
arbol.ImprimeArbolIzq()
print
print
print ‘Impresion del arbol comenzando por la derecha’
arbol.ImprimeArbolDer()
print
print
print ‘Buscando un valor’
valor = arbol.BuscaNodo(7)
print valor
print


Esperando como siempre que esto le sirva a alguien

Atte: Faustino Vasquez Limon

Fuente

http://linuxsc.net/index.php/the-prog/480-creacion-de-un-arbol-de-busqueda-en-python

Creado por el mismo autor…


Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: