Reconocimiento de un arbol rojinegro

Solo disponible en BuenasTareas
  • Páginas : 5 (1098 palabras )
  • Descarga(s) : 0
  • Publicado : 29 de octubre de 2010
Leer documento completo
Vista previa del texto
//Aguilar Avila Hugo Alberto.

Esta es un programa que hice de tarea para reconocer si un árbol dado es rojinegro o no
Las entradas se deben leer desde archivo como el siguiente y dar un resultado en el siguiente formato
Entrada 1 | Salida 1 | Entrada 2 | Salida 2 |
7
0 0 0
1 1 5
1 0 0
1 0 0
0 4 3
0 7 2
0 0 0 | 1
4
1 3 4 7 | 7
1 0 0
1 1 5
1 0 0
0 0 0
1 4 3
0 7 2
0 0 0 |0
3
1 3 5 |

Bueno espero les sirva, en caso de duda o comentario les responderé con gusto en hugoaguilar8@hotmail.com .

#include <iostream>
#include <fstream>
#include <cstdlib>
#define fil 100
#define col 4
using namespace std;

int llenaMatriz(int matriz[fil][col]);
int cabeza(int Matriz[fil][col], int filas);
void esrojinegro(int Matriz[fil][col], intfilas, int cab);
int rojos(int Matriz[fil][col], int filas, int aux[fil][col]);
int nodosMal(int aux[fil][col], int fil2, int Mal[fil]);
bool busca(int aux[fil][col], int fil2, int num);
bool veriNegros(int Matriz[fil][col], int filas, int cab, int &hoja);
int HoPa(int hoja, int Matriz[fil][col], int filas, int cab);
int buscaDese(int nodo, int Matriz[fil][col], int cab, int filas);void Seleccion_directa(int A[], int N);

int main()
{
int Matriz[fil][col];
int filas=0, cab=0;
filas=llenaMatriz(Matriz);
cab=cabeza(Matriz, filas);
esrojinegro(Matriz, filas, cab);
return 0;
}

//____________________________________________________________

__________________
int llenaMatriz(int matriz[fil][col])
{
ifstream entrada;
int i=0, j=1,fila=0;

entrada.open ("entrada1.txt");
if(!entrada.fail())
{
entrada>>fila;
while((!entrada.eof())&&(i<fila))
{
matriz[i][0]=i+1;
for(j=1; j<col; j++)
{
entrada>>matriz[i][j];
}
i++;
}entrada.close();
return fila;
}
else
{
exit(1);
}
}

//____________________________________________________________

__________________
int cabeza(int Matriz[fil][col], int filas)
{
int cabe=Matriz[0][0];
int i=0, j=2, band=-1;

for(int fils=0; (fils<filas)&&(band==-1); fils++)
{
i=0;while((cabe!=Matriz[i][2])&&(cabe!=Matriz[i][3])&&(i<filas))
{
i++;
}
if(((cabe==Matriz[i][2])||(cabe==Matriz[i][3]))&&(i<filas))
{
cabe=Matriz[fils+1][0];
band=-1;
}
else
band=1;

}
return cabe;
}
//______________________________________________________________________________
void esrojinegro(int Matriz[fil][col], int filas, int cab)
{
if(Matriz[cab-1][0]==1) //manejo del caso en que el nodo padre sea rojo
{
ofstream salida;
salida.open("Res.txt");
if(salida.fail())
{
cout<<"EL ARCHIVO DE SALIDA NO SE PUDO ABRIR\n";exit(1);
}
else
{
salida<<0<<"\n";
salida<<0<<"\n";
salida<<0<<"\n";
for(int i=0; i<filas; i++)
salida.close();
}
}
else//busqueda de la condicion 2 si se cumple o no
{
int aux[fil][col];
int fil2=0;
fil2=rojos(Matriz, filas, aux);
int Mal[fil2], nodos=0;
nodos=nodosMal(aux, fil2, Mal);
Seleccion_directa(Mal, nodos);

if(nodos!=0)
{
ofstream salida;
salida.open("Res.txt");
if(salida.fail())
{...
tracking img