Download Arboles enhebrados

Á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
G
struct nodetype {
int info;
info;
struct nodetype *lefth;
lefth;
struct nodetype *right;
right;
int rthread;
/* campo extra */
rthread;
C
B
H
E
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