ARBOLES BINARIOS
Un árbol binario es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno.Los arboles como máximo pueden tener dos nodos hijo.
15 NODO RAIZ
1,4,7,12,17,24 NODOS HOJA
5,2,9,18,20 NODOS RAMAS
Definicion de un arbol binario como estructura
#include <stdio.h>
#include <conio.h>
struct nodo {
int info;
struct nodo *izq;
struct nodo *der;
};
//DEFINIMOS ESTRUCTURA
typedef struct nodo arbol;
void ins_izq(arbol *,char); //NODO IZQUIERDO
void ins_der(arbol *,char); //NODO DERECHO
//DIFERENTES RECORRIDOS EXPLICADOS MAS ABAJO
void inOrden( arbol*);
void preOrden( arbol*);
void postOrden( arbol*);
void imp_arbol( arbol *,int, int);
void main () {
struct nodo *raiz,*q;
int x,y;
//ASIGNACION DE VALOR EN NODO RAIZ
raiz=new arbol;
raiz->info=30;
raiz->izq=NULL;
raiz->der=NULL;
//ASIGNACION DE VALORES A NODO IZQUIERDO DERECHO Y HIJOS
ins_izq(raiz,25 );
ins_der(raiz, 42);
q=raiz->izq;
ins_izq(q, 21);
ins_der(q, 29);
q=raiz->izq->izq;
ins_izq(q, 19);
ins_der(q, 22);
q=raiz->izq->izq->izq;
ins_izq(q, 18);
q=raiz->izq->izq->izq->izq;
ins_izq(q, 16);
q=raiz->izq->izq->izq->izq->izq;
ins_izq(q, 15);
q=raiz->izq->izq->izq->izq->izq->izq;
ins_izq(q, 5);
q=raiz->izq->izq->izq->izq->izq->izq->izq;
ins_der(q, 8);
q=raiz->der;
ins_izq(q, 32);
ins_der(q, 60);
q=raiz->der->izq;
ins_izq(q, 31);
ins_der(q, 40);
q=raiz->der->izq->der;
ins_izq(q, 33);
q=raiz->der->der;
ins_izq(q, 43);
q=raiz->der->der->izq;
ins_der(q, 51);
q=raiz->der->der->izq->der;
ins_der(q, 56);
q=raiz->der->der->izq->der->der;
ins_izq(q, 52);
preOrden (raiz);
printf("\n\n");
inOrden(raiz);
printf("\n\n");
postOrden(raiz);
getchar();
//clrscr();
x=40;
y=15;
x y Y UBICACION EN PANTALLA DE ARBOL
imp_arbol( raiz, x, y);
getchar();
} //fin main
//insertar izquierda
void ins_izq(struct nodo *p,char n){ //PROCEDIMIENTO DE INSERTADO
arbol *nuevo;
nuevo=new arbol;
nuevo->info=n;
nuevo->izq=NULL;
nuevo->der=NULL;
p->izq=nuevo;
}
//insertar derecha PREORDEN HOJAS NIVEL POSORDEN
void ins_der(struct nodo *p,char n){
arbol *nuevo;
nuevo=new arbol;
nuevo->info=n;
nuevo->izq=NULL;
nuevo->der=NULL;
p->der=nuevo;
}
////////////////////////////////////////////////////////////////////////////
void imp_arbol( arbol *ptrArbol,int x,int y ){ IMPRECION DE ARBOL EN EJES X Y
if ( ptrArbol!=NULL){
gotoxy(x,y);
printf("%d",ptrArbol->info);
x=x-3;
y=y+3;
imp_arbol( ptrArbol->izq,x,y);
x=x+6;
imp_arbol( ptrArbol->der,x,y);
y=y-3;
}
}
RECORRIDO DE ARBOLES BINARIOS
INORDEN(izquierdo, raíz, derecho).
Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
- Atraviese el sub-árbol izquierdo
- Visite la raíz
- Atraviese el sub-árbol derecho
void inOrden (arbol *ptrArbol){
printf("");
if (ptrArbol != NULL){
inOrden (ptrArbol->izq);
printf("%d ",ptrArbol->info);
inOrden(ptrArbol->der);
}
}
PREORDEN (raíz, izquierdo, derecho).
Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:
- Visite la raíz
- Atraviese el sub-árbol izquierdo
- Atraviese el sub-árbol derecho
void preOrden (arbol *ptrArbol){
printf("");
if (ptrArbol != NULL){
printf("%d ",ptrArbol->info);
preOrden (ptrArbol->izq);
preOrden(ptrArbol->der);
}
}
POS ORDEN (izquierdo, derecho, raíz).
Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones en cada nodo:
- Atraviese el sub-árbol izquierdo
- Atraviese el sub-árbol derecho
- Visite la raíz
void postOrden (arbol *ptrArbol){
if (ptrArbol != NULL){
preOrden (ptrArbol->izq);
preOrden(ptrArbol->der);
printf("%d ",ptrArbol->info);
}
}
0 comentarios: