Home UC3M
Home IT
Home / Docencia / I. Tec. Telecom. (esp. Sis. Telecomunicación) / Programación de Sistemas / Práctica 6
anteriorsiguiente

Práctica 6

Fecha: 25 abril 2006
Conceptos: Árboles binarios
Profesores: Raquel M. Crespo García, José Jesús García Rueda, José María Rubio Manso Daniel Díaz Sánchez

 INTRODUCCIÓN

En esta práctica se trabajará con árboles binarios en Java, prestando especial atención a cómo recorrerlos (preorden, postorden, enorden).

  EJERCICIO 1: Implementación de un árbol binario

  • Concepto de árbol binario

En este ejercicio se utilizará la definición recursiva de árbol para diseñar una clase Java que implemente un árbol binario: Un árbol binario es o bien vacío o consta de una raíz y dos árboles hijo (izquierdo y derecho).

Apartado 1

Crea la clase BTree.java basándote en la definición recursiva anterior. Programa un constructor que reciba como parámetro el elemento (de la clase Object) de la raíz. Programa los métodos getElemento, getIzquierda y getDerecha.

Apartado 2

Programa la excepción BTreeException, con un constructor que reciba un mensaje, de tipo String.

Apartado 3

Programa, en la clase BTree, un método que permita insertar un subárbol en el árbol, siguiendo la siguiente declaración:

public void insertar(BTree tree, int lado) 
      throws BTreeException;

El parámetro tree es el subárbol que debe ser insertado, y el parámetro lado indica en cuál de los dos lados (declara, en la clase BTree, los atributos LADO_IZDO y LADO_DRCHO necesarios). Si se introduce un lado incorrecto, o hay un subárbol no vacío en el lado indicado, debe lanzar la excepción BTreeException.

 EJERCICIO 2: Recorrido de árboles binarios.

  • Árboles binarios.
  • Recorrido de árboles binarios: pre-orden, post-orden y en-orden

En este ejercicio se dotará a la clase BTree del ejercicio anterior de tres métodos que permitan recorrer, de forma recursiva, el árbol.

Apartado 1

Programa el método imprimePreOrden que recorra el árbol en pre-orden, imprimiendo en pantalla el elemento contenido en cada nodo.

Apartado 2

Programa el método imprimePostOrden que recorra el árbol en post-orden, imprimiendo en pantalla el elemento contenido en cada nodo.

Apartado 3

Programa el método imprimeEnOrden que recorra el árbol en en-orden, imprimiendo en pantalla el elemento contenido en cada nodo.

 EJERCICIO 3: Utilización de la clase BTree

  • Árboles binarios

En este ejercicio debes utilizar la clase BTree programada en los ejercicios anteriores. Para ello, debes programar la clase Trabalenguas, que en su método main cree un árbol con la siguiente estructura:

               Tres
                |
       --------------------
       |                  |
    tristes             tigres
       |
  ------------
  |          | 	
  |          | 	
comían     trigo

Apartado 1

Imprime el árbol anterior, utilizando los métodos programados en el ejercicio anterior. Comprueba que el orden en que aparecen los elementos en pantalla sea el correcto.

Apartado 2

Haz los cambios que necesites, en la estructura del árbol, para que, imprimiendo en pre-orden, aparezca en pantalla "Tres tristes tigres comían trigo".

 EJERCICIO 4: Extracción de subárboles

  • Árboles binarios

La clase BTree que has implementado no permite eliminar nodos del árbol tras ser añadidos a éste. En este ejercicio debes programar el método BTree extraer(int lado), que devuelve al subárbol del lado indicado y lo extrae del árbol (esto es, pone a null la referencia al subárbol). Añade código a la clase Trabalenguas para probar este método.

  SOLUCIONES

Solución: prac06-sol.zip


Última actualización:

Localización | Personal | Docencia | Investigación | Novedades | Intranet
inicio | mapa del web | contacta