Un àrbol en estructura de datos esuna emulaciòn en forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raìz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce comorama.

Arboles binarios

• Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
• Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
• Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura)
• A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad.

un árbol binario es un árbol en el que ningun nodo puede tener mas de dos subarboles. es un árbol binario, cada nodo puede tener, cero, uno o dos hijos(subarboles). se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Aquì un ejemplo de àbol binario en C++

//LISTA DOBLE CIRCULARES
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>

//Estructuras de arboles binarios
typedef struct arbolesBinarios
{
int dato;
struct  arbolesBinarios *izq;
struct arbolesBinarios *der;

}tipoNodo;

//PROTOTIPOS
tipoNodo *nuevo_elemento();
void crearraiz();
void presentar();
void insertar();
void insertarElem(tipoNodo *auxRaiz, tipoNodo *elem);
void inrden(tipoNodo *nodo);
void preorden(tipoNodo *nodo);
void postOrden(tipoNodo *nodo);
void inrdeninver(tipoNodo *nodo);
void preordeninver(tipoNodo *nodo);
void postOrdeninver(tipoNodo *nodo);
void todos();
void buscar(int num, tipoNodo *nodo);

void cuadro(int x1,int y1,int x2,int y2,char c);

tipoNodo *cabraiz;
//tipoNodo *cola;

tipoNodo *nuevo_elemento()
{
tipoNodo  *nodo1;
nodo1=(tipoNodo *)malloc(sizeof(tipoNodo ));
if(!nodo1)
cout<<”No se ha reservado memoria para el nuevo “;
return nodo1;
}

//MENU PRINCIPAL
void  main()
{
clrscr();
crearraiz();
int num;
clrscr();
char opc=’ ‘;

do
{

clrscr();
cuadro(1,10,35,56,’’);
gotoxy(13,3);cout<<”->[ LISTAS ENLAZADAS CIRCULARES ]<-\n”;
gotoxy(12,6);cout<<”    MENU PRINCIPAL\n”;
gotoxy(12,9); cout<<” [1]:  INSERTAR \n”;
gotoxy(12,12);cout<<” [2]:  MODIFICAR\n”;
gotoxy(12,15);cout<<” [3]:  BUSCAR\n”;
gotoxy(12,18);cout<<” [4]:  ORDENAR\n”;
gotoxy(12,21);cout<<” [5]:  ELIMINAR\n”;
gotoxy(12,24);cout<<” [6]:  PRESENTAR\n”;
gotoxy(12,27);cout<<” [7]:  PRESENTAR RECORRIDO\n”;
gotoxy(12,30);cout<<” [8]:  SALIR DEL MENU\n”;
gotoxy(12,33);cout<<” Elegir una Opci¢n [ ]“;
gotoxy(32,33);cin>>opc;

switch(opc)
{
case’1′:
clrscr();
insertar();getch();break;
/*  case’2′:
clrscr();
modificar();getch();break;*/
case’3′:
clrscr();
cout<<”INGRESE EL NUMERO A BUSCAR :”;
cin>>num;
buscar( num, cabraiz);getch();break;
/*   case’4′:
clrscr();
ordenar();getch();break;
case’5′:
clrscr();
eliminar();getch();break;*/

case’6′:
clrscr();
presentar();getch();break;
/* case’7′:
clrscr();
presentar_recorrido();getch();break; */
}

}while(opc!=’8′);

getch();

}

//CREAR LA RAIZ
void crearraiz()
{
clrscr();
int dat;
gotoxy(20,20);
cout<<”Ingrese Elemento:  “;
cin>>dat;
cabraiz=nuevo_elemento();
cabraiz->dato=dat;
cabraiz->der=NULL;
cabraiz->izq=NULL;
getch();
}

void insertar()
{
clrscr();
tipoNodo *elem;
//    tipoNodo *auxraiz;
elem=nuevo_elemento();
clrscr();
gotoxy(20,20);
cout<<”\t\t”<<”INGRESE VALOR  :\t”;
cin>>elem->dato;
elem->der=NULL;
elem->izq=NULL;
insertarElem(cabraiz,elem);
}

void insertarElem(tipoNodo *auxRaiz, tipoNodo *elem)
{

if(elem->dato>auxRaiz->dato)
{

if( auxRaiz->der==NULL)
{
auxRaiz->der=elem;

}
else
{
insertarElem( auxRaiz->der,  elem);
}
}
else
{
if( auxRaiz->izq==NULL)
{
auxRaiz->izq=elem;

}
else
{
insertarElem( auxRaiz->izq,  elem);
}

}

getch();

}

