Download EjerciciosDeArboles

EJERCICIOS DE ARBOLES
Para el Siguiente Nodo
class NodoABB {
int clave;
NodoABB der, izq;
}
a) Escriba un m‚todo static NodoABB podar(NodoABB p, int x ) que reciba un puntero
a la cabeza
de un arbol y retorne un puntero a un arbol con nodos > x. Esto lo debe hacer
en orden
menor que O(N log N) . Esto se logra de la siguiente manera:
- si el arbol es null se retorna null
- si se esta en un nodo con valor menor o igual que x se debe retornar el nodo
el hijo derecho
- si se esta en un nodo con valor mayor que x, podo lo que hay en el hijo izquierdo
y
retorno un puntero al mismo nodo
Nodo podar(Nodo p, int x) {
if (p == null) return null;
if (p.clave <= x) return p.der
p.izq = podar(p.izq, x);
}
b) Escriba un metodo con el encabezado Nodo clonar(Nodo p)
que recibe como parametro un puntero a un arbol binario
y retorna un puntero a un duplicado de ese mismo arbol.
El algorotmo a usar es:
si p es null el clonado es null
si no es null, retorno un nodo que es un clon del nodo apuntado
por p, con hijos derecho e izquierdos apuntando a clones de los
los hijos derechos e izquierdos de p
if (p == null) return p;
Nodo aux = new Nodo();
aux.clave = p.clave;
aux.izq = clonar(p.izq);
aux.der = clonar(p.der);
return aux;
----------------------------------------------------------------------------4- Se tiene la siguiente clase:
NodoArbol {
int info;
NodoAista izq, der;
}
a) Escriba una función int sumarClaves(NodoArbol x) que suma las infos de los nodos
que tiene
un árbol cuya raiz es x según el siguiente algoritmo recursivo:
• Si x es null se retorna 0
• Si no, se retorna la suma de las claves del ambos árboles hijos más la clave
del nodo x
b) Escribir una funcion public int mayor(NodoArbol x) que recibe un puntero a la
raiz de
un arbol y retorna el numero mayor guardado en sus nodos, suponiendo que solo tiene
numeros
positivos, USANDO EL SIGUIENTE ALGORITMO:
• si
• si
y el
info
x es null retorno -1
no es null, busco el mayor del sub-arbol derecho (m1),
mayor del sub-arbol izquiero (m2). Luego retorno el mayor entre m1, m2 y la
guardada en el nodo.
c) Escriba el método int jerárquico(NodoArbol x) que recibe un puntero
a la raiz de árbol que contiene solo números positivos mayores que 0.
El método retorna el valor en el nodo x si para todo el árbol se cumple
que la información que contiene el nodo padre es mayor que la que contienen
todos los hijos. En caso contrario retrna -1;
Use el siguiente algoritmo para resolver esto es el siguiente:
si x apunta a null retorno 0
en caso contrario, llamo recursivamente a la funcion para los dos hijos.
Si alguna llamada retorna -1 entonces retorno -1. De lo contrario,
si el resultado de ambas llamadas recursivas es menor que el contenido del
cambo info del nodo retorno ese valor (x.info), si no, retorno -1.
----------------------------------------------------------------------------------------------------------------------------- -----------------------------Pregunta 3:
Se tiene la siguiente clase:
NodoArbol {
int info;
NodoAista izq;
}
a) Escriba una función int cuantasVeces(NodoArbol x, int i) que retorna el numero
de nodos que contienen como info el numero i en el árbol cuya raíz es x según el
siguiente algoritmo recursivo:



Si x es null se retorna 0
Si no, llama recursivamente la funcion para contar cuantas veces está el i en
el subarbol izquierdo y cuantas veces esta i en el subarbol derecho.
Si el nodo x tambien contiene a i entonces se retorna la suma de ambos resultados
+ 1, si no, se retorna solo la suma de ambos resultados.
b) Escriba una función de encabezado boolean esta(NodoArbol x, int i) que retorna
true si el número i esta en al menos un nodo del árbol x USANDO OBLIGADAMENTE el
siguiente algoritmo:




Si x es null retorno false ;
Si info es igual a i retorno true;
Si nada de lo anterior se cumple, llamo recursivamente la función para que
busque en el subárbol izquierdo, si la llamada retorna true entonces retorno
true yo también;
Si no, llamo recursivamente la función para que busque en el subárbol
izquierdo, si la llamada retorna true entonces retorno true yo también, si
retorna false entonces retorno false también;
-----------------------------------------------------------------------------------1- Un arbol puede tener más de dos hijos. Para esto se
hace que cada nodo tenga un arreglo de punteros a hijos
NodoArbol {
int info;
NodoArbol[] hijos;
}
a) Escriba una funcion int nnodos(NodoArbol x) que cuente la cantidad de
nodos del arbol cuya raiz esta apuntada por x con el siguiente algoritmo:
Si x es null retorno 0
Si no es null, entonces pregunto si el arreglo hijos es null
Si es null retorno 1
Si no es null, para cada hijo no null llamo recursivamente
a la funcion y retorno la suma de todas las llamadas + 1
NodoArbol {
int info;
NodoArbol izq, der;
}
Escribir una funcion public int mayor(NodoArbol x) que recibe un
puntero a la raiz de
un arbol y retorna el numero mayor guardado en sus nodos, suponiendo
que solo tiene numeros
positivos, USANDO EL SIGUIENTE ALGORITMO:
• si x es null retorno -1
• si no es null, busco el mayor del sub-arbol derecho (m1),
y el mayor del sub-arbol izquiero (m2). Luego retorno el mayor entre
m1, m2 y la info guardada en el nodo.
----------------------------------------------------------------------------3- Considere el siguiente nodo para un arbol cuyos nodos pueden tener hasta 3 hijos:
NodoArbol {
int info;
NodoArbol izq, medio, der;
}
programe el metodo
public static int nnodos(NodoArbol x, int i, int j)
que retorna el numero de nodos del árbol que tiene x como raíz
------------------------------------------------------------------------------