• Author / Uploaded
• Erika

Citation preview

ÁRBOLES ENHEBRADOS. • • • • •

INTRODUCCIÓN. DEFINICIÓN. EJEMPLOS. IMPLEMENTACIONES. CONCLUSIONES. CONCLUSIONES.

INTRODUCCIÓN • En este tema se tratara de mostrar una mejor implementación de árboles aprovechando ese espacio para mantener un encadenamiento adicional que permita a algunas operaciones propias de los árboles. Moverse con mayor facilidad y tratar de usar menos memoria.

ÁRBOLES ENHEBRADOS (Por la derecha)

• HEBRA: Apuntador a su sucesor (en orden ), en lugar de NULL. A A

B A

C A

INTRODUCCIÓN • En las exposiciones pasadas pudimos observar los códigos de diferentes tipos de árboles, en los cuales a la hora de realizar los recorridos se pierde tiempo y memoria al indicar en el recorrido que un subárbol se encuentra vacío.

DEFINICIÓN: • Se define como el árbol binario que esta tanto a la derecha como a la izquierda. • En otras palabras quiere decir que tienen apuntadores llamados hebras que apuntan a sus sucesores y antecesores respectivamente.

IMPLEMENTACIÓN • Todas las hojas y nodos sin subárbol derecho tienen un apuntador hacia su sucesor en el árbol en su recorrido en orden. • Para distinguir si el apuntador va a un hijo o a un sucesor en orden, se requiere un campo adicional en cada nodo, que indique este hecho.

1

EJEMPLOS :

Implementación de lo anterior.

A A

B D

C F

E

D

E G

struct nodetype { int info; info; struct nodetype *lefth; lefth; struct nodetype *right; right; int rthread; /* campo extra */ rthread;

C

B

H

I

I

H

G

F J

K

L

} Árboles binarios enhebrados por la derecha.

• Rutina para implantar el recorrido en orden de un árbol binario enhebrado por la derecha. intrav3(tree intrav3(tree)) NODEPTR tree; tree; { NODEPTR p, q; p = tree; tree; do{

p = q ->right; right; while( while( q ->rthread && p != NULL) { printf (“%d\ (“%d\n”, pp->info); q = p; p = pp->right; right; } } }while( while( q != NULL); }

typedef struct nodetype *NODEPTR;

q = NULL; While (p != NULL) { q = p; p = pp->left; left; } if (q != NULL) { printf (“%d\ (“%d\n”, q ->info);

Implementación para la creación de un árbol : NODEPTR crea_arbol (x) { int x; NODEPTR p; p = GetNode (); p->info = x; p->left = NULL; p->rigth = NULL; p->rthread = TRUE; return p; }

2

• Setleft (p , x) NODEPTR p; int x; { if (p == NULL) error (“inserción no efectuada”); else if(p ->left != NULL) error (“inserción no válida”); else { q = getnode(); getnode(); q->info = x; p->left = q; q->left = NULL; q->right = p; q->tthread = TRUE; } }

• setright(p, setright(p, x) NODEPTR p; { int x; NODEPTR q, r; if(p == NULL) printf(“inserción printf(“inserción no efectuada”); else if(!p if(!p-->rthread) rthread) printf(“iserción printf(“iserción inválida”); else{ else{ q = GetNode(); GetNode(); q->info = x; r = pp->right; right; p->right = q; p->rightread = FALSE; q->left = NULL; q->right = r; q->rthread = read = TRUE; } }

CONCLUSIONES • Los árboles enhebrados se utilizan para el mejor aprovechamiento de la memoria. • Sus ventajas principales son: • No se requiere el uso de pilas para el recorrido de dichos árboles. • El recorrido en orden puede hacerse de manera iterativa. Por lo tanto no se necesita el uso de la recursividad para realizar los recorridos.

3