Ejemplo 20. ejemplo 20. 2 completo lleno ejemplo 20. 3



Descargar 102.42 Kb.
Fecha de conversión10.01.2017
Tamaño102.42 Kb.
EJEMPLO 20.1. .



EJEMPLO 20.2



completo lleno


.

EJEMPLO 20.3






Árbol de expresión (X+Y)*(A-B)

Árbol de expresión (X+(Y*Z))+(A-B)



EJEMPLO 20.4








(A+B)*C

A+B*(-(C+D))

(A*(X+Y))*C



EJEMPLO 20.5







Preorden

Inorden

Postorden


EJEMPLO 20.6.










Ejemplo 20.7 .



EJEMPLO 20.8






EJEMPLO 20.9







EJEMPLO 20.10..







EJEMPLO 20.11.







EJERCICIO 20.1

La primera estructura no es un árbol binario ya que el nodo cuyo contenido es B tiene tres hijos y le máximo número de hijos de un árbol binario es dos. Esta estructura es un un árbol general. La segunda no es un árbol binario porque hay dos caminos distintos para ir al nodo F y por tanto no se expresa la jerarquía de la definición de árbol un árbol en general y de un binario en particular. La tercera por la misma razón que la segunda no es un árbol binario.


EJERCICIO 20.2
a) Su altura es cuatro.

b) El árbol está equilibrado ya que la diferencia de las alturas de los subárboles izquierdo y derecho es como máximo uno.

c) Los nodos hoja son: W, T, X, V.

d) El predecesor inmediato (padre) del nodo U es el nodo que contiene R.

e) Los hijos del nodo R son U y V.

f) Los sucesores del nodo R son U, V, X.


EJERCICIO 20.3

  1. Recorrido RDI : P, R, V, U, X, Q, T, S, W.

  2. Recorrido DRI : V, R, X, U, P, T, Q, S, W.

  3. Recorrido DIR : V, X, U, R, T, W, S, Q.


EJERCICIO 20.4






I

II





III

IV

b) los recorridos en inorden, preorden y postorden de cada uno de los árboles son:




Inorden: E, M, R, T, Y

Preorden: M, E, Y, T, R

Prostorden: E, R, T, Y, M

I


Inorden: E, M, R, T, Y

Preorden: R, E, M, Y, T

Prostorden: M, E, T, Y, R

II


Inorden: E, M, T, R,Y

Preorden: T, M, E, Y, R

Prostorden: E, M, R, Y, T

III


Inorden: A, C, E, F, K, L, N, O, R, S

Preorden: C, A, O, N, F, E, L, K, R, S

Prostorden: A, E, K, L, F, N, S, R, O, L

IV



EJERCICIO 20.5:













EJERCICIO 20.6.


PROBLEMA 20.1
typedef int Telemento;

class Nodo;

class Arbol

{

protected:

Nodo *a; // puntero a la clase Nodo

public:

Arbol Ohi(); // Obtener hijo izquierdo

Arbol Ohd(); // Obtener hijo derecho

Arbol Phi(Arbol a1); // Poner hijo izquierdo

Arbol Phd(Arbol a1); // Poner hijo derecho

Telemento Oraiz(); // Obtener elemento raíz



void Praiz(Telemento e1); // Poner elemento raíz

Arbol(); // constructor

~ Arbol(); //destructor

};
class Nodo

{

private:

Telemento e; // elemento que se almacena

Arbol hi, hd; // hijo izquierdo y derecho son árboles

friend class Arbol; // Arbol es clase amiga de Nodo

public:

Nodo (Arbol ai, Telemento x, Arbol ad); // contructor

~ Nodo(){}; //destructor

};


Arbol Arbol::Ohi()

{

return a->hi;

};
Arbol Arbol::Ohd()

{

return a->hd;

};
Arbol Arbol::Phi(Arbol a1)

{

a->hi = a1;



};
Arbol Arbol::Phd(Arbol a1)

{

a->hd = a1;



};

Telemento Arbol::Oraiz()

{

return a->e;

};
void Arbol::Praiz(Telemento e1)

{

a->e = e1;



};

Arbol::Arbol()

{

a = NULL;



};
Arbol::~Arbol()

{

if (a)



delete a;

}

Nodo::Nodo (Arbol ai, Telemento x, Arbol ad)



{

e = x;


hi = ai;

hd = ad;


};

PROBLEMA 20.2
Arbol::Arbol(const Arbol & arb)

{ // constructor de copia



if (arb.a == NULL)

a = NULL;



else

a = new Nodo(arb.a->hi, arb.a->e, arb.a->hd);

//llama recursivamente al constructor por copia

}
PROBLEMA 20.3


void Arbol:: Copiar ( Arbol & a1)

{

if(a)

{

a1.a = new Nodo (Arbol(),a->e, Arbol()); //copia raíz



a->hi.Copiar(a1.a->hi); // copiar hijo izquierdo

a->hd.Copiar(a1.a->hd); // copiar el hijo derecho

}

else; //sin hacer hada funciona el constructor. a1 = NULLL

}

PROBLEMA 20.4


const Arbol& Arbol::operator = (const Arbol& arb)

{ // sobrecarga del operador de asignación



if (a != NULL)

delete a; // hay que elminar el árbol antes de copiar



if (arb.a == NULL)

a = NULL;



else

a = new Nodo(arb.a->hi, arb.a->e, arb.a->hd);

//llama recursivamente al constructor por copia

return *this;

}
PROBLEMA 20.5


void Arbol:: Espejo ( Arbol & a1)

{

if(a)

{ a1;

a1.a = new Nodo (Arbol(),a->e, Arbol());



a->hi.Espejo(a1.a->hd);

a->hd.Espejo(a1.a->hi);

}

else;

}
PROBLEMA 20.6


void Arbol::IRD() // Recorrido en inorden

{

if (a !=NULL)

{

a->hi.IRD();



cout << a->e <<" XXX" << endl;

a->hd.IRD();

}

}
void Arbol::IDR()



{

if (a !=NULL)

{

a->hi.IDR();



a->hd.IDR();

cout << a->e <<" XXX" << endl;

}

}
void Arbol::RID()



{

if (a !=NULL)

{

cout << a->e <<" XXX" << endl;



a->hi.RID();

a->hd.RID();

}

}
PROBLEMA 20.7


int Arbol::Cuantos()

{

if (a!= NULL)



return 1+ a->hi.Cuantos() + a->hd.Cuantos();

else

return 0;

}
PROBLEMA 20.8


int Arbol::CuantasH()

{

if (a!= NULL)



if (a->hi.a == NULL && a->hi.a == NULL)

return 1;

else

return a->hi.CuantasH() + a->hd.CuantasH();

else

return 0;

}
PROBLEMA 20.9


void Arbol::NodosNivel(int n)

{

if (a)



if (n == 1)

cout << a->e ;



else

{

a->hi.NodosNivel(n - 1);



a->hd.NodosNivel(n - 1);

}

}


PROBLEMA 20.10
void Arbol::RecorreMayores(Telemento e)

{

if (a)

{

if(a->e > e)

cout << a->el << endl;

a->hi.RecorreMayores(e);

a->hd.RecorreMayores(e);

}

}
PROBLEMA 20.11


void Arbol::AnadeA (Telemento x)

{

if (a == NULL)

a = new Nodo (Arbol(), x, Arbol());

else

if (a->e > x)

a->hi.AnadeA(x);



else if (a->e < x)

a->hd.AnadeA(x);



else; // tratamiento de repeticiones rep(x)

}

void Arbol::AnadeAI (Telemento x) // añade iterativamente

{

Nodo *Ant = NULL, *nuevo, *pos = a;



bool enc = false;
while (!enc && pos != NULL) // búsqueda

{

if (pos->e == x)

enc = true; // encontrado

else

{

Ant = pos;



if( pos->e < x )

pos = pos->hd.a; // avanza hacia la derecha



else

pos = pos->hi.a; // avanza hacia la izquierda

}

}

if (enc)



//repe(x); tratamiento de claves repetidas

else //inserción del nodo

{

nuevo = new Nodo(Arbol(),x,Arbol());



if (Ant == NULL)// es la raíz

a = nuevo;



else

if (Ant->e < x) // es un hijo derecho de Ant

Ant->hd.a = nuevo;



Else // es un hijo izquierdo de Ant

Ant->hi.a = nuevo;

}

}
PROBLEMA 20.12


void Arbol:: BorrarA (Telemento x)

{

if (a == NULL)

cout << "error en borrado no está " << endl;

else

if (a->e < x)

a->hd.BorrarA(x); //llamada a la derecha



else if (a->e > x)

a-> hi.BorrarA(x); //llamada a la izquierda



else if (a-> hi.a == NULL) // no tiene hijo izquierdo

{

Nodo * aborrar;



aborrar = a;

a = a->hd.a; // enlaza con su hijo derecho

aborrar->hd = Arbol();// para que no se propague el delete

delete aborrar;

}

else if( a->hd.a == NULL) // no tiene hijo derecho

{

Nodo * aborrar;



aborrar = a;

a= a->hi.a; // enlaza con su hijo izjierdo

aborrar->hi = Arbol();// para que no se propague el delete

delete aborrar;

}

else // dos hijos predecesor inmediato

a->hi.BorP(a->e);// avanza uno izquierda y recibe valor en a->e

}
void Arbol::BorP( Telemento &x)

{ // todo a la derecha

if ( a->hd.a == NULL)// si no tiene hijo derecho fin recursividad

{

Nodo * aborrar = a;



a = a->hi.a; // enlaza con su hijo izquierdo

aborrar-> hi= Arbol();

x = aborrar-> e ; // retorna el valor a raíz original

delete aborrar;

}

else

a->hd.BorP (x); // llamada recursiva

}
void Arbol::BorrarAI(Telemento x)

{

Nodo * Ant = NULL, *aborrar, *pos = a;



bool enc = false;

while (!enc && pos != NULL) // no encontrado y quede árbol

{


if (pos->e == x)

enc = true; // encontrado



else

{

Ant = pos; // quedarse con el anterior



if( pos->e < x )

pos = pos->hd.a; // avanza a la derecha



else

pos = pos->hi.a; // avanza a la derecha

}

}

if (enc)



{

if ( pos-> hd.a == NULL) // no hijo derecho

{

if (Ant) // no es la raíz



if (Ant->hd.a == pos) // pos es hijo derecho de Ant

Ant->hd.a = pos->hi.a;



else

Ant->hi.a= pos->hi.a;



else // es la raíz

a = pos->hi.a;

pos->hi = Arbol() ;

delete pos;

}

else if ( pos-> hi.a ==0) // no hijo izquierdo

{

if (Ant) // no es la raíz



if (Ant->hd.a == pos) //pos es hijo izquierdo de Ant

Ant->hd.a = pos->hd.a;



else

Ant->hi.a = pos->hd.a;



else

a = pos->hd.a;

pos->hd= Arbol();

delete pos;

}

else // dos hijos predecesor inmediato

a->hi.BorPI(a->e); // uno a la izquierda, y todo derecha

}

else

cout << " no encontrado";

}

void Arbol::BorPI(Telemento &x)

{

Nodo *Ant = NULL, *Aux = a;



while( Aux->hd.a) // búsqueda a la derecha

{

Ant = Aux;



Aux = Aux->hd.a;

}

if (Ant == NULL) // No tenía hijo derecho

a = Aux->hi.a; // enlaza el padre

else

Ant->hd.a = Aux->hi.a; // enlaza hijo derecho de Ant con

//izquiedo de aux

Aux ->hi= Arbol();

x = Aux->e;

delete Aux;



}







La base de datos está protegida por derechos de autor ©bazica.org 2016
enviar mensaje

    Página principal