Download EjerciciosDeArboles
Document related concepts
Transcript
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 ------------------------------------------------------------------------------