UNIDAD III: ESTRUCTURAS NO LINEALES

Árboles

Definición

un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo  "a" es padre de un nodo "b" si existe un enlace desde "a" hasta "b" (en ese caso, también decimos que "b" es hijo de "a"). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Propiedades:

GRADO: Número de descendientes directos de un determinado nodo.

GRADO DE ÁRBOL: Es el máximo grado de todos los nodos del árbol.

NIVEL: Es el número de arcos que pueden ser recorridos para llegar a un determinado nodo.

Por definición Raíz tiene nivel = 1.

Dado el sig. árbol determine: Raíz, hijos, padres, hermanos, grado, nivel y altura del árbol.

Raíz = A

A= Padre de B y C.

B= Hijo de A, Hermano de C, Padre de D & E.

C= Hijo de A, Hermano de B, padre de E & F.

D= Hijo de B, Hermano de  E, no tiene Hijos, se le considera Hoja.

E= Hijo de B, Hermano de D, no tiene Hijos, se le considera Hoja.

F= Hijo de C, Hermano de G, no tiene Hijos, se le considera Hoja.

Nivel de árbol:

El nodo A está en el nivel 1 sus descendientes directos están en el nivel 2 y así sucesivamente.
El nivel del árbol está dado por el nodo de máximo nivel.

Grado de nodo: es el número de nodos hijos que tiene dicho nodo
Ej. El nodo A tiene grado 2.
El nodo B tiene grado 2.
Nota: Los nodos sin hijos no tienen grado.

Grado de un árbol: Es el máximo de los grados de todos los nodos de un árbol.
Ej. El grado del árbol es 2.

Operaciones de árboles.

Las operaciones comunes en árboles son:

• Enumerar todos los elementos.
• Buscar un elemento.
• Dado un nodo, listar los hijos (si los hay).
• Borrar un elemento.
• Eliminar un subárbol (algunas veces llamada podar).
• Añadir un subárbol (algunas veces llamada injertar).
• Encontrar la raíz de cualquier nodo.

Longitud de camino interno:

Definición
Es la suma de longitudes de camino de todos los nodos del árbol.

h

LCI=Σni * i

i=1

i=nivel del árbol
h=altura
ni=número de nodos en el nivel i
Lci=número de nivel*número de nodos+número de nivel*número de nodos...
Ejemplo: (1*1+2*2+4*3+4*4=33)

Árbol extendido:

Aquel en el que el número de hijos de cada nodo es igual al grado del árbol, que no cumplir con esta característica se deben incorporar nodos especiales.

Nodos especiales:
Reemplazan las ramas vacías o nulas.

Longitud de camino Externo:
Es la suma de todos los nodos especiales.

Formula:

h+1

LCE=Σnei* i i=2




i=Nivel del árbol
h=altura
nei=número de nodos especiales

Árboles Binarios

Es un árbol ordenado en el cual cada nodo puede tener como máximo 2 subárboles.

>> Estructura homogénea, resultado de la concatenación de un elemento de tipo T, llamado Raíz, con 2 árboles disjuntos llamados Subárbol iquierdo y Subárbol derecho.

Árbol General - Árbol Binario

Nota: Éste no es un árbol Binario porque "B" tiene 3 hijos.

Pasos a seguir para convertir un Árbol General a Binario:

1. Enlazar los hijos de cada nodo en forma horizontal las raíces de los distintos arboles generales. 
2. Relacionar los hijos de cada nodo (los hermanos en forma horizontal).
3. Enlazar en forma vertical el nodo Padre con el hijo que se muestra mas a la izquierda . Además se debe eliminar el vinculo del padre con el resto de sus hijos.
4. Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda y así obtendrá un árbol binario correspondiente.

Bosques

Representa un conjunto normalmente ordenado de uno o más árboles.

Conversión a Árbol Binario:

1. Enlazar en forma horizontal las raíces de los distintos árboles generales.
2. Relacionar los hijos de cada nodo (los hermanos) en forma horizontal.
3. Enlazar en forma vertical el nodo padre con el hijo que se encuentra más a la izquierda. Además se debe eliminar el vínculo del padre con el resto de sus hijos.
4. Rotar el diagrama 45° grados aprox. hacia la izquierda y así obtendrá el árbol binario correspondiente.

Resultado:

Recorridos

Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

• Visite la raíz
• Atraviese el sub-árbol izquierdo  
• Atraviese el sub-árbol derecho

Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

