ÁRBOLES

1) ÁRBOLES

Un árbol es una estructura de datos dinámica (las estructuras del árbol pueden cambiar durante la ejecución del programa) no lineal (puesto que a cada elemento del árbol puede seguirle varios elementos) y homogénea en el que cada elemento puede tener varios elementos posteriores y solamente un elemento anterior. Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, de los cuales uno es conocido como raíz, además se crea una relación de parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc.

Un árbol es una estructura que está compuesta por un dato y varios árboles. Dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente, es decir un nodo cualquiera puede ser considerado como la raíz de una árbol completo.

Ejemplo:

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<string.h>

struct nodoarbol{ //ESTRUCTURA DEL ARBOL

struct nodoarbol *izqnodo;

int info;

struct nodoarbol *dernodo;

};

typedef struct nodoarbol NODO; //DEFINICION DE TIPO NODO

typedef NODO *ARBOL; //DECLARACION DE VARIABLE PUNTERO A NODO

void insertanodonuevo(ARBOL *,int); //DECLARACION DE FUNCIONES

void inorden(ARBOL);

void preorden(ARBOL);

void postorden(ARBOL);

void treefree(ARBOL);

main(){

int i;

char newnod,chain[200],elementos;

clrscr();

ARBOL raiz=NULL; //DECLARACION DE VARIABLE DE TIPO ARBOL

printf("\n\n\tIntroduzca una cadena de caracteres (max. 200 elementos):\n");

gets(chain);

elementos=strlen(chain);

for(i=1;i<=elementos;i++) {

newnod=chain[i-1];

insertanodonuevo(&raiz,newnod);

}

printf("\n\n preorden ¯¯\t");

preorden(raiz); //LLAMADO A FUNCION DE RECORRIDO EN PREORDEN

printf("\n\n inorden ¯¯\t");

inorden(raiz); //LLAMADO A FUNCION DE RECORRIDO EN INORDEN

printf("\n\n postorden ¯¯\t");

postorden(raiz); //LLAMADO A FUNCION DE RECORRIDO EN POSTORDEN

getch();

treefree(raiz); //LIBERACION DE MEMORIA DEL ARBOL.

raiz=NULL; //ASIGNACION DE UN VALOR NULO A LA RAIZ.

return 0;

}

void insertanodonuevo(ARBOL *rarbol,int nuevo){

if(*rarbol==NULL){ //CREACION DE UN NUEVO NODO

*rarbol=(NODO *)malloc(sizeof(NODO));

if(*rarbol!=NULL){

//ASIGNACION DE VALORES NUEVOS EN EL NODO NUEVO

(*rarbol)->info=nuevo;

(*rarbol)->izqnodo =NULL;

(*rarbol)->dernodo=NULL;

}

else{printf("\n¬¬¬¬ Memoria No Disponible !!!!\n");}

}

else

if(nuevo<(*rarbol)->info) //checa si el elemento nuevo es mayor que el elemento padre

insertanodonuevo(&((*rarbol)->izqnod… //coloca el elemento a la izquierda del padre o raiz

else

if(nuevo>(*rarbol)->info) //checa si el elemento nuevo es menor que el elemento padre

insertanodonuevo(&((*rarbol)->derno… //coloca el elemento a la derecha del padre o raiz

}

void preorden(ARBOL rarbol){

if(rarbol!=NULL){

printf(" %c ",rarbol->info);

preorden(rarbol->izqnodo);

preorden(rarbol->dernodo);

}

}

void inorden(ARBOL rarbol){

if(rarbol!=NULL){

inorden(rarbol->izqnodo);

printf(" %c ",rarbol->info);

inorden(rarbol->dernodo);

}

}

void postorden(ARBOL rarbol){

if(rarbol!=NULL){

postorden(rarbol->izqnodo);

postorden(rarbol->dernodo);

printf(" %c ",rarbol->info);

}

}

void treefree(ARBOL rarbol){

if(rarbol!=NULL){

treefree(rarbol->izqnodo);

treefree(rarbol->dernodo);

free(rarbol);

}

}

2) NODO RAÍZ

Los nodo raíz o, sencillamente, raíz. La información la almacenaremos en dichos nodos, de los cuales a su vez pueden colgar otros nodos es el único nodo del árbol que no tiene padre este es el nodo que usaremos para referirnos al árbol.

Ejemplo:

typedef struct nodo

{

int dato; //datos guardado

NODO *liga_izq; //liga para el hijo izquierdo

NODO *liga_der; //liga para el hijo derecho

}NODO;

Así se crean tos nodos, iniciando con la raíz:

NODO raíz = new NODO;

raiz.dato=80;

raiz.liga_izq=NULL;

raiz.liga_der=NULL;

luego se crean los hijos

//funcion para agregar un nodo

void agregar_nodo(int dato, NODO nodo_padre)

{

NODO nuevo_nodo = new NODO;

nuevo_nodo.dato = dato;

//tomar este criterio es para que el árbol este ordenado, cuando se haga el recorrido:

if (nodo.dato < nodo_padre.dato){

nodo_padre.liga_izq = nuevo_nodo;

nodo_padre.liga_der = NULL;

{

else

if (nodo.dato > nodo_padre.dato){

nodo_padre.liga_izq = NULL;

nodo_padre.liga_der = nuevo_nodo;

}

//nota: si el dato es igual al padre, no agregar, ya que es el mismo nodo

}

//ejemplo para agregar un nodo al árbol desde la raíz:

agregar_nodo(35, raiz);

//ejemplo para agregar un nodo al hijo izquierdo de la raiz:

agregar_nodo(12, raiz->liga_izq);

3) NODO HOJA

Nodo que no tiene hijos se llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).

Ejemplo si se quiere borrar un nodo hoja

• En el árbol de ejemplo, borrar el nodo 3.1.

• Localizamos el nodo a borrar, al tiempo que mantenemos un puntero a'Padre'.2.

• Hacemos que el puntero de 'Padre' que apuntaba a 'nodo', ahora apunte aNULL.3.

• Borramos el 'nodo'.

4) NODO PADRE

Cualquiera de los nodos apuntados por uno de los nodos del árbol. En la figura, el nodo 'A' es padre de 'B', 'C' y 'D'.

5) NODO HIJO

Nodo que

...