UNIDAD III ARBOLES 

Concepto de árbol

un árbol es una estructura de datos ampliamente usada que emula 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 mas 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.

El árbol También se define como una estructura de datos no lineal. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenidos. Entre otros tenemos un tipo especial de de árbol que es, llamado árbol binario, que puede ser implementado fácilmente en la computadora.

Árboles Generales.
Un árbol general ( a veces es llamado árbol ) se define como un conjunto, finito no vació T de elementos, llamados nodos, tales que:
T contiene un elemento distinguido R, llamado raíz de T.

Los restantes elementos de T forman una colección ordenada de cero o mas árboles disjuntos T1, T2,.., Tm..

ÁRBOL BINARIO 

Es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

TIPOS DE ARBOLES BINARIOS 

Vamos a dar una lista de términos que se usan frecuentemente cuando se trabaja con árboles:

• Si A es la raíz de un árbol y B es la raíz de su subárbol izquierdo (o derecho), se dice que A es el padre de B y se dice que B es el hijo izquierdo (o derecho)de A. 
• Un nodo que no tiene hijos se denomina hoja 
• El nodo a es antecesor del nodo b (y recíprocamente el nodo b es descendiente del nodo a), si a es el padre de b o el padre de algún ancestro de b. 
• Un nodo b es un descendiente izquierdo del nodo a, si b es el hijo izquierdo de a o un descendiente del hijo izquierdo de a. Un descendiente derecho se define de la misma forma. 
• Dos nodos son hermanos si son hijos izquierdo y derecho del mismo padre.

Otros términos relacionados con árboles, tienen que ver con su funcinoamiento y topología:

• Si cada nodo que NO es una hoja tiene un subárbol izquierdo y un subárbol derecho, entonces se trata de un árbol binario completo. 
• El nivel de un nodo es el número de aristas que se deben recorrer para llegar desde ese nodo al nodo raíz. De manera que el nivel del nodo raíz es 0, y el nivel de cualquier otro nodo es el nivel del padre más uno. 
• La profundidad de un nodo es el máximo nivel de cualquier hoja en el árbol.

CLASIFICACIÓN DE ARBOLES BINARIOS 

DISTINTO

Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.

SIMILARES

Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.

EQUIVALENTES

Son aquellos arboles que son similares y que además los nodos contienen la misma información.

COMPLETOS

Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subarbol izquierdo y el subarbol derecho.

ÁRBOL FAMILIAR 

ALGORITMO DE ARBOLES BINARIOS

Clase Nodo

class nodo {     int dato;     nodo der;     nodo izq;     nodo(int dat)     {         this.dato=dat;         this.der=null;         this.izq=null;     } } Clase Árbol  public class arbol {     nodo raiz=null;     public boolean tieneraiz()     {         if(raiz==null) return false;         else return true;     }      public arbol alta(int dat)     {         if(!tieneraiz())         {             nodo nuevo=new nodo(dat);             raiz=nuevo;         }         else         {             boolean izq;             nodo actual=raiz;             while(true)             {                 if(actual.dato<dat) izq=false;                 else izq=true;                 if(!izq)                 {                     if(actual.der==null)                     {                         nodo nuevo=new nodo(dat);                         actual.der=nuevo;                         break;                     }                     else actual=actual.der;                 }                 else                 {                     if(actual.izq==null)                     {                         nodo nuevo=new nodo(dat);                         actual.izq=nuevo;                         break;                     }                     else actual=actual.izq;                 }             }         }return this;     }      public boolean baja(int dat)     {         nodo actual=raiz, anterior=raiz, temp;         while(true)         {             if(actual==null) break;             if(actual.dato==dat) break;             anterior=actual;             if(actual.dato<dat) actual=actual.der;             else actual=actual.der;         }         if(actual==null) return false;         else         {             if(actual==raiz)             {                 temp=actual.izq;                 raiz=raiz.der;                 anterior=raiz;             }             else             if (anterior.der == actual)             {                 temp=actual.izq;                 anterior=actual.der;             }             else             {              temp=actual.izq;              anterior.der=actual.izq;             }             actual=new nodo();             while(actual.izq!=null)                 actual=actual.izq;             actual.izq=temp;             return true;         }     }      public void imprimirpreorden()     {         ayudantePreorden(raiz);     }      public void ayudantePreorden(nodo dat)     {         if(dat==null)                 return;         System.out.printf("%d ",dat.dato);         ayudantePreorden(dat.der);         ayudantePreorden(dat.izq);     }      public void impririnorden(nodo dat)     {         if(dat!=null)         {             impririnorden(dat.izq);             System.out.println(" "+dat.dato);             impririnorden(dat.der);         }     } } Clase Main public class Main {      public static void main(String[] args) {         java.util.Scanner leer=new java.util.Scanner(System.in);         arbol x=new arbol();         int z;         System.out.print("Ingrese el numero de Datos a capturar: ");         z=leer.nextInt();         for(int i=1; i<=z;i++){         int m;         System.out.println("Ingrese Dato "+i+":  ");m=leer.nextInt();         x.alta(m);         }         System.out.println("Valores Capturados en PreOrden:");      x.imprimirpreorden();         int q;         System.out.print("\nIngrese dato a borrar: ");q=leer.nextInt();      x.baja(q);         System.out.println("\nDespues de borrar el dato "+q+" :");      x.imprimir();     }  }