• Atraviese el sub-árbol izquierdo
• Visite la raíz
• Atraviese el sub-árbol derecho

Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
Atraviese el sub-árbol izquierdo
Atraviese el sub-árbol derecho
Visite la raíz

Programa de árbol Binario en Java.

public class Arbol {
    class Nodo
    {
        int info;
        Nodo izq, der;
    }
    Nodo raiz;
    int cant;
    int altura;
    public Arbol() {
        raiz=null;
    }
    public void insertar (int info) {
        if (!existe(info)) {
            Nodo nuevo;
            nuevo = new Nodo ();
            nuevo.info = info;
            nuevo.izq = null;
              nuevo.der = null;
            if (raiz == null)
                raiz = nuevo;
            else {
                Nodo anterior = null, reco;
                reco = raiz;
                while (reco != null)  {
                    anterior = reco;
                    if (info < reco.info)
                        reco = reco.izq;
                    else
                        reco = reco.der;
                }
                if (info < anterior.info)
                    anterior.izq = nuevo;
                else
                    anterior.der = nuevo;
            }
        }
    }
    public boolean existe(int info) {
        Nodo reco=raiz;
        while (reco!=null) {
            if (info==reco.info)
                return true;
            else
                if (info>reco.info)
                    reco=reco.der;
                else
                    reco=reco.izq;
        }
        return false;
    }
    private void imprimirEntre (Nodo reco)  {
        if (reco != null)  {
            imprimirEntre (reco.izq);
            System.out.print(reco.info + " ");
            imprimirEntre (reco.der);
        }
    }
    public void imprimirEntre () {
        imprimirEntre (raiz);
        System.out.println();
    }

    private void cantidad(Nodo reco) {
        if (reco!=null) {
            cant++;
            cantidad(reco.izq);
            cantidad(reco.der);
        }
    }
    public int cantidad() {
        cant=0;
        cantidad(raiz);
        return cant;
    }
    private void cantidadNodosHoja(Nodo reco) {
        if (reco!=null) {
            if (reco.izq==null && reco.der==null)
                cant++;
            cantidadNodosHoja(reco.izq);
            cantidadNodosHoja(reco.der);
        }
    }
    public int cantidadNodosHoja() {
        cant=0;
        cantidadNodosHoja(raiz);
        return cant;
    }
    private void imprimirEntreConNivel (Nodo reco,int nivel)  {
        if (reco != null) {
            imprimirEntreConNivel (reco.izq,nivel+1);
            System.out.print(reco.info + " ("+nivel+") - ");
            imprimirEntreConNivel (reco.der,nivel+1);
        }
    }
    public void imprimirEntreConNivel () {
        imprimirEntreConNivel (raiz,1);
        System.out.println();
    }
    private void retornarAltura (Nodo reco,int nivel)    {
        if (reco != null) {
            retornarAltura (reco.izq,nivel+1);
            if (nivel>altura)
                altura=nivel;
            retornarAltura (reco.der,nivel+1);
        }
    }
    public  int retornarAltura () {
        altura=0;
        retornarAltura (raiz,1);
        return altura;
    }
    public void mayorValorl() {
        if (raiz!=null) {
            Nodo reco=raiz;
            while (reco.der!=null)
                reco=reco.der;
            System.out.println("Mayor valor del įrbol:"+reco.info);
        }
    }
    public void borrarMenor() {
        if (raiz!=null) {
            if (raiz.izq==null)
                raiz=raiz.der;
            else {
                Nodo atras=raiz;
                Nodo reco=raiz.izq;
                while (reco.izq!=null) {
                    atras=reco;
                    reco=reco.izq;
                }
                atras.izq=reco.der;
            }
        }
    }
    public static void main (String [] ar)
    {
        Arbol abo = new Arbol ();
        abo.insertar (100);
        abo.insertar (50);
        abo.insertar (25);
        abo.insertar (75);
        abo.insertar (150);
        System.out.println ("Impresion entreorden: ");
        abo.imprimirEntre ();
        System.out.println ("Cantidad de nodos del įrbol:"+abo.cantidad());
        System.out.println ("Cantidad de nodos hoja:"+abo.cantidadNodosHoja());
        System.out.println ("Impresion en entre orden junto al nivel del nodo.");
        abo.imprimirEntreConNivel();
        System.out.print ("Artura del arbol:");
        System.out.println(abo.retornarAltura());
        abo.mayorValorl();
        abo.borrarMenor();
        System.out.println("Luego de borrar el menor:");
        abo.imprimirEntre ();
    }
}