void buscar(int num, tipoNodo *nodo)
{
if(nodo!=NULL)
{
if(num==nodo->dato)
{

cout<<”OK”;
}
else
{

if(num>nodo->dato)
{
buscar(num, nodo->der);
}
else
{
buscar(num, nodo->izq);
}
}
}
else
{

cout<<”NO” ;
}

getch();
}

void presentar()
{
clrscr();
clrscr();
char opc=’ ‘;

do
{

clrscr();
cuadro(1,10,35,56,’’);
gotoxy(13,3);cout<<”->[ PRESENTAR ]<-\n”;
gotoxy(12,6);cout<<”    MENU PRINCIPAL\n”;
gotoxy(12,9); cout<<” [1]:  PRESENTAR EN ORDEN \n”;
gotoxy(12,12);cout<<” [2]:  PRESENTAR EN PREORDEN\n”;
gotoxy(12,15);cout<<” [3]:  PRESENTAR EN POST ORDEN\n”;
gotoxy(12,18);cout<<” [4]:  PRESENTAR EN ORDEN INVERSO \n”;
gotoxy(12,21);cout<<” [5]:  PRESENTAR EN PREORDEN  INVERSO \n”;
gotoxy(12,24);cout<<” [6]:  PRESENTAR EN POST ORDEN  INVERSO \n”;
gotoxy(12,27);cout<<” [7]:  PRESENTAR TODOS\n”;
gotoxy(12,30);cout<<” [8]:  REGRESAR\n”;

gotoxy(12,33);cout<<” Elegir una Opci¢n [ ]“;
gotoxy(32,33);cin>>opc;

switch(opc)
{
case’1′:
clrscr();
inrden(cabraiz);getch();break;
case’2′:
clrscr();
preorden(cabraiz);getch();break;
case’3′:
clrscr();
postOrden(cabraiz);getch();break;

case’4′:
clrscr();
inrdeninver(cabraiz);getch();break;

case’5′:
clrscr();
preordeninver(cabraiz);getch();break;

case’6′:
clrscr();
postOrdeninver(cabraiz);getch();break;

case’7′:
clrscr();
todos();getch();break;

}
}while(opc!=’8′);

getch();

}

void inrden(tipoNodo *nodo)
{
if(nodo!=NULL)
{
inrden(nodo->izq);
cout<<nodo->dato;
cout<<”\t”;
inrden(nodo->der);
}
getch();
}

void inrdeninver(tipoNodo *nodo)
{
if(nodo!=NULL)
{
inrdeninver(nodo->der);
cout<<nodo->dato;
cout<<”\t”;
inrdeninver(nodo->izq);
}
getch();
}
void preorden(tipoNodo *nodo)
{
if(nodo!=NULL)
{
cout<<nodo->dato;
cout<<”\t”;
preorden(nodo->izq);
preorden(nodo->der);
}
getch();
}
void preordeninver(tipoNodo *nodo)
{
if(nodo!=NULL)
{
preordeninver(nodo->der);
preordeninver(nodo->izq);
cout<<nodo->dato;
cout<<”\t”;

}
getch();
}
void postOrden(tipoNodo *nodo)
{
if(nodo!=NULL)
{
postOrden(nodo->izq);
postOrden(nodo->der);
cout<<nodo->dato;
cout<<”\t”;

}
getch();
}

void postOrdeninver(tipoNodo *nodo)
{
if(nodo!=NULL)
{
cout<<nodo->dato;
cout<<”\t”;
postOrdeninver(nodo->der);
postOrdeninver(nodo->izq);

}
getch();
}
void todos()
{
cout<<”\t\t** # INORDENADOS**”;
cout<<”\n\n”;
inrden(cabraiz);
cout<<”\n\n\n”;
cout<<”\t\t ** # PREORDENADOS**”;
cout<<”\n\n”;
preorden(cabraiz);
cout<<”\n\n\n”;
cout<<”\t\t ** # POSTORDENADOS**”;
cout<<”\n\n”;
postOrden(cabraiz);
cout<<”\n\n\n”;
cout<<”\t\t ** # INORDENADOSIN**”;
cout<<”\n\n”;
inrdeninver(cabraiz);
cout<<”\n\n\n”;
cout<<”\t\t ** # PREORDENADOSIN**”;
cout<<”\n\n”;
preordeninver(cabraiz);
cout<<”\n\n\n”;
cout<<”\t\t ** # POSTORDENADOSIN **”;
cout<<”\n\n”;
postOrdeninver(cabraiz);
}

void cuadro(int x1,int y1, int x2, int y2, char simb)
{
for (int i1=y1;i1<=y2;i1++)
{
gotoxy(i1,x1);cout<<simb;
gotoxy(i1,x2);cout<<simb;
}
for (int i2=x1;i2<=x2;i2++)
{
gotoxy(y1,i2);cout<<simb;
gotoxy(y2,i2);cout<<simb;
}
}