Informatica

Estructuras de datos
Un arbol es un conjunto de nodos que cumplen
con las relaciones padre, hijo y hermano.
Llamamos hijos de un nodo a todos los nodos que
podemos llegar directamente por medio de un
apuntador hacia ellos y descendencia a todos los
que pudieramos llegar a traves de los hijos y su
propia descendencia.
Llamamos padre al nodo del cual proviene el nodo
hijo. Existe un nodoque no tiene padre y le
llamamos raiz del arbol.
Ing. Jorge A. Hernández P.: Arboles
Ing. Jorge A. Hernández P.: Arboles

Estructuras de datos
Llamamos hermanos a todos los nodos que tienen el
mismo padre.
Llamamos hoja al nodo que no tiene hijos.
Podemos definir un árbol de manera recursiva diciendo
que un árbol sin nodos esta vacío. Un arbol es un nodo
llamado raiz cuyos hijos sontambien arboles(vacios o no).
Notemos que una lista es un arbol cuyos nodos solo tienen
un hijo.
Un arbol binario es aquel cuyos nodos pueden tener a lo
más dos hijos.
Ing. Jorge A. Hernández P.: Arboles
Ing. Jorge A. Hernández P.: Arboles

1

Estructuras de datos
Un arbol cuyos nodos tienen 0 o 2 hijos se llama
estrictamente binario. Si algún nodo tiene un solo
hijo ya no lo es.Llamamos nivel al numero de apuntadores que se
tienen que recorrer para llegar a un nodo a partir la
raiz, asi el nodo raiz esta en el nivel 0 y sus hijos
en el nivel 1.
La profundidad de un árbol es igual al mayor nivel
de sus hojas
Ing. Jorge A. Hernández P.: Arboles
Ing. Jorge A. Hernández P.: Arboles

Estructuras de datos
Un árbol estrictamente binario cuyas hojas estan
todas en el mismonivel se llama arbol binario
completo.
Un arbol estrictamente binario cuyas hojas estan a
lo más en dos niveles diferentes se llama arbol casi
completo y se dice que el arbol esta balanceado.
Los arboles binarios son muy importantes en las
operaciones de busqueda y para ello deben
mantenerse balanceados.
Ing. Jorge A. Hernández P.: Arboles
Ing. Jorge A. Hernández P.: Arboles

2Estructuras de datos
raiz
1

2

4

3

5

6

7

El nodo 1 es el nodo raiz. Los
nodos 2 y 3 son el hijo
izquierdo y el hijo derecho del
nodo raiz. Los nodos 4, 5, 6 y 7
son las hojas del arbol.

El padre del nodo 5 es 2 y del nodo 7 es 3. Los nodos 2
y 3 son hermanos. La profundidad del arbol es 2.

Ing. Jorge A. Hernández P.: Arboles
Ing. Jorge A. Hernández P.: ArbolesEstructuras de datos
El arbol de la lamina anterior tambien es un arbol
estrictamente binario y ademas completo.
Para mayores ejemplos de arboles binarios y su
clasificación consultar el libro de Tenenbaum en el
capítulo de arboles.

Ing. Jorge A. Hernández P.: Arboles
Ing. Jorge A. Hernández P.: Arboles

3

Estructuras de datos
Para implementar un arbol binario es necesario crearprimero una clase
Nodo_Arbol capaz de almacenar cualquier dato y que tenga dos
apuntadores a los hijos izquierdo y derecho.
template class Nodo_Arbol: public Nodo{
public:
Nodo_Arbol(T);
T
GetDato(){ return Nodo::GetDato();}
Nodo_Arbol*
GetDer(){ return (Nodo_Arbol *)GetSiguiente();}//cast de Nodo * a Nodo_Arbol *
void
SetDer(Nodo_Arbol *d){SetSiguiente((Nodo *)d);}//cast de Nodo_Arbol * aNodo *
Nodo_Arbol*
GetIzq(){ return izq;}
void
SetIzq(Nodo_Arbol *d){izq = d;}
private:
Nodo_Arbol
*izq;
};
template Nodo_Arbol::Nodo_Arbol(T x): Nodo(x){ //manda a llamar al constructor de Nodo
izq = NULL;
}

Ing. Jorge A. Hernández P.: Arboles
Ing. Jorge A. Hernández P.: Arboles

Estructuras de datos
La implementación de Nodo_Arbol usa herencia y
hereda las caracteristicas deNodo, es decir usa las
propiedades y la interfaz de la clase Nodo que se
uso para crear Listas. Para tener una nomenclatura
consistente se renombro el apuntador siguiente
para convertirlo en der, y se añadio el apuntador al
nodo izq. Para ello fue necesario hacer
conversiones de tipos o cast. Estas conversiones
deben manejarse con cuidado para evitar
referencias erroneas a la memoria....