Arboles

REPUBLICA BOLIVARIANA DE VENEZUELA

MINISTERIO DEL PODER POPULAR PARA LA EDUCACION

SUPERIOR

UNIVERSIDAD CENTROCCIDENTAL LISANDRO ALVARADO

Es una estructura de datos no lineal, donde

la organización de los datos es de forma

Jerárquica o de niveles

La relación entre los elementos del árbol es de uno a

muchos, es decir, a cada elemento del árbol le pueden

seguir varios elementos.

Los objetos o elementos que conforman un árbol

son llamados nodos.

Un árbol es un conjunto finito de nodos, donde:

Existe un nodo único conocido como el nodo RAIZ.

Los nodos se relacionan entre ellos dando lugar a

las relaciones de

Padre, Antecesor, Hijo, Sucesor, Hermanos, etc.

Estructura de un Árbol

Es un tipo de árbol que se caracteriza por el hecho

de que cada nodo tiene grado menor o igual a 2, es

decir, cada nodo del árbol tiene un máximo de 2

hijos


Nodo Raíz: Primer elemento del árbol, solo existe un nodo raíz en un árbol.

Nodo Hoja o Terminal: Nodos que no tienen hijos.

Nodo Interior: Es un nodo que no es raíz ni Terminal.

Nodo Padre (Antecesor): nodo que tiene al menos un hijo (Un nodo X es padre de Y si apunta al nodo Y).

Nodo Hijo (Sucesor): nodo que tiene un padre. (Un Y es hijo de X si es apuntado por un nodo X). Un hijo puede ser IZQUIERDO o DERECHO, dependiendo si esta a la izquierda o ala derecha del nodo padre.

Nodos Hermanos: Nodos que son descendientes directos de un mismo padre.


- NODO RAIZ A

- NODOS HOJAS E,F,G,H

- NODOS INTERIORES B,C

- NODOS PADRES A (De B y C), B(De E y F) y C(De G y H)

- NODOS HIJOS B,C (De A), G,H(De C) E,F (De B)

- NODOS HERMANOS B y C, E y F, G y H


Ancestro: Un nodo X es ancestro del nodo Y, si X es padre de Y o si X es padre algún nodo ancestro de Y. (Por ejemplo el nodo raíz es un ancestro de todos los nodos del árbol.)

Descendiente: Un nodo Y es descendiente de X si Y es hijo de X, o si Y es hijo de algún nodo descendiente de X. (Por ejemplo todos los nodos de un árbol son descendientes del nodo raíz.)

Subárbol izquierdo: todos los descendientes por la izquierda de un nodo forman un subárbol izquierdo, cuya raíz es el hijo izquierdo de ese nodo.

Subárbol derecho: todos los descendientes por la derecha de un nodo forman un subárbol derecho, cuya raíz es el hijo derecho de ese nodo.



- Los Ancestros de I son: E, B y A

- Los Descendientes de C son : G, H y K

- El Sub-árbol izquierdo es el árbol de raíz B

- El Sub-árbol derecho es el árbol de raíz C

Grado de un Nodo: Es el número de descendientes directos o hijos de un nodo.

Grado del Árbol: Es el grado máximo de los nodos

del árbol.

Nivel de un Nodo: Es el numero de nodos que hay desde el nodo raíz hasta un nodo. El nodo raíz tiene

nivel 1, luego cada nodo tiene el nivel de su

padre+1.

Nivel del Árbol (Profundidad del Árbol o Altura del Árbol): Nivel máximo alcanzado por algún nodo del

árbol.


- El Grado de B es 2, el grado de H es 0.

- El Grado del árbol es 2

- El Nivel de E es 3, de B es 2, de A es 1…

- El Nivel del árbol es 3.


Es un árbol binario donde todos sus nodos tiene

dos hijos, menos los nodos del último nivel que son

nodos terminales.

De un árbol binario completo se puede decir que:

En cada nivel n hay 2 n-1 nodos, El Total de nodos

del árbol de Nivel N es igual a 2N -1

Árbol Binario Completo

- En el nivel 1 hay: 20 =1 nodo



- El total de nodos del árbol es: 23-1 = 7

Dado un árbol no binario, para convertirlo en

árbol binario se puede proceder de la

siguiente manera:

Cada nodo conservará solo a su hijo

izquierdo.

Cada nodo adoptará a su hermano

derecho como hijo derecho

CONSTRUCCIÓN DE UN ÁRBOL BINARIO A

PARTIR DE UN ARBOL NO BINARIO

