Caso de uso de arboles binarios

http://repositorio.upct.es/bitstream/handle/10317/2745/pfc4277.pdf?sequence=1

Introducción

Vamos a hablar primero un poco de que son los arboles binarios; “Un árbol binario es un grafo conexo, a cíclico y no dirigido tal que el grado de cada vértice no es mayor a 3”, eso significa que tenemos un grafo donde cada nodo puede tener máximo 2 hijos u hojas  y estas hojas no pueden tener como hijos a cualquier otra hoja anterior como podemos ver en la figura que se relaciona a continuación:

¿Para que sirve un árbol binario?

Como todos sabemos un árbol binario es una estructura de datos, y como todas, este sirve para organizar datos para facilitar su manipulación, ya sea el ingreso, borrado o búsqueda de datos, y precisamente una de las principales ventajas de los árboles binarios es la búsqueda, ya que como en muchos algoritmos de búsqueda necesitamos tener la información ordenada y en nuestros árboles binarios precisamente los datos van ingresando de forma ordenada. Recorridos con los conocidos métodos recursivos:

1. Inorden
2. Postorden
3. Preorden

 
                            Caso de estudio

  Creación de una interfaz gráfica para la gestión de un árbol genealógico.

Introducción

Un árbol genealógico es un árbol que presenta la herencia biológica de una persona, comenzando con sus padres y retrocediendo a través de las generaciones, pasando por sus abuelos, bisabuelos, etc. La diferencia entre un árbol genealógico teórico y un árbol genealógico real es que el árbol real puede no estar perfectamente equilibrado, debido a la falta de datos o a la existencia de datos incompletos. En lo que respecta a este caso de estudio, se va a crear una interfaz gráfica para la gestión de un árbol genealógico que permitirá al usuario seleccionar un padre y luego ir introduciendo los hijos de cualquiera de los padres existentes en el programa. A su vez también se podrá eliminar cualquier nodo. El programa también permite guardar los datos introducidos en un documento de texto, imprimir el árbol guardado y salir del sistema.

Diseño inicial

El programa está formado por cuatro componentes: la clase árbol, la clase hoja, la clase test y la interfaz gráfica de usuario (GUI).

En un principio el programa se ejecutaba a través de la clase test (donde se encuentra el método main). Por lo que por consola se mostraba un pequeño menú con cuatro opciones: añadir, eliminar, guardar, imprimir y salir.

Si se escribe la opción añadir se pedirá el nombre del hijo que se quiere añadir y el nombre del padre al que se quiere añadir ese nuevo hijo. Si el nombre del padre es igual a “null”, es que este hijo va a ser un nuevo nodo raíz y si no se irá comparando el nombre del padre introducido por teclado con todos los nombres de los nodos que haya en el documento de texto guardado “read.txt” y cuando lo encuentre se insertara el nuevo hijo a ese padre. Abajo se muestra el método para que se pueda entender mejor:

public Leaf addNewChild(String childName, String parentName, Leaf
rootNode){

//se da el número de hijos de ese nodo

         for(int i=0; i<rootNode.getChildren().size(); i++){

// se recorren todos los hijos de esa hoja y en el nodo en el que este en ese momento será el padre.
     
   Leaf parentNode = rootNode.getChildren().get(i);

// se comparan los nombres
      
       if(parentNode.getName().equals(parentName)){

// si es el nombre que el programa está buscando, inserta el nodo

parentNode.insertChild(new Leaf(childName,parentNode));

//se encuentra un nodo con el mismo nombre que el usuario ha introducido

control = true;

//en el caso de que el usuario ponga más de un nodo con el mismo nombre, el programa solo añade el hijo en el primer nodo. Otra posibilidad es quitar el "break" y el programa añade el nuevo hijo a todos los padres con el mismo nombre.//

break;}

//cierro if si el nodo tiene hijos, el programa llama al método recursivo

 if (parentNode.getChildren().size() != 0){
      addNewChild(childName, parentName, parentNode);}
}

//cierro for

         return rootNode;}


//cierro método addNewChild

Si la opción es eliminar el programa pedirá el nombre del nodo a eliminar y se irá comparando con cada uno de los hijos del árbol .Si corresponde con uno de los nodos guardados en el documento de texto se eliminara dicho nodo introducido. Abajo se muestra el método para su mejor compresión:

//metodo que elimina el nombre de nodo que se le pasa

public void removeChild(String Node, Leaf rootNode){

//se da el número de hijos de este subárbol


for(int i=0; i<rootNode.getChildren().size(); i++){


//se recorre uno a uno los nodos del árbol

Leaf parentNode = rootNode.getChildren().get(i);

// se comparan los nombres

if(parentNode.getName().equals(Node)){

// si es el nombre que el programa está buscando,elimina el nodo

rootNode.getChildren().remove(i);

// se encuentra un nodo con el mismo nombre que el usuario ha introducido

control = true; break; }

//llamada al método recursivo

removeChild(Node,parentNode); }

//cierra for
}

//cierra removeChild()

Si la opción es guardar se almacenara en un documento de texto ese nuevo padre e hijo introducido anteriormente en la opción añadir o si se ha eliminado algún nodo también se modificara el documento de texto “read.txt”.

se muestra un ejemplo de lo que almacena el archivo “read.txt”:

Si la opción es imprimir se mostrara por consola el documento de texto donde se guardan los datos que se introducen por teclado pero en forma de árbol. El archivo que lo muestra así es el “out.txt”.

+

A continuación se muestra un ejemplo de lo que almacena el archivo “out.txt”:

Implementación de la interfaz grafica 

Para diseñar la interfaz grafica que visualice de la forma más clara y sencilla el árbol genealógico se crea una ventana principal donde hay un área de texto donde se mostrara el árbol y unos botones que serán añadir, eliminar y salir. En la Figura se muestra como quedaría dicha interfaz.

Si se pulsa el botón añadir se abrirá una nueva ventana donde se podrá introducir el nombre del hijo y se mostrara un desplegable con todos los nodos almacenados en el archivo “read.txt” para poder seleccionar el padre al que se quiere añadir ese hijo.

Cuando se pulse el botón “Add” estos datos serán guardados en un documento de texto y a su vez el árbol se imprimirá en el área de texto de la ventana principal en forma de árbol.

Si el botón seleccionado es eliminar se abrirá una nueva ventana donde se volverá a mostrar un desplegable con todos los nodos almacenados en el archivo “read.txt”. Entonces se elegirá el nodo a eliminar.

Cuando se pulse el botón “Clear” el nodo seleccionado se eliminara, se guardara dicho cambio y el árbol será mostrado en la ventana principal de nuevo.

Al pulsar el botón de salir se abrirá una nueva ventana con un pequeño menú donde se le preguntara al usuario si está seguro de querer salir del programa. Si se pulsa que “Si” el programa se cerrara y si es que “No” el programa permanecerá abierto.