Tarea #7 [solución]

Ordenamiento arboleado de una lista

      Para esta tarea programada usted debe enviarme estos archivos:

1. List.java
2. UseList.java
3. CARNET.docx
4. CARNET.html
5. CARNET.url

Para resolver esta tarea ustede debe usar como base la clase lista vista en el curso obtener estas 3 clases. Primero escriba un método que tome los nodos de la lista y los reacomode para formar un árbol binario ordenado, en el que se cumpla siempre que en cada nodo los valores a la izquierda son menores o iguales al nodo y los de la derecha mayores o iguales. Una vez que haya reacomodado los nodos de la lista para que formen un árbol binario, recórrale en inorden para obtener la lista ordenada. Note que nunca hace falta copie o elimine valores, pues todo el trabajo se hace cambiando los enlaces entre nodos. Si lo desea, use recursividad.

Consulta:

Profe: Según entiendo la tarea, lo que tenemos que hacer es utilizar los métodos públicos de la clase List.java para producir el árbol binario a partir de la lista.

Respuesta:

Sí hay que usar los nodos de la lista para crear un árbol. Lo que pasa es que eso no se puede hacer con ningún método público de la lista, porque lo nodos son privados, por lo que no están disponibles desde ningún método público.. Por eso, tenés que agregarle uno o varios métodos a la lista para transaformar primero la lista en un árbol binario ordenado, y luego transformar el árbol binario ordenado en una lista.
    http://www.di-mare.com/adolfo/p/Rep.htm

    Tenés que implementar un método que tome cada uno de los nodos de la lista, lo desconecte y luego lo agregue al árbol binario local. En pseudo código es algo parecido a lo siguiente:

private void list2tree() {
    // this es la lista a la que le sacamos los nodos
    List miArbol = new List(); // este es el árbol binario de nodos
    if ( !miArbol.empty() } { /* siempre nace vacío */ }

    while ( ! this.empty() ) { // quedan nodos
        Node elSacado = this.sacaNodo(); // saca el primer nodo
        miArbol.insertNode( elSacado );
        // http://google.com/search?as_qdr=all&&num=100&&as_q=java+binary+insert+tree
    }
    if ( this.empty() } { /* IMPOSIBLE */ }

// Ahora hay que sacar en orden los nodos de miArbol
// Cada nodo sacado debe se agregado al fina de this
// - http://google.com/search?as_qdr=all&&num=100&&as_q=java+binary+delete+tree
// - Node otroSacado = miArbol.deleteNode( elSacado );
// - deleteNode() es la parte más dura de la tarea
}

Consulta:

Profe: Luego con el árbol binario obtenido a partir de la lista, seguimos la misma dinámica pero esta vez para obtener la lista ordenada; ¿cierto? Nota: Favor corregirme si entendí mal: el árbol binario va a ser la misma lista inicial, ya que solamente vamos a modificar sus enlaces.

Respuesta:

Así es. A partir de la lista obtenés el árbol binario ordenado. Luego usás el recorrido inOrder() [IPD] para quitarle los nodos en orden ascendente. Cada uno de esos nodos debe ser agregado al final de la lista, de manera que la lista (this) queda totalmente ordenada.
    http://google.com/search?as_qdr=all&&num=100&&as_q=java+inOrder+tree

Consulta:

Profe: Me metí a la red para ver cómo están implementados los métodos para eliminar un nodo de un árbol binario ordenado (BST: Binary Search Tree), pero veo que hay mucho problema cuando uno tiene que eliminar un nodo que tiene 2 hijos. Por eso, ¿me permite no usar ese mismo nodo sino que agrego con List.add() el valor del nodo? De lo contrario la lógica del programa requiere que uno tenga acceso al nodo padre, pero en el el nodo solo hay referencia a los hijos y no al padre.

Respuesta:

Es cierto que es un poco más complicado eliminar un nodo que tiene 2 hijos. Sin embargo, al recorrer el árbol tenés que usar IPD, por lo que cuando llegués a un nodo que tengás que eliminar es porque ya le quitaste todos los hijos izquierdos: todos esos ya estarán enlazados en la lista, por lo que nunca tendrás que eliminar un nodo que tenga 2 hijos lo que, en consecuencia, simplifica la lógica de borrado.

    Para resolver el problema de la referencia al padre, lo que podés hacer es retornar en deleteNode() la referencia al hijo derecho del nodo que queda, si lo hubiera, o (null) si no existe el hijo derecho. De esta forma, al retornar a la invocación recursiva del padre, ese mismo padre tendrá la referencia que necesita para primero borrarse y luego terminar el recorrido IPD de sus descendientes derechos.

    De todas formas, si te queda más cómo podés usar List.add() para agregar el valor del nodo al final de la lista, sin eliminar el árbol, aunque es menos eficiente.

      Entregue su tarea por correo electrónico, como lo hizo anteriormente.

Entrega de Tareas

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2012
Derechos de autor reservados © 2012