CONSTRUCCIÓN DE UN ÁRBOL BINARIO A

PARTIR DE UN ARBOL NO BINARIO

Representación Enlazada

En la implementación enlazada se utilizan apuntadores para

tener acceso a los nodos del árbol. Así como en las listas

enlazadas, existe un apuntador externo que apunta a la raíz del

árbol, y luego a partir de allí se puede acceder a todos losnodos del árbol.

Los nodos en este caso, se conforman de tres campos:

Un campo para la información del nodo.

Un campo apuntador para apuntar al subárbol izquierdo y

otro para apuntar al subárbol derecho.

NIVEL DE IMPLEMENTACION

#ifndef Arbol_H

#define Arbol_H

template <class Tipo>

class Arbol;

#ifndef NODO_H

#define NODO_H


class nodo

{

Tipo info;

nodo<Tipo>* izq;

nodo<Tipo>* der;

friend class Arbol<Tipo>;

};

#endif


Arbol<Tipo>::Arbol() {

Raiz=NULL;

};


bool Arbol<Tipo>::Vacia() {

return Raiz == NULL;

};


bool Arbol<Tipo>::Llena() {

nodo<Tipo> *p; p=new nodo<Tipo>;

if (p==NULL)

return true;

else {

delete p;

return false;

}

};


Crear Nodo: Esta operación crea un nodo y lo asigna como raíz con

subárboles izquierdo y derecho vacíos y retorna la dirección de este

nodo.



nodo<Tipo>* Arbol<Tipo>::CrearNodo(Tipo

Valor) {

Apuntador nuevo;

if (!Llena()) {

nuevo=new nodo<Tipo>;

nuevo->info=Valor;

nuevo->izq=NULL;

nuevo->der=NULL;

return nuevo;

};

};

Crear Hijo Derecho : Esta operación almacena un nodo como

el hijo derecho del nodo PTR.



bool

Arbol<Tipo>::CrearHijoDer(Apuntador

p,Tipo Valor) {

Apuntador nuevo;

if (!Llena()) {

if ((p==NULL) || (p->der!=NULL))

return false;

else {

nuevo=CrearNodo(Valor);

p->der=nuevo;

return true;

};

}

else return false; };

CrearHijoIzq: Esta operación almacena un nodo como el hijo

izquierdo del nodo PTR.



bool Arbol<Tipo>::CrearHijoIzq(Apuntador

p,Tipo Valor) {

Apuntador nuevo;

if (!Llena()) {

if ((p==NULL) || (p->izq!=NULL))

return false;

else {


p->izq=nuevo; return true;

};

}

else

return false;

};

Combinar: Esta función combina dos árboles binarios A1 y A2

teniendo como unión la raíz cuya información es valor.



nodo<Tipo>* Arbol<Tipo>::Combinar(Apuntador a1,Apuntador a2,Tipo Valor)

{

Apuntador nuevo;

if (!Llena())

{


nuevo->izq=a1;

nuevo->der=a2;

return nuevo;

}

else

return NULL;

};

EliminarDer: Elimina el hijo derecho siempre que sea nodo

terminal y retorna el valor.


bool Arbol<Tipo>::EliminarDer(Apuntador padre,Tipo &Valor)

{

Apuntador p;

p=padre->der;

if ((p->izq==NULL) && (p->der==NULL))

{

Valor=p->info;

padre->der=NULL;

delete p;

return true;

}

else

return false;

};


EliminarIzq: Elimina el hijo izquierdo siempre que sea nodo

terminal y retorna el valor.



bool

Arbol<Tipo>::EliminarIzq(Apuntador

padre,Tipo &Valor)

{

Apuntador p;

p=padre->izq;


{

Valor=p->info;

padre->izq=NULL;

delete p;

return true;

}

else

return false;

};

Eliminar: Elimina el nodo p siempre que sea nodo terminal y

retorna el valor.



bool Arbol<Tipo>::Eliminar(Apuntador &p,Tipo &Valor)

{


{

Valor=p->info;

delete p;

p=NULL;

return true;

}

else

return false;

};

Destructor: Liberar el espacio ocupado por el Árbol, para lo

cual llama a la función Liberar, que de forma recursiva libera el

Árbol.



void Arbol<Tipo>::Liberar(Apuntador

&p) {

if (p!=NULL)

{

Liberar(p->izq);

Liberar(p->der);

delete p;

p=NULL;

};

};


Arbol<Tipo>::~Arbol()

{

Liberar(Raiz);

};

Arboles

Education

Transcript of Arboles