Programa arbol

Capítulo 14

Árboles binarios equilibrados

Ejemplo 14.2
Rotación derecha-izquierda

Como se observa en la figura 14.6 al insertar el nodo con clave 6 en el arbol mostrado, se sigue el camino derecha de 4 e izquierda de 7 para terminar insertando por la derecha de 5. Al regresar por el camino de búsqueda los factores de equilibrio se incrementan en 1 si se fue por la rama derecha y sedecrementan en uno cuando se fue por la rama izquierda. En el nodo 4 el equilibrio se rompe, por lo que será necesario efectuar una rotación derecha-izquierda con la finalidad de restablecerlo. El nodo que ahora puede actuar como raiz es el antepenúltimo visitado en el camino de vuelta, es decir el 5 (figura 14.7)

Figura 14.6. Inserción de un elemento y actualización de los factores de equilibrioFigura 14.7. Rotación derecha-izquierda

PROBLEMAS RESUELTOS

14.11

#include
#include

typedef struct Arbol
{
int e;
struct Arbol* izq;
struct Arbol* der;
}arbol;

int vacio(arbol* a);
void recorreras(arbol * a, int n);
void arbolr(int n, arbol** a, FILE* f);

int main()
{
int n;
char pausa;
arbol* a;
FILE * f;

if ((f = fopen("arminimo.dat", "rt")) == NULL)
{
puts ("Error de apertura para lectura ");
exit(1);
}
//el primer entero es el número de nodos
fscanf (f, "%d", &n);
arbolr(n, &a, f);
fclose(f);
printf("Valores Nivel\n");
recorreras(a, 1);
pausa = getchar();
return 0;
}

void arbolr(int n, arbol** a, FILE* f)
{
int nizq;
int nder;

if (n == 0)
*a = NULL;
//no existen datos el árbol es vacío
else
{
nizq = n / 2; // nodos que van a la izquierda
nder = n - nizq - 1; // nodos que van a la derecha
*a = (arbol*)malloc(sizeof(arbol));
arbolr(nizq, &(*a)->izq, f);
fscanf(f,"%d ",&(*a)->e);
arbolr(nder, &(*a)->der, f);
}
}

int vacio(arbol* a)
{
return a == NULL;
}

void recorreras(arbol * a, int n)
{
if(! vacio(a))
{
recorreras(a->izq, n+1);
printf(" %d %d\n", a->e, n);
recorreras(a->der, n+1);
}
}

14.12.

#include
#include
#define True 1
#define False 0

typedef struct Arbol
{
int info;
struct Arbol* izq;
struct Arbol* der;
int Fe;
}arbol;
void inicializar(arbol ** a);
int vacio(arbol* a);
void insertar(arbol ** a, int e, int*sw);
void borrar(arbol ** a, int c, int* sw);
void buscar(arbol * a, int c, int* encontrado);
void recorreras(arbol * a);
void recorrerdes(arbol * a);
arbol* construir(arbol * a, int e, arbol* b);
void menor(arbol* a, int * e);
void eliminar( arbol ** a, int * sw);
void rotacioniisimple(arbol** a);
void rotacionddsimple(arbol** a);
void rotacioniddoble(arbol** a);
voidrotaciondidoble(arbol** a);
void actualizarizq(arbol** a, int* sw);
void actualizarder(arbol** a, int* sw);
void rotacionii2(arbol** a);
void rotaciondd2(arbol** a);
void actualizarbd(arbol** a, int* sw);
void actualizarbi(arbol** a, int * sw);
void dibujar(arbol* a, int h);

//Programa principal

int main()
{
int nm;
char pausa;
arbol* a;
int sw;

inicializar (&a);printf("Deme numero (0 -> Fin): ");
scanf("%d*c ", &nm);
while (nm !=0)
{
insertar(&a,nm,&sw);
dibujar (a, 0);
puts("");
printf("Deme numero (0 -> Fin): ");
scanf("%d*c ", &nm);
}
printf("Deme numero a borrar(0 -> Fin): ");
scanf("%d*c ", &nm);
while (nm !=0)
{
borrar(&a,nm,&sw);
dibujar (a, 0);
puts("");
printf("Deme numero aborrar(0 -> Fin): ");
scanf("%d%*c ", &nm);
}
pausa = getchar();
return 0;
}

void inicializar(arbol ** a)
{
*a = NULL;
}

int vacio(arbol* a)
{
return a == NULL;
}

void buscar(arbol * a, int c, int * encontrado)
{
if (vacio(a))
*encontrado = False;
else
if (a->info == c)
*encontrado = True;
else
if (a->info > c)
buscar(a->izq,...