Conceptos De Arboles

Concepto De Arbol:

Un árbol es una estructura de datos ramificada (no lineal) que puede representarse como un conjunto denodos enlazados entre sí por medio de ramas.

Los árboles representan las estructuras no-lineales y dinámicas de datos más importantes en computación. Dinámicas, puesto que la estructura árbol puede cambiar durante la ejecución de un programa. No-lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.

Aplicaciones:

• Formulas Matematicas
• Circuitos Electricos 
• Arbol Genealogico

Propiediades: 

Se dice que  todos los nodos que son descendientes directps hijos de un mismo nodo padre, son hermanos.

• Hoja: Son todos nodos que no tiene ramificaciones hijos.  

• Grado: Numero  de descendientes directos de un determinado nodo. 

• Grado de Arbol: Es el maximo grado de todos los nodos del arbol.

• Nivel: es el numero  de areas  que pueden ser rrecorridas para llegar a un determinado nodo  por definicion raiz tiene  el nivel numero 1.

• Raiz: Padre de todos.  

Longitud De Camino Interno:   

Es la suma de longitud de camino de todos los nodos del arbol. Esta operacion solo se realiza con arboles binarios.

 

h

LCI=Σni * i

i=1

i=Nivel del árbol
h=Altura
ni=Número de nodos en el nivel i
Lci=Numero de nivel*número de nodos+número de nivel*número de nodos...
Ejemplo: Lci= (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 caracteristica 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.

Calcular la longitud de camino externo:

n+1

LCE=Σnei* i

                                                                               i=2



i=Nivel del árbol
h=Altura
nei= Numero de nodos especiales


 

 Arbol Binario:

Estructura homogenea, resultado de la concatenacion de un elemento de tipo T, llamado raiz, con dos arboles binarios disjustos, llamados sub arbol izquierdo y subarbol derecho. 

Ejemplo  De Codigo En Java De Arbol Binario:

Inserta, imprime(inorden, preorden, posorden), # de hojas del arbol .

public class NodoA { //CLASE NODO NodoA izq;
NodoA der;
String dato;
NodoA(String info)
{
izq=der=null;
dato=info; }  

public void InsertarA(NodoA elemento) {
if(elemento.dato.compareTo(dato)<0)
{
if(izq==null)
{
izq= elemento ; }
else
{
izq.InsertarA(elemento); }
}
else
{
if(elemento.dato.compareTo(dato)>0)
{
if(der==null)
{

der =elemento; }
else {

der.InsertarA(elemento); }
}

if(elemento.dato.compareTo(dato)==0) { }
}
}
}


package arbolito;


public class Arbol { // CLASE ARBOL

NodoA raiz; Arbol() //constructor de la clase Arbol
{

raiz=null; //crea un arbol vacio }

public boolean Vacio() // verifica si el arbol esta creado {


return (raiz==null); }



public void IngresaE(NodoA muuu) // ingresa dato tipo nodo {
if(raiz==null)
{


raiz=muuu; }
else
{


raiz.InsertarA(muuu); }
}

public String Inorden(NodoA root) // METODO RECURSIVO INORDEN
{


String mensaje="";

if(root==null) {


mensaje="n"; }
else
{


mensaje=mensaje+Inorden(root.izq);

mensaje=mensaje+root.dato;

mensaje=mensaje+Inorden(root.der); }


return mensaje; }


public void imprimirInorden() //METODO IMPRIMIR INORDEN {


System.out.println(Inorden(raiz)); }



public String PosOrden(NodoA subraiz) // METODO RECURSIVO POSORDEN {


String men="";


if(subraiz==null) {


men=" "; }
else
{


men=men +PosOrden(subraiz.izq);

men=men+PosOrden(subraiz.der)+"n";

men=men+subraiz.dato; }


return men; }


public void ImprimirPosOrden() // METODO IMPRIMIR POSORDEN {


System.out.println(PosOrden(raiz)); }


public String Preorden(NodoA raizz) // METODO RECURSIVO PREORDEN {


String messagge="";

if(raizz==null) {


messagge="n"; }
else
{


messagge=messagge+raizz.dato;

messagge=messagge+Preorden(raizz.izq);

messagge=messagge+Preorden(raizz.der); }


return messagge; }


public void ImprimirPreorden() // METODO IMPRIMIR PREORDEN {


System.out.println(Preorden(raiz)); }



public int Contar(NodoA Otraraiz) // CUENTA EL NUMERO DE HOJAS
{


int hojas=0;

if((Otraraiz.izq==null)&&(Otraraiz.der==null)) {


hojas++; }


else {


if(Otraraiz.izq!=null)

{

hojas=hojas+Contar(Otraraiz.izq);

}

if(Otraraiz.der!=null)

{

hojas=hojas+Contar(Otraraiz.der);

} }


return hojas; }


public void ImprimirHojas() // IMPRIME EL NUMERO DE HOJAS
{


System.out.println("numero de hojas: "+Contar(raiz)); }
// CUENTA ELEMENTOS MAYORES RECURSIVAMENTE


public int Contarmayores(NodoA Root,String valor)
{


int numero=0;

if(Root.dato.compareTo(valor)>0) {
numero++;


if(Root.izq!=null)

{

numero=numero+Contarmayores(Root.izq,valor);

}

if(Root.der!=null)

{

numero=numero+Contarmayores(Root.der,valor);

} }


else {


if(Root.izq!=null)

{

numero=numero+Contarmayores(Root.izq,valor);

}

if(Root.der!=null) {


numero=numero+Contarmayores(Root.der,valor);

} }


return numero; }


public void imprimirmayor(String valorr) {


System.out.println(Contarmayores(raiz,valorr)); }
}

CLASE MAIN

public static void main(String[] args) {
Arbol a= new Arbol();
a.IngresaE(new NodoA("a"));
a.IngresaE(new NodoA("l"));
a.IngresaE(new NodoA("m"));
a.IngresaE(new NodoA("p"));
a.IngresaE(new NodoA("t"));
a.IngresaE(new NodoA("z"));
a.IngresaE(new NodoA("g"));
System.out.println("Recorridos");
System.out.println("inorden");
a.imprimirInorden();


System.out.println("---------------");System.out.println("Posorden");
a.ImprimirPosOrden();


System.out.println("---------------");

System.out.println("Preorden");

a.ImprimirPreorden();

a.ImprimirHojas();

a.imprimirmayor("n"); 

}
}

Arboles Distintos:

 Dos arboles binarios son distintos cuando sus estructuras son diferentes.

Arboles Similares:

Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos difiere entre sí.

 

  Arboles Equivalentes:

Los árboles binarios equivalentes definen como aquellos que son similares y además los nodos contienen la misma información.

 Arbol General:

 Conversion De Un Arbol General A Un Arbol Binario: 

• Enlazar los hijos de cada nodo en forma horizontal (los hermanos).

• Relacionar en forma vertical el nodo padre con el hijo,  que se encuentra mas ala izquierda ademas, se debe eliminar el vinculo de ese padre con el resto de los hijos.

• Rotar el diagrama resultante aproximadamente   45 grados hacia la izquierda y asi obtendra un arbol binario correspondiente. 

Ejemplo:

Bosque:

 Representa un conjunto normalmente ordenado  de uno o mas arboles generales.

Conversion De Un Bosque A Arbol Binario:

• Enlazar en forma horizontal las raizes de los distintos arboles generales.
• Relacionar los hijos de cada  nodo (los hermanos) en forma horizontal.
• Enlazar en forma vertical el nodo padre con el hijo que se encuentra mas a la izquierda ademas se debe eliminar el vinculo del padre con el resto de sus hijos.
• rotar el diagrama  resultante  aproximadamente  45 grados hacia la izquierda y asi obtendra el arbol  binario correspondiente.

Ejemplo:

 

Recorridos De Un Arbol Binario:
 

Recorrer significa visitar los nodos del árbol en forma sistemática; de tal manera que todos los nodos sean visitados una sola vez. Las tres formas diferentes de efectuar el recorrido son: 

a)Recorrido en preorden

• Visitar la raíz.
• Recorrer el subárbol izquierdo.
• Recorrer el subárbol derecha.

b)Recorrido en inorden.

• Recorrer el subárbol izquierdo.
• Visitar la raíz.
• Recorrer el subárbol derecho.

c)Recorrido en posorden.

• Recorrer el subárbol izquierdo.
• Recorrer el subárbol derecho.
• Visitar la raíz.

Ejemplo:

Arbol Genealogico:

Un árbol genealógico es una representación gráfica que enlista los antepasados y los descendientes de un individuo en una forma organizada y sistemática, sea en forma de árbol o tabla. Puede ser ascendente, exponiendo los antepasados o ancestros de una persona, o descendente, exponiendo todos los descendientes.