Estructuras de Datos I - Árbol Binario de Búsqueda Implementación Ligada

Vista previa del material en texto

Árbol Binario de Búsqueda
Implementación Ligada
1
Nodo del Árbol
G
D
A
L
I
S
Función: inicializa()
Recibe: raíz
Regresa: nada
Raíz == NULO
Función: vacío()
Recibe: raíz
Regresa: booleano
¿Raíz == NULO?
	Si: Regresar verdadero
	No: Regresar falso
Función: vacío()
Recibe: raíz
Regresa: booleano
¿Raíz == NULO?
	Si: Regresar verdadero
	No: Regresar falso
Función: recupera()
Recibe: raíz, posi
Regresa: elemento
¿Raíz == NULO o posi == NULO?
	Si: ¡Excepción!
		Insuficiencia de datos
		Terminar
	No: regresar posielemento
Función: inserta()
Recibe: raíz, elemento
Regresa: nada
¿Raíz == NULO?
	Si: aux = nuevo nodo
		auxele = ele
		raíz = aux
	No: ¿elemento < raízele?
			Si: insertar(raízizq, elemento)
			No: insertar(raízdere, elemento)
Función: localiza()
Recibe: raíz, elemento
Regresa: posición
¿Raíz == NULO?
	Si: devolver NULO
		Terminar
	No: ¿elemento == raízele?
			Si: devolver raíz
			No: ¿elemento < raízele?
					Si: localiza(raízizq, elemento)
					No: localiza(raízdere, elemento)
Función: menor()
Recibe: raíz
Regresa: posición
¿Raíz == NULO?
	Si: devolver NULO
		Terminar
	No: ¿raízizq == NULO?
			Si: devolver raíz
			No: devolver menor(raízizq)
Función: mayor()
Recibe: raíz
Regresa: posición
¿Raíz == NULO?
	Si: devolver NULO
		Terminar
	No: ¿raízdere == NULO?
			Si: devolver raíz
			No: devolver mayor(raízdere)
Función: es_hoja()
Recibe: raíz
Regresa: booleano
¿Raíz == NULO?
	Si: devolver FALSO
¿raízizq == NULO Y raízdere == NULO?
	Si: devolver VERDADERO
	No: devolver FALSO
¡MUCHO OJO!
Los recorridos no necesariamente deben imprimir el árbol, se pueden realizar diferentes procesos dentro del recorrido.
Función: recorrido_preorder()
Recibe: raíz
Regresa: nada
¿Raíz == NULO?
	Si: terminar
Imprimir raízelemento /// Aquí es el proceso
Recorrido_preorder(raízizq)
Recorrido_preorder(raízdere)
Función: recorrido_inorder()
Recibe: raíz
Regresa: nada
¿Raíz == NULO?
	Si: terminar
Recorrido_inorder(raízizq)
Imprimir raízelemento /// Aquí es el proceso
Recorrido_inorder(raízdere)
Función: recorrido_postorder()
Recibe: raíz
Regresa: nada
¿Raíz == NULO?
	Si: terminar
Recorrido_postorder(raízizq) Recorrido_postorder(raízdere)
Imprimir raízelemento /// Aquí es el proceso
Función: altura()
Recibe: raíz
Regresa: entero
¿Raíz == NULO?
	Si: devolver 0
	No: alt_izq = altura(raízizq)
		 alt_dere = altura(raízdere)
		¿alt_izq > alt_dere?
			Si: devolver alt_izq + 1
			No: devolver alt_dere + 1
Función: elimina()
Recibe: raíz, posición
Regresa: nada
¿Raíz == NULO?
	Si: Insuficiencia de datos
		Terminar
	No: ¿es_hoja(raíz)?
		Si: liberar raíz
			raíz = NULO
		No: ¿raízizq != NULO?
				Si: pos_reemplazo = mayor(raízizq)
				No: pos_reemplazo = menor(raízdere)
			raízelemento = pos_reemplazoelemento
			elimina(raíz, pos_reemplazo)
Bienvenidos a:
Árboles Binarios de Búsquedas
Fuentes
Experiencia Laboral
Joyanes L. (2006). Programación en C++. Algoritmos, Estructuras de Datos y Objetos. España. Mcgraw-hill / Interamericana De España
Silvia Guardati Buemo (2007). Estructura de datos orientada a objetos: Algoritmos con C++ Pearson
20