Download to get the file

Tema 4 Árboles.
Árboles binarios. Algoritmos básicos
Algoritmos básicos con árboles binarios
 Recorrido completo.
 Creación.
 Terminación anticipada.
 Recorridos especiales.
 Manejo de varias estructuras.
Recorrido en Preorden.
// Escribe las claves del árbol binario en preorden.
static void preOrden (NodoArbol arbol) {
if (arbol != null) {
System.out.print (arbol.clave+" ") ;
arbol
preOrden (arbol.iz);
preOrden (arbol.de);
}
}
public void preorden () {
preorden (raiz);
}
nombre
raiz
Aplicado a objetos de la clase Arbol:
1
2
 Orden de visita de nodos:
3
1, 2, 4, 9, 15, 5, 3, 8 y 7.
4
 Preferido para:
 Búsquedas.
9
5
15
8
7
Recorrido en Orden Central
 Aplicado a objetos de la clase Arbol:
nombre
// Escribe las claves del árbol binario en orden central.
static void ordenCentral (NodoArbol arbol) {
if (arbol != null) {
ordenCentral (arbol.iz);
System.out.print (arbol.clave+" ");
ordenCentral (arbol.de);
}
}
public void ordenCentral () {
ordenCentral (raiz);
4
}
 Orden de visita de nodos:
9, 4, 15, 2, 5, 1, 8, 3 y 7.
9
raiz
arbol
1
2
3
5
8
15
 Preferido para:
 Recorrido de acuerdo al orden físico de los nodos.
 En árboles binarios de búsqueda recupera la secuencia.
7
Recorrido en Postorden
// Escribe las claves del árbol binario en postorden.
static void postOrden (NodoArbol arbol) {
arbol
if (arbol != null) {
postOrden (arbol.iz);
postOrden (arbol.de);
System.out.print (arbol.clave + " ") ;
}
}
public void postOrden () {
postOrden (raiz);
}
 Orden de visita de nodos:
1
2
4
9, 15, 4, 5, 2, 8, 7, 3 y 1.
 Preferido para:
 Liberar memoria.
 Nodos buscados en los niveles
más bajos del árbol.
nombre
9
raiz
 Aplicado a objetos de la clase Arbol:
3
5
15
8
7
Ejemplo: suma de claves
static int sumaClaves (NodoArbol nodoArbol) {
int resul = 0;
if (nodoArbol != null) {
resul = nodoArbol.clave + sumaClaves (nodoArbol.iz);
resul = resul + sumaClaves (nodoArbol.de);
}
return resul;
}
static int sumaClaves (Arbol a) {
return sumaClaves (a.raiz);
}
If (nodoArbol != null)
{
resul =sumaClaves(nodoArbol.iz)+nodoArbol.clave;
resul =resul+sumaClaves(arbol.de);
}
1
else resul=0
34 resul =15+24=39
6
17 resul =9+6
18
16 resul=5+4 = 9
33 resul =15+9=24
25 resul =7+8
9 resul=2+3
3
8
2
10
19
26
2
3
8 resul=2+0 = 2
5 resul=0+2
6
null
4 resul=0
null
7 resul=0
24 resul =7+0 = 7
22 resul =0+7
7
13 resul=0+4
4
11
14
null
12 resul=0
null
15 resul=0
20
null
21 resul=0
null
23 resul=0
32 resul=9+0 = 9
29 resul=0+9
9
30
27
null
28 resul=0
null
31 resul=0
Recorrido en Amplitud
arbol
static void probarAmplitud (Arbol arbol) {
NodoArbol referencia;
ColaArbol colaArbol = new ColaArbol ();
referencia = arbol.raiz;
if (referencia != null)
colaArbol.encolar (referencia);
while (! colaArbol.colaVacia ()) {
referencia = colaArbol.desencolar ();
System.out.print (referencia.clave + " ");
if (referencia.iz != null)
colaArbol.encolar (referencia.iz);
if (referencia.de != null)
colaArbol.encolar (referencia.de);
}
raiz
Arbol
nombre
1
2
}
 Orden de visita de nodos:
4
5
1, 2, 3, 4, 5, 8, 7, 9 y 15.
9
3
15
8
7
Obtención de la copia de un árbol
static Arbol copiarArbol (Arbol arbol) {
Arbol resul = new Arbol();
resul.nombre = "Arbol copia";
if (arbol.raiz != null)
resul.raiz = copiaArbol (arbol.raiz);
return resul;
}
static NodoArbol copiaArbol (NodoArbol nodoArbol) {
NodoArbol nuevoNodo = new NodoArbol();
nuevoNodo.clave = nodoArbol.clave;
if (nodoArbol.iz != null)
nuevoNodo.iz = copiaArbol (nodoArbol.iz);
if (nodoArbol.de != null)
nuevoNodo.de = copiaArbol(nodoArbol.de);
return nuevoNodo;
}
Insertar
 Criterio de inserción:
 Orden de los nodos.
 Operación juntar (join).
 Preguntar en qué rama se quiere insertar …
 No se permite insertar claves repetidas
 Búsqueda previa del dato que se quiere insertar para
evitar repeticiones.
 Se inserta cuando alcanzamos el nivel más
profundo (nodos hojas) de la rama seleccionada.
Inserción en árbol binario genérico
static public void juntar (Arbol arbol, int dato, Arbol a1, Arbol a2) {
if (a1.raiz == a2.raiz && a1.raiz != null)
System.out.println ("no se pueden juntar, a1 y a2 son iguales") ;
else {
arbol.raiz = new NodoArbol () ;
arbol.raiz.clave = dato;
arbol.raiz.iz = a1.raiz;
arbol.raiz.de = a2.raiz;
if (arbol != a1)
a1.raiz = null;
if (arbol != a2)
a2.raiz = null;
}
}
Inserción en árbol binario de búsqueda.
static NodoArbol insertar (NodoArbol arbol, int dato) {
NodoArbol resul = arbol;
if (arbol != null)
if (arbol.clave < dato)
arbol.de = insertar (arbol.de, dato);
else if (arbol.clave > dato)
arbol.iz = insertar (arbol.iz, dato);
else System.out.println ("la clave ya existe");
else resul = new NodoArbol (dato);
return resul;
}
public void insertar (int dato) {
raiz = insertar (raiz, dato);
}
Método static que
recibe un NodoArbol
y devuelve otro
como resultado
Método de objeto
de Arbol
Búsqueda en árbol binario.
boolean encontrar (int dato) {
return encuentra (raiz, dato);
}
static boolean encuentra (NodoArbol nodoArbol, int dato) {
boolean resul;
if (nodoArbol != null)
if (nodoArbol.clave == dato)
resul = true;
else {
resul = encuentra (nodoArbol.iz, dato);
if (!resul)
resul = encuentra (nodoArbol.de, dato);
}
else resul = false;
return resul;
}
Búsqueda en árbol binario de búsqueda.
boolean encontrar (int dato) {
return encuentra (raiz, dato);
}
public static boolean encuentra (NodoArbol nodoArbol, int dato) {
boolean resul = false;
if (nodoArbol != null)
if (nodoArbol.clave == dato)
resul = true;
else if (nodoArbol.clave > dato)
resul = encuentra (nodoArbol.iz, dato);
else resul = encuentra (nodoArbol.de, dato);
return resul;
}
Ejemplo: Verificar que un árbol Binario es
de Búsqueda
static class arbolBusqueda {
static int ant;
static boolean primero = true;
static boolean esBusqueda (NodoArbol arbol) {
boolean resul;
if (arbol == null)
resul = true;
else {
resul = esBusqueda (arbol.iz);
if (primero)
primero = false;
else if (arbol.clave <= ant)
resul = false;
if (resul) {
ant = arbol.clave;
resul = esBusqueda(arbol.de);
}
}
static boolean esBusqueda (Arbol a) {
return resul;
return arbolBusqueda.esBusqueda (a.raiz);
}
}
}
Eliminar una clave (I).
 Fase I. Se localiza la clave a eliminar (si existe).
 Fase II. Tres posibles situaciones:
 Clave está en un nodo hoja:
 Liberar memoria (innecesario en Java) y asignar el árbol a null.
 Clave tiene un único descendiente:
 Apuntar al subárbol no vacío y liberar memoria (innecesario en
Java).
 Clave tiene dos descendientes:
 [Orden topológico anterior] Se localiza el descendiente más a la
derecha del hijo izquierdo, se sustituye la clave a borrar por la
clave encontrada, se “cortocircuita” el subárbol izquierdo y se
borra (innecesario en Java) el nodo que contenía la clave
sustituida.
Eliminar una clave (II).
 Peculiaridades del lenguaje Java.
 Causa: Las referencias (punteros) se pasan por valor.
 Efecto: Los cambios realizados en la instancia actual
sobre el puntero (NodoArbol) que se recibe como
argumento no surten efecto cuando se retorna a la
instancia de llamada.
 Técnica posible: Construir métodos que devuelvan
actualizado el puntero (referencia) que se recibe como
argumento.

Ejemplo:
static NodoArbol elimina (NodoArbol nodoArbol, int dato) {
// cuerpo del método que modifica nodoArbol;
return nodoArbol;
}
static void eliminarClave (Arbol arbol, int dato) {
arbol.raiz = eliminarElemento (arbol.raiz, dato);
}
static NodoArbol eliminarElemento (NodoArbol arbol, int elem) {
NodoArbol p;
if (arbol != null)
if (arbol.clave > elem)
arbol.iz = eliminarElemento (arbol.iz, elem);
else if (arbol.clave < elem)
arbol.de = eliminarElemento (arbol.de, elem);
else {
p = arbol;
if (arbol.iz == null)
arbol= arbol.de;
else if (arbol.de == null)
arbol = arbol.iz;
else arbol.iz = eliminar2Hijos (arbol.iz, p);
}
else System.out.println (" la clave buscada no existe");
return arbol;
}
static NodoArbol eliminar2Hijos (NodoArbol arbol, NodoArbol p) {
NodoArbol resul;
if (arbol.de != null) {
resul = arbol;
arbol.de = eliminar2Hijos (arbol.de, p);
}
else {
p.clave = arbol.clave;
resul = arbol.iz;
}
return resul;
}
Eliminar un árbol.
static void eliminarArbol (Arbol arbol) {
System.out.println ("NOTA: Este algoritmo es innecesario en Java ");
System.out.println (“Lo que no sucede en todos los lenguajes");
if (arbol.raiz == null)
System.out.println ("Arbol vacio");
else {
arbol.raiz =eliminaArbol (arbol.raiz);
System.out.println (“Faltaría 'destruir' la referencia principal (arbol)");
}
}
static NodoArbol eliminaArbol (NodoArbol nodoArbol) {
NodoArbol resul;
if (nodoArbol != null) {
nodoArbol.iz = eliminaArbol (nodoArbol.iz);
nodoArbol.de = eliminaArbol (nodoArbol.de);
System.out.println ("Clave antes de ser eliminada: “+nodoArbol.clave);
nodoArbol = null;
resul = nodoArbol;
}
else resul = null;
return resul;
}
Tratamiento de hojas. Ejemplo.
 Condición de hoja:
(nodoArbol.iz == null) && (nodoArbol.de == null)
 Ejemplo: Devuelve el número de hojas de un árbol
static int cuentaHojas (Arbol arbol) {
return contarHojas (arbol.raiz);
}
static int contarHojas (NodoArbol nodoArbol) {
int resul = 0;
if (nodoArbol != null)
if ((nodoArbol.iz == null) && (nodoArbol.de == null))
resul = 1;
else resul = contarHojas (nodoArbol.iz) + contarHojas (nodoArbol.de);
return resul;
}
Constancia de nivel. Recorrido en
profundidad (I)
 Mecanismo:
Se pasa un argumento entero (inicializado a 1) que se incrementa
en cada llamada.
 Ejemplo:
static void clavesNiveles (Arbol arbol) {
clavesNiveles (arbol.raiz,1);
}
static void clavesNiveles (NodoArbol nodoArbol, int n) {
if (nodoArbol != null) {
System.out.println ("Clave: “ + nodoArbol.clave + " en el nivel: “ + n);
clavesNiveles (nodoArbol.iz, n+1);
clavesNiveles (nodoArbol.de, n+1);
}
}
Constancia de nivel. Recorrido en
profundidad (II)
Ejemplo: Método que devuelve la altura de un árbol.
static int pruebaAltura (Arbol arbol) {
int resul = 0;
if (arbol.raiz != null)
resul = Altura.altura (arbol.raiz,1);
return resul;
}
static int altura (NodoArbol nodoArbol, int n, int altura) {
int resulIz, resulDe;
if (nodoArbol != null) {
if (n > altura)
altura = n;
resulIz = altura (nodoArbol.iz, n+1, altura);
resulDe = altura (nodoArbol.de, n+1, altura);
altura = Math.max (resulIz, resulDe);
}
return altura;
}
Constancia de nivel. Recorrido en amplitud (I).
 Dos opciones:
 Iteración anidada en dos niveles.
 Modificar la cola de referencias a nodos del árbol para
que incluya una variable con el nivel.
Constancia de nivel. Recorrido en amplitud (II)
 Sin modificar la cola de referencias.
 Dos iteraciones:


Externa que recorre el árbol en niveles
Interna que visita los nodos en amplitud
 Variables:



contador: controla el recorrido del nivel
actual: amplitud del nivel
siguiente: número de hijos del siguiente nivel
static void ListarAmplitud (Arbol arbol) {
Cola c = new tad_cola ();
int actual, siguiente, contador, altura;
NodoArbol p p = arbol.raiz;
Arbol.raiz
altura = 0;
siguiente = 1;
p
p = arbol;
2
if (p != null )
c.encolar (p);
4
5
while (!c.colaVacia()) {
actual = siguiente;
siguiente = 0;
↑1
contador = 1;
altura++;
altura = 0
while (contador <= actual) {
siguiente =1;
p = c.desencolar ();
System.out.println ("clave: "+p.clave+" nivel: "+altura);
contador++;
if (p.iz != null) {
c.encolar (p.iz);
siguiente++;
}
if (p.de != null) {
c.encolar (p.de);
siguiente++;
}
}
}
}
1
3
8
altura = 0
static void ListarAmplitud (Arbol arbol) {
siguiente = 1;
Cola c = new tad_cola ();
Arbol.raiz
int actual, siguiente, contador, altura;
c.inicializarCola ();
p
NodoArbol p = arbol.raiz;
2
altura = 0;
siguiente = 1;
p = arbol;
4
5
if (p != null )
c.encolar (p);
↑1
while (!c.colaVacia()) {
actual = siguiente;
actual = 1
siguiente = 0;
contador = 1;
siguiente = 0
altura++;
contador = 0
while (contador <= actual) {
altura = 1
p = c.desencolar ();
System.out.println ("clave: "+p.clave+" nivel: "+altura);
contador++;
if (p.iz != null) {
c.encolar (p.iz);
siguiente++;
}
if (p.de != null) {
c.encolar (p.de);
siguiente++;
}
}
}
}
1
3
8
Iteración interna:
static void ListarAmplitud (Arbol arbol) {
NodoArbol p p = arbol.raiz;
while (contador <= actual) actual = 1
Cola c = new tad_cola ();
contador = 0
int actual, siguiente, contador, altura;
altura = 1
Arbol.raiz
altura = 0;
siguiente = 1;
1
c.inicializarCola ();
p
p = arbol;
2
3
if (p != null )
c.encolar (p);
4
5
8
while (!c.colaVacia()) {
actual = siguiente;
↑2 ↑3
siguiente = 0;
contador = 1;
altura++;
while (contador <= actual) {
clave es 1, altura 1
↑1
p = c.desencolar ();
contador = 1
System.out.println ("clave: "+p.clave+" nivel: "+altura);
contador++;
siguiente = 1
if (p.iz != null) {
siguiente = 2
c.encolar (p.iz);
siguiente++;
}
salimos de la iteración interna
if (p.de != null) {
c.encolar (p.de);
siguiente++;
}
}
}
}
Arbol.raiz
static void ListarAmplitud (Arbol arbol) {
1
NodoArbol p p = arbol.raiz;
P
siguiente =2
Cola c = new tad_cola ();
altura =1
2
3
int actual, siguiente, contador, altura;
altura = 0;
4
5
8
siguiente = 1;
c.inicializarCola ();
p = arbol;
↑2 ↑3
if (p != null )
c.encolar (p);
actual = 2
while (!c.colaVacia()) {
siguiente = 0
actual = siguiente;
contador = 0
siguiente = 0;
altura = 2
contador = 1;
altura++;
while (contador <= actual) {
while (contador <= actual)
p = c.desencolar ();
System.out.println ("clave: "+p.clave+" nivel: "+altura);
1
P
contador++;
if (p.iz != null) {
↑3 ↑4
2
3
↑5
c.encolar (p.iz);
siguiente++;
}
4
5
8
if (p.de != null) {
c.encolar (p.de);
siguiente++;
↑2
siguiente = 1
}
siguiente = 2
}
clave es 2 y altura 2
}
contador = 1
}
iteración interna:
static void ListarAmplitud (Arbol arbol) {
while (contador <= actual)
NodoArbol p p = arbol.raiz;
1
P
Cola c = new tad_cola ();
int actual, siguiente, contador, altura;
↑4
2
3
↑5 ↑8
altura = 0;
siguiente = 1;
4
5
8
c.inicializarCola ();
p = arbol;
↑3
if (p != null )
c.encolar (p);
siguiente = 3
while (!c.colaVacia()) {
clave es 3 y altura 2
actual = siguiente;
siguiente = 0;
contador = 2
contador = 1;
altura++;
---- salimos de la iteración interna ---while (contador <= actual) {
p = c.desencolar ();
System.out.println ("clave: "+p.clave+" nivel: "+altura);
P
contador++;
1
if (p.iz != null) {
c.encolar (p.iz);
↑4
2
3
↑5 ↑8
siguiente++;
}
4
5
8
if (p.de != null) {
c.encolar (p.de);
siguiente++;
actual = 3
}
siguiente = 0
}
contador = 0
altura = 3
}
}
clave es 3 y altura 2
iteración interna:
static void ListarAmplitud (Arbol arbol) {
while (contador < =actual)
NodoArbol p p = arbol.raiz;
Cola c = new tad_cola ();
1
P
int actual, siguiente, contador, altura;
altura = 0;
2
↑5 ↑8
siguiente = 1;
c.inicializarCola ();
4
5
8
p = arbol;
↑4
if (p != null )
actual = 3
c.encolar (p);
contador = 1
while (!c.colaVacia()) {
actual = siguiente;
clave es 4 y altura 3
siguiente = 0;
contador = 1;
altura++;
actual = 3
↑8
while (contador <= actual) {
contador = 2
p = c.desencolar ();
↑5"+altura);
System.out.println ("clave: "+p.clave+" nivel:
clave es 5 y altura 3
contador++;
if (p.iz != null) {
c.encolar (p.iz);
siguiente++;
actual = 3
}
contador = 3
if (p.de != null) {
c.encolar (p.de);
clave es 8 y altura 3
↑8
siguiente++;
}
}
}
}
3
Constancia de nivel. Recorrido en amplitud (III)
 Modificando la cola de referencias.
class tElemento {
int nivel;
NodoArbol nodoArbol;
tElemento (NodoArbol a, int n) {
nivel = n;
nodoArbol = a;
}
class NodoColaArbolModificada {
NodoColaArbolModificada siguiente;
tElemento elem;
NodoColaArbolModificada () {
elem = null;
siguiente = null;
}
}
}
public class ColaArbolModificada {
private NodoColaArbolModificada principio;
private NodoColaArbolModificada fin;
public ColaArbolModificada () {
principio = null;
fin = null;
}
}
Constancia de nivel. Recorrido en amplitud (IV)
static void listarAmplitud (Arbol arbol) {
NodoArbol p;
int nivel;
ColaArbolModificada cola = new ColaArbolModificada();
p = arbol.raiz;
if (p != null) {
tElemento elem = new tElemento (referencia, 1);
cola.encolar(elem);
while (! cola.colaVacia()) {
elem = cola.desencolar ();
p = elem.nodoArbol;
nivel = elem.nivel;
System.out.println("nivel: "+nivel+" "+p.clave+" ");
if (p.iz != null) {
elem = new tElemento(p.iz,nivel+1);
cola.encolar(elem);
}
if (p.de != null) {
elem = new tElemento (p.de, nivel+1);
cola.encolar(elem);
}
}
}
}
Ver
codigo
nodoArbol
1
p
static void listarAmplitud(Arbol arbol) {
2
NodoArbol referencia;
int nivel;
4
5
ColaArbolModificada cola = new ColaArbolModificada();
p = arbol.raiz;
↑1 1
if (p != null) {
tElemento elem = new tElemento (p, 1);
cola.encolar(elem);
nodoArbol
while (! cola.colaVacia()) {
elem = cola.desencolar();
p = elem.nodoArbol;
p
nivel = elem.nivel;
2
System.out.println("nivel: "+nivel+" "+p.clave+" ");
4
5
if (p.iz != null) {
elem = new tElemento (p.iz, nivel+1);
cola.encolar (elem);
↑2 2
↑3 2
}
if (p.de != null) {
p = ↑1
elem = new tElemento(p.de, nivel+1); ↑1 1
nivel =1;
cola.encolar(elem);
clave 1, Nivel 1
}
}
}
}
3
8
1
3
8
nodoArbol
1
p
2
while (! cola.colaVacia()) {
elem = cola.desencolar();
↑2 2
referencia = elem.nodoArbol;
nivel = elem.nivel;
System.out.println("nivel: "+nivel+" "+p.clave+" ");
if (p.iz != null) {
elem = new tElemento (p.iz,nivel+1);
cola.encolar(elem);
}
if (p.de != null) {
elem = new tElemento (p.de,nivel+1);
cola.encolar(elem);
}
}
3
4
5
↑3 2
↑4 3
↑5 3
p = ↑2
nivel =2;
clave 1, nivel 1
clave 2, nivel 2
nodoArbol
p
1
2
4
3
5
↑4 3
↑3 2
8
p = ↑3
nivel =3;
clave 1, nivel 1
clave 2, nivel 2
8
↑5 3
↑8 3
nodoArbol
1
p
2
while (! cola.colaVacia()) {
elem = cola.desencolar();
4
5
8
referencia = elem.nodoArbol;
nivel = elem.nivel;
System.out.println("nivel: "+nivel+" "+p.clave+" "); ↑5 3 ↑8 3
if (p.iz != null) {
p = ↑4; n =2;
elem = new tElemento (p.iz,nivel+1);
↑4 3
clave 1, nivel 1
cola.encolar(elem);
clave 2, nivel 2
}
clave 3, nivel 2
clave 4, nivel 3
if (p.de != null) {
elem = new tElemento (p.de,nivel+1);
nodoArbol
cola.encolar(elem);
1
}
}
3
2
4
p
p = ↑5; n =3;
clave 1, nivel 1
clave 2, nivel 2
clave 3, nivel 2
clave 4, nivel 3
clave 5, nivel 3
↑8 3
↑5 3
5
3
8
nodoArbol
1
2
3
p
4
while (! cola.colaVacia()) {
elem = cola.desencolar();
referencia = elem.nodoArbol;
↑8 3
nivel = elem.nivel;
System.out.println("nivel: "+nivel+" "+p.clave+" ");
if (p.iz != null) {
elem = new tElemento (p.iz,nivel+1);
cola.encolar(elem);
}
if (p.de != null) {
elem = new tElemento (p.de,nivel+1);
cola.encolar(elem);
}
}
5
8
p = ↑8; n =3;
clave 1, nivel 1
clave 2, nivel 2
clave 3, nivel 2
clave 4, nivel 3
clave 5, nivel 3
Clave 8, nivel 3
Verificar si dos árboles son iguales
static boolean pruebaIguales (Arbol arboA, Arbol arbolB) {
return sonIguales (arbol1.raiz, arbol2.raiz);
}
static boolean sonIguales (NodoArbol a, NodoArbol b) {
boolean resul ;
if ((a == null) && (b == null))
resul = true;
else if ((a == null) || (b == null))
resul = false;
else if (a.clave == b.clave)
resul = sonIguales (a.iz, b.iz) && sonIguales (a.de, b.de);
else resul = false;
return resul;
}
Arbol Binario de Búsqueda contenido en
lista
static boolean estaContenido (NodoArbol nodoArbol, NodoLista nodoLista) {
boolean seguir, saltar;
if (nodoArbol == null)
seguir = true;
else {
seguir = estaContenido (nodoArbol.iz, nodoLista);
if (seguir && (nodoLista != null))
if (nodoArbol.clave < nodoLista.clave)
seguir = false;
else {
saltar = true;
while ((nodoLista != null) && saltar)
if (nodoArbol.clave == nodoLista.clave)
saltar = false;
else nodoLista = nodoLista.sig;
if (!saltar)
seguir = estaContenido (nodoArbol.de, nodoLista.sig);
else seguir = false;
}
else seguir = false;
}
return seguir;
}
static boolean estaContenido (Arbol arbol, Lista lista) {
return estaContenido (arbol.raiz, lista.inicio);
}