Ejercicios arbol avl

1771 palabras 8 páginas
EJERCICIOS DE ÁRBOLES BINARIOS 1) Supongamos que tenemos una función valor tal que dado un valor de tipo char (una letra del alfabeto) devuelve un valor entero asociado a dicho identificador. Supongamos también la existencia de un árbol de expresión T cuyos nodos hoja son letras del alfabeto y cuyos nodos interiores son los caracteres *, +, -, /. Diseñar una función que tome como parámetros un nodo y un árbol binario y devuelva el resultado entero de la evaluación de la expresión representada. 2) El recorrido en preorden de un determinado árbol binario es: GEAIBMCLDFKJH y en inorden IABEGLDCFMKHJ. • • • Dibujar el árbol binario. Dar el recorrido en postorden. Diseñar una función para dar el recorrido en postorden dado el recorrido en …ver más…
En nuestro caso almacenamos la altura real por simplicidad. Por consiguiente podemos definir la siguiente macro: #define altura(n) (n?n->altura:-1) La cual nos devuelve la altura de un nodo_avl. Con estas declaraciones la funciones de creación y destrucción para los árboles AVLpueden ser como sigue: arbolAVL Crear_AVL() { return AVL_VACIO; } void Destruir_AVL (arbolAVL A) { if (A) { Destruir_AVL(A->izqda); Destruir_AVL(A->drcha); free(A); } }

Es sencillo realizar la implementación de una función que podemos llamar miembro que nos devuelve si un elemento pertenece al árbol AVL. Podría ser la siguiente: int miembro_AVL(tElemento e,arbolAVL A) { if (A == NULL) return 0; if (e == A->elemento) return 1; else if (e < A->elemento) return miembro_AVL(e,A->izqda); else return miembro_AVL(e,A->drcha); }

Veamos ahora la forma en que puede afectar una inserción en un árbol AVL y la forma en que deberíamos reorganizar los nodos de manera que siga equilibrado. Consideremos el esquema general de la siguiente figura, supongamos que la inserción ha provocado que el subárbol que cuelga de Ai pasa a tener una altura 2 unidades mayor que el subárbol que cuelga de Ad. ¿Qué operaciones son

5

necesarias para que el nodo r tenga 2 subárboles que cumplan la propiedad de árboles AVL?.

Para responder a esto estudiaremos dos situaciones distintas que requieren 2 secuencias de operaciones distintas: La

Documentos relacionados

  • Educando al arbol pequeño
    2423 palabras | 10 páginas
  • árbol filogenético humano
    1296 palabras | 6 páginas
  • Arbol De Decision
    816 palabras | 4 páginas
  • Arbol de decisiones
    1147 palabras | 5 páginas
  • el arbol que no queria morir
    814 palabras | 4 páginas
  • Dia del arbol
    691 palabras | 3 páginas
  • Arbol de soluciones
    835 palabras | 4 páginas
  • EJERCICIO DE ARBOL DE DECISIONES 1
    976 palabras | 4 páginas
  • Casa Del Arbol
    2021 palabras | 9 páginas
  • Informe Del Test Del Arbol
    843 palabras | 4 páginas