Ejercicios "amistosos"
Árboles
Un árbol es una estructura de datos jerárquica compuesta de elementos u objetos llamados nodos, de los cuales, el principal se llama raíz. Entre los nodos se crea una relación o parentesco generando términos como padre, hijo, hermano, sucesor, antecesor, ancestro, hoja, nodo no terminal, camino, longitud, nivel, grado de un nodo, altura, peso...
Los árboles se utilizan en la programación de hojas de cálculo o en Inteligencia Artificial. Cada nodo del árbol se define como una variable mediante la siguiente estructura dinámica:
struct arbol{ // estructura de arbol binario
int clave; // variable que indica el valor del nodo
arbol *izquierda;
arbol *derecha;
};
Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque es su característica inherente. La mayoría de las funciones utilizadas por estas estructuras de datos son recursivas (cada subárbol es un árbol). Los árboles enearios son estructuras usadas principalmente para guardar información donde cada padre debe tener un número indeterminado de hijos.
En computación, una de las estructuras de datos más importantes es la conocida como árboles binarios. En un árbol binario cada nodo puede tener como máximo dos subárboles, el subárbol izquierdo y el subárbol derecho. Tienen especiales aplicaciones porque permiten búsquedas, inserciones y borrados rápidos. Existen dos formas tradicionales de representar un árbol binario en memoria: Por medio de variables dinámicas (punteros) y por medio de arreglos.
El recorrido de un árbol binario es una de las operaciones más importantes. Esto implica visitar los nodos del árbol una sola vez. Hay tres formas diferentes de recorrer un árbol: Preorden, Inorden y Postorden.
void
lista_preorden(Arbol *aux){
if (!aux){
cout << "El Arbol vacio!";return;}
cout << aux->info<<" ";
lista_preorden(aux->izq);
lista_preorden(aux->der);
}
void lista_inorden(Arbol *aux){
if (!aux){
cout << "El Arbol vacio!";return;}
lista_inorden(aux->izq);
cout << aux->info<<" ";
lista_inorden(aux->der);
}
void lista_postorden(Arbol *aux){
if (!aux){
cout << "El Arbol vacio!";return;}
lista_postorden(aux->izq);
lista_postorden(aux->der);
cout << aux->info<<" ";
}
TERMINOLOGÍA
IMPORTANTE EN ÁRBOLES
Altura: Distancia en arcos de la raíz al nodo más lejano del
árbol.
Árbol balanceado AVL: Tiene la propiedad de que la altura de la
rama
izquierda menos la altura de la rama derecha difiere en máximo 1.
Árbol binario: Árbol homogéneo en el que el máximo número de
sub-árboles que salen de cualquiera de sus nodos es 2.
Árbol binario de búsqueda: Para todo nodo N del árbol se debe
cumplir
que todos los valores de los nodos del sub-árbol izquierdo de N deben
ser menores o iguales al valos del nodo N. De igual forma, todos los
valores de los nodos del sub-árbol derecho de N deben ser mayores o
iguales al valor del nodo N.
Árbol completo: Todos sus nodos terminales tienen la misma
altura.
Árbol homogéneo: Todos sus nodos tienen la misma estructura.
Árboles N-arios: Se denominan de acuerdo con el número de sub-árboles
que salen de los nodos; binarios, ternarios, cuaternarios, y en
general, árboles N-arios.
Árbol ordenado: Se caracteriza porque la posición relativa de
los
sub-árboles es fija, es decir, no se pueden intercambiar.
Camino: Un árbol siempre se examina hacia abajo. Un camino es el
conjunto de nodos que se tienen que visitar para llegar a un nodo
específico.
Factor de balance: Indica para cada nodo, la diferencia de altura
entre
su sub-árbol izquierdo y su sub-árbol derecho.
Grado: Número de sub-árboles que salen o entran de un nodo.
Longitud: Número de nodos que se deben recorrer para pasar de
un nodo a otro.
Nivel: Nodos del árbol se pueden relacionar con sus inmediatos
sucesores y antecesores. A la raíz se asigna el nivel cero, los inmediatos
sucesores de un nodo tienen un nivel más que éste.
Nodo terminal: Aquel que no tiene sucesores. También se denomina
hoja.
Peso: El peso del árbol en un nodo dado es el número de nodos
en el
árbol sin contarse el nodo dado.
Rama: Camino que parte del nodo raíz y termina en una hoja.
Recorrido: Suma de las distancias, medidas en arcos, de la raíz a
cada
uno de los nodos.
ORDENAMIENTO CON ÁRBOLES
Existen varios algoritmos de ordenamiento que usan la estructura de
árbol y en especial la de los árboles binarios. En general, estos
algoritmos son más eficientes que los que emplean listas. El número de
comparaciones es directamente proporcional a la altura del árbol y al
número de nodos.
Método de Foster: Uno de los algoritmos más usados para el proceso
de ordenamiento. Para su implementación usa árboles AVL y consta de dos
pasos:
Primer paso: Se forma un árbol binario AVL de acuerdo con las sigtes.
normas:
<> El primer elemento que entre es la raíz.
<> Cualquier nuevo elemento se compara con la raíz, de forma recursiva,
hasta encontrar su posición.
<> Si el elemento es menor o igual a la raíz se coloca en el sub-árbol
izquierdo.
<> Si el elemento es mayor que la raíz se coloca en el sub-árbol
derecho.
<> Si el árbol está sesgado se pueden usar algoritmos de balanceo para
corregirlo.
Segundo paso: Una vez conformado el árbol, se recorre en inorden y se
obtiene la lista ordenada.
Ordenar la siguiente lista: 40 15 62 10 35 51 70 5 77 55 39 18
Método de Floyd: El método se basa en la estructura de árbol
binario y
se desarrolla en dos pasos. En el primer paso se construye un árbol
binario de forma balanceada (AVL), por niveles de acuerdo con las
siguientes normas, si el ordenamiento es descendente:
<> El valor contenido en un nodo raíz debe ser menor o igual al valor
contenido en cualquier nodo de sus sub-árboles.
<> El árbol se va construyendo por niveles y para la entrada de cualquier
nuevo elemento se comienza a comparar por la raíz.
<> Si el nuevo elemento es mayor que la raíz se desciende al siguiente
nivel, a comparar, hasta que se encuentre la posición, en la cual
quede correctamente ubicado.
<> Si la raíz es mayor que el nuevo elemento éste queda en la raíz, y
el elemento que estaba en ésta pasa al siguiente nivel para continuar
el proceso de comparación hasta que encuentre la posición correcta.
Una vez construido el árbol se procede a efectuar el segundo paso, que
tiene por objetivo obtener de la siguiente manera los valores ordenados
ascendentemente:
<> El elemento de menor valor está en la raíz y es el primero que pasa
a la lista de salida.
<> La posición en la raíz del árbol que tenía el elemento que salió,
la ocupa el que tenga el menor valor de los inmediatos sucesores.
<> La posición en el árbol que tenía el elemento que cambia de nivel,
la ocupa el que tenga el menor valor de los inmediatos sucesores.
<> El proceso continúa de manera iterativa con la salida de los elementos
hasta cuando se desocupe el árbol.
Este método se puede desarrollar en memoria mínima si se toma como base un
arreglo en el cual se construye el árbol.
CAMBIO DE NOTACIÓN EN EXPRESIONES ALGEBRAICAS
El cambio de notación en expresiones algebraicas se puede desarrollar
mediante el recorrido del árbol binario que represente la expresión.
Un recorrido del árbol en preorden genera una notación pre-fijo:
= - * - ABC / + D E F Y
Al recorrer el árbol en inorden, se genera una notación in-fijo:
A - B * C - D + E/F = Y
El recorrido del árbol en postorden genera una notación post-fijo:
AB - C * DE + F / - Y =
***********************************************************************
// El siguiente programa permite insertar un valor n
en un árbol binario.
#include "iostream.h"
#include "conio.h"
#define T 20
#define L clrscr()
struct nodo{ // estructura de arbol binario
int info;
nodo *izq;
nodo *der;
};
struct LIFO{ // estructura tipo pila
int t;
nodo *a[T];
};
leer_numero(){
int n; L;
cout << "Entrada de datos para el ARBOL"<<endl;
cout << "Digite un numero entero. Para salir, teclee -1 : ";
cin >> n;
return(n);
}
void insertar_izq(nodo *p,int n){
nodo *nuevo;
nuevo=new(nodo);
nuevo->info=n;
nuevo->izq=NULL;
nuevo->der=NULL;
p->izq=nuevo;
}
void insertar_der(nodo *p,int n){
nodo *nuevo;
nuevo=new(nodo);
nuevo->info=n;
nuevo->izq=NULL;
nuevo->der=NULL;
p->der=nuevo;
}
void inicia_pila(LIFO *p){
p->t=0;
}
pila_vacia(LIFO *p){
return(!p->t);
}
void inserta_pila(LIFO *p,nodo *s){
if (p->t == T){
cout << "La pila ya esta llena!"<<endl;getch();}
else{
p->t++;
p->a[p->t-1]=s;}
}
void saca_pila(LIFO *p,nodo **s){
if(pila_vacia(p)){
cout << "La pila esta vacia!"<<endl;
*s=NULL;getch();}
else{
*s=p->a[p->t-1];
p->t--;}
}
void listar_preorden(nodo *p){
// Imprime el arbol en preorden utilizando una PILA
LIFO pila;
inicia_pila(&pila);
L;
cout << "Contenido del Arbol..."<<endl;
while(p){
cout << p->info<<" ";
inserta_pila(&pila,p);
p=p->izq;
}
while(!pila_vacia(&pila)){
saca_pila(&pila,&p);
p=p->der;
while(p){
cout << p->info<<" ";
inserta_pila(&pila,p);
p=p->izq;
}
}
}
void crearbol(){
nodo *p,*q,*raiz; int n;
n=leer_numero();
raiz=new(nodo);
raiz->info=n;
raiz->izq=NULL;
raiz->der=NULL;
n=leer_numero();
while(n!=-1){
q=p=raiz;
while(q!=NULL && p->info != n){
p=q;
if(n < p->info)
q=q->izq;
else
q=q->der;
}
if (p->info == n){
cout << "Numero ya existe!!!"<<endl;getch();}
else if (n < p->info)
insertar_izq(p,n);
else
insertar_der(p,n);
n=leer_numero();
}
listar_preorden(raiz);
}
void main()
{
crearbol();
getch();
}
1.) Escriba un programa para crear su árbol genealógico, imprimirlo en inorden y determinar cúantos nodos tiene el árbol.
2.) Codifique una función que reciba un puntero a un nodo y retorne el valor 1 si ese nodo es la raíz de un árbol binario y 0 en caso contrario.
3.) Escriba una función que acepte un puntero a un árbol binario y un puntero a un nodo del árbol, y retorne el nivel del nodo en el árbol.
4.) Implemente una función que reciba tres datos: la raíz de un árbol binario y dos datos de tipo entero a y b. La función debe devolver 1 si entre a y b existe un camino, o 0 en caso contrario. Suponga que en el árbol no existen datos repetidos y el árbol no está ordenado.
5.) Desarrolle una función que reciba la raíz de un árbol binario y devuelva 1 si el árbol es completo ó 0 de lo contrario.
6.) Escriba una función que reciba las raíces de dos árboles binarios y devuelva 1 si estos árboles son iguales ó 0 en caso contrario.
7.) Codifique una función que
reciba la raíz de un árbol binario ordenado y un dato n. La función
debe devolver la dirección del padre de n o null en caso de
que n sea la raíz o n no esté en el árbol.
