Universidad de Panamá
Centro Universitario de Coclé
Programación II
Semestral
Arboles y Grafos
Profesora: Dayalis Vargas
Estudiante: Marichell Araúz
Cédula: 2-749-655
Fecha: 21/07/21
lunes, 19 de julio de 2021
DEFINICIÓN DE ARBOL
Definición
Son estructuras de datos muy similares a las listas doblemente enlazadas, en el sentido que tienen punteros que apuntan a otros elementos, pero no tienen una estructura lógica de tipo lineal o secuencial como aquellas, sino ramificada. Tienen aspecto de árbol, de ahí su nombre.
Los árboles representan las estructuras no-lineales y dinámicas de datos más importantes en computación. Dinámicas, puesto que la estructura árbol puede cambiar durante la ejecución de un programa. No-lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.
TIPOS DE ARBOLES BINARIOS
Tipos
Existen cuatro tipos de árbol binario:
¤ Distinto: Cuando sus estructuras son diferentes.
¤ Similares: Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente
¤ Equivalentes: Son aquellos árboles que son similares y que además los nodos contienen la misma información.
¤ Completos: Son aquellos árboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.
domingo, 18 de julio de 2021
MOSTRAR EL ARBOL COMPLETO
Mostrar el arbol completo
Despues de insertar los nodos se mostrara el resultado de los elementos del arbol.
Ejemplo:
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
struct Nodo{
int dato;
Nodo *der;
Nodo *izq;
};
//Prototipos
void menu();
Nodo *crearNodo(int);
void insertarNodo(Nodo *&,int);
void mostrarArbol(Nodo *,int);
Nodo *arbol = NULL;
int main(){
menu();
getch();
return 0;
}
//Funcion de menu
void menu(){
int dato,opcion,contador=0;
do{
cout<<"\t.:MENU:."<<endl;
cout<<"1. Insertar un nuevo nodo"<<endl;
cout<<"2. Mostrar el arbol completo"<<endl;
cout<<"3. Salir"<<endl;
cout<<"Opcion: ";
cin>>opcion;
switch(opcion){
case 1: cout<<"\nDigite un numero: ";
cin>>dato;
insertarNodo(arbol,dato,NULL); //Insertamos un nuevo nodo
cout<<"\n";
system("pause");
break;
case 2: cout<<"\nMostrando el arbol completo:\n\n";
mostrarArbol(arbol,contador);
cout<<"\n";
system("pause");
break;
}
system("cls");
}while(opcion != 3);
}
//Funcion para crear un nuevo nodo
Nodo *crearNodo(int n,Nodo *padre){
Nodo *nuevo_nodo = new Nodo();
nuevo_nodo ->dato = n;
nuevo_nodo ->der = NULL;
nuevo_nodo ->izq = NULL;
return nuevo_nodo;
}
//Funcion para insertar elementos en el arbol
void insertarNodo(Nodo *&arbol,int n,Nodo *padre){
if(arbol == NULL){ //Si el arbol esta vacio
Nodo *nuevo_nodo = crearNodo(n,padre);
arbol = nuevo_nodo;
}
else{ //Si el arbol tiene un nodo o mas
int valorRaiz = arbol->dato; //Obtenemos el valor de la raiz
if(n < valorRaiz){ //Si ele elemento es menor a la raiz, insertamos en izq
insertarNodo(arbol->izq,n,arbol);
}
else{//Si el elemento es mayor a la raiz, insertamos en der
insertarNodo(arbol->der,n,arbol);
}
}
}
//Funcion para mostrar el arbol completo
void mostrarArbol(Nodo *arbol,int cont){
if(arbol == NULL){ //Si el arbol esta vacio
return;
}
else{
mostrarArbol(arbol->der,cont+1);
for(int i=0;i<cont;i++){
cout<<" ";
}
cout<<arbol->dato<<endl;
mostrarArbol(arbol->izq,cont+1);
}
}
BUSCAR UN NODO ESPECIFICO
Buscar un nodo especifico
La búsqueda en un árbol binario de búsqueda consiste en acceder a la raíz del árbol, si el elemento a localizar coincide con este la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado es que no existe en el árbol. La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) se puede realizar de dos formas, iterativa o recursiva.
Ejemplo
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
struct Nodo{
int dato;
Nodo *der;
Nodo *izq;
};
//Prototipos
void menu();
Nodo *crearNodo(int,Nodo *);
void insertarNodo(Nodo *&,int,Nodo *);
void mostrarArbol(Nodo *,int);
bool busqueda(Nodo *,int);
Nodo *arbol = NULL;
int main(){
menu();
getch();
return 0;
}
//Funcion de menu
void menu(){
int dato,opcion,contador=0;
do{
cout<<"\t.:MENU:."<<endl;
cout<<"1. Insertar un nuevo nodo"<<endl;
cout<<"2. Mostrar el arbol completo"<<endl;
cout<<"3. Buscar un elemento en el arbol"<<endl;
cout<<"4. Salir"<<endl;
cout<<"Opcion: ";
cin>>opcion;
switch(opcion){
case 1: cout<<"\nDigite un numero: ";
cin>>dato;
insertarNodo(arbol,dato,NULL); //Insertamos un nuevo nodo
cout<<"\n";
system("pause");
break;
case 2: cout<<"\nMostrando el arbol completo:\n\n";
mostrarArbol(arbol,contador);
cout<<"\n";
system("pause");
break;
case 3: cout<<"\nDigite el elemento a buscar: ";
cin>>dato;
if(busqueda(arbol,dato) == true){
cout<<"Elemento "<<dato<<" a sido encontrado en el arbol\n";
}
else{
cout<<"\nElemento no encontrado \n";
}
cout<<"\n";
system("pause");
break;
}
system("cls");
}while(opcion != 4);
}
//Funcion para crear un nuevo nodo
Nodo *crearNodo(int n,Nodo *padre){
Nodo *nuevo_nodo = new Nodo();
nuevo_nodo ->dato = n;
nuevo_nodo ->der = NULL;
nuevo_nodo ->izq = NULL;
nuevo_nodo ->padre = padre;
return nuevo_nodo;
}
//Funcion para insertar elementos en el arbol
void insertarNodo(Nodo *&arbol,int n,Nodo *padre){
if(arbol == NULL){ //Si el arbol esta vacio
Nodo *nuevo_nodo = crearNodo(n,padre);
arbol = nuevo_nodo;
}
else{ //Si el arbol tiene un nodo o mas
int valorRaiz = arbol->dato; //Obtenemos el valor de la raiz
if(n < valorRaiz){ //Si ele elemento es menor a la raiz, insertamos en izq
insertarNodo(arbol->izq,n,arbol);
}
else{//Si el elemento es mayor a la raiz, insertamos en der
insertarNodo(arbol->der,n,arbol);
}
}
}
//Funcion para mostrar el arbol completo
void mostrarArbol(Nodo *arbol,int cont){
if(arbol == NULL){ //Si el arbol esta vacio
return;
}
else{
mostrarArbol(arbol->der,cont+1);
for(int i=0;i<cont;i++){
cout<<" ";
}
cout<<arbol->dato<<endl;
mostrarArbol(arbol->izq,cont+1);
}
}
//Funcion para buscar un elemento en el arbol
bool busqueda(Nodo *arbol,int n){
if(arbol == NULL){ //Si el arbol esta vacio
return false;
}
else if(arbol->dato == n){//Si el nodo es igual al elemento
return true;
}
else if(n < arbol ->dato){
return busqueda(arbol->izq,n);
}
else{
return busqueda(arbol->der,n);
}
}
Video
https://youtu.be/av3hXDcqEo4
RECORRER EL ARBOL EN (PreOrden, InOrden, PostOrden)
Recorrido del arbol en PreOrden, InOrden, PostOrden
preorden: raiz-hijo izquierdo-hijo derecho
postorden: hijo izquierdo-hijo derecho-raíz
inorden: hijo izquierdo-raíz-hijo derecho
Ejemplo
include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
struct Nodo{
int dato;
Nodo *der;
Nodo *izq;
};
//Prototipos
void menu();
Nodo *crearNodo(int,Nodo *);
void insertarNodo(Nodo *&,int,Nodo *);
void mostrarArbol(Nodo *,int);
bool busqueda(Nodo *,int);
void preOrden(Nodo *);
void inOrden(Nodo *);
void postOrden(Nodo *);
Nodo *arbol = NULL;
int main(){
menu();
getch();
return 0;
}
//Funcion de menu
void menu(){
int dato,opcion,contador=0;
do{
cout<<"\t.:MENU:."<<endl;
cout<<"1. Insertar un nuevo nodo"<<endl;
cout<<"2. Mostrar el arbol completo"<<endl;
cout<<"3. Buscar un elemento en el arbol"<<endl;
cout<<"4. Recorrer el arbol en PreOrden"<<endl;
cout<<"5. Recorrer el arbol en InOrden"<<endl;
cout<<"6. Recorrer el arbol en PostOrden"<<endl;
cout<<"7. Salir"<<endl;
cout<<"Opcion: ";
cin>>opcion;
switch(opcion){
case 1: cout<<"\nDigite un numero: ";
cin>>dato;
insertarNodo(arbol,dato,NULL); //Insertamos un nuevo nodo
cout<<"\n";
system("pause");
break;
case 2: cout<<"\nMostrando el arbol completo:\n\n";
mostrarArbol(arbol,contador);
cout<<"\n";
system("pause");
break;
case 3: cout<<"\nDigite el elemento a buscar: ";
cin>>dato;
if(busqueda(arbol,dato) == true){
cout<<"Elemento "<<dato<<" a sido encontrado en el arbol\n";
}
else{
cout<<"\nElemento no encontrado \n";
}
cout<<"\n";
system("pause");
break;
case 4: cout<<"\nRecorrido en preOrden: ";
preOrden(arbol);
cout<<"\n\n";
system("pause");
break;
case 5: cout<<"\nRecorrido en InOrden: ";
inOrden(arbol);
cout<<"\n\n";
system("pause");
break;
case 6: cout<<"\nRecorrido en PostOrden: ";
postOrden(arbol);
cout<<"\n\n";
system("pause");
break;
}
system("cls");
}while(opcion != 7);
}
//Funcion para crear un nuevo nodo
Nodo *crearNodo(int n,Nodo *padre){
Nodo *nuevo_nodo = new Nodo();
nuevo_nodo ->dato = n;
nuevo_nodo ->der = NULL;
nuevo_nodo ->izq = NULL;
return nuevo_nodo;
}
//Funcion para insertar elementos en el arbol
void insertarNodo(Nodo *&arbol,int n,Nodo *padre){
if(arbol == NULL){ //Si el arbol esta vacio
Nodo *nuevo_nodo = crearNodo(n);
arbol = nuevo_nodo;
}
else{ //Si el arbol tiene un nodo o mas
int valorRaiz = arbol->dato; //Obtenemos el valor de la raiz
if(n < valorRaiz){ //Si ele elemento es menor a la raiz, insertamos en izq
insertarNodo(arbol->izq,n,arbol);
}
else{//Si el elemento es mayor a la raiz, insertamos en der
insertarNodo(arbol->der,n,arbol);
}
}
}
//Funcion para mostrar el arbol completo
void mostrarArbol(Nodo *arbol,int cont){
if(arbol == NULL){ //Si el arbol esta vacio
return;
}
else{
mostrarArbol(arbol->der,cont+1);
for(int i=0;i<cont;i++){
cout<<" ";
}
cout<<arbol->dato<<endl;
mostrarArbol(arbol->izq,cont+1);
}
}
//Funcion para buscar un elemento en el arbol
bool busqueda(Nodo *arbol,int n){
if(arbol == NULL){ //Si el arbol esta vacio
return false;
}
else if(arbol->dato == n){//Si el nodo es igual al elemento
return true;
}
else if(n < arbol ->dato){
return busqueda(arbol->izq,n);
}
else{
return busqueda(arbol->der,n);
}
}
//Funcion para recorrido en profundidad - PreOrden
void preOrden(Nodo *arbol){
if(arbol == NULL){ //Si el arbol esta vacio
return;
}
else{
cout<<arbol->dato<<" - ";
preOrden(arbol->izq);
preOrden(arbol->der);
}
}
//Funcion para recorrido en profundidad - InOrden
void inOrden(Nodo *arbol){
if(arbol == NULL){
return;
}
else{
inOrden(arbol->izq);
cout<<arbol->dato<<" - ";
inOrden(arbol->der);
}
}
//Funcion para recorrido en profundidad - PostOrden
void postOrden(Nodo *arbol){
if(arbol == NULL){//Si el arbol esta vacio
return;
}
else{
postOrden(arbol->izq);
postOrden(arbol->der);
cout<<arbol->dato<<" - ";
}
}
Video
https://youtu.be/ZmCfRs9lUUY
BORRAR UN NODO DEL ARBOL
Borrar
La operación de borrado no es tan sencilla como las de búsqueda e inserción. Existen varios casos a tener en consideración:
* Borrar un nodo sin hijos o nodo hoja: simplemente se borra y se establece a nulo el apuntador de su padre.
* Borrar un nodo con un subárbol hijo: se borra el nodo y se asigna su subárbol hijo como subárbol de su padre.
* Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho).
Ejemplo
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
struct Nodo{
int dato;
Nodo *der;
Nodo *izq;
Nodo *padre;
};
//Prototipos
void menu();
Nodo *crearNodo(int,Nodo *);
void insertarNodo(Nodo *&,int,Nodo *);
void mostrarArbol(Nodo *,int);
bool busqueda(Nodo *,int);
void preOrden(Nodo *);
void inOrden(Nodo *);
void postOrden(Nodo *);
void borrar(Nodo *,int);
void borrarNodo(Nodo *);
Nodo *minimo(Nodo *);
void reemplazar(Nodo *,Nodo *);
void destruirNodo(Nodo *);
Nodo *arbol = NULL;
int main(){
menu();
getch();
return 0;
}
//Funcion de menu
void menu(){
int dato,opcion,contador=0;
do{
cout<<"\t.:MENU:."<<endl;
cout<<"1. Insertar un nuevo nodo"<<endl;
cout<<"2. Mostrar el arbol completo"<<endl;
cout<<"3. Buscar un elemento en el arbol"<<endl;
cout<<"4. Recorrer el arbol en PreOrden"<<endl;
cout<<"5. Recorrer el arbol en InOrden"<<endl;
cout<<"6. Recorrer el arbol en PostOrden"<<endl;
cout<<"7. Borrar un nodo del arbol"<<endl;
cout<<"8. Salir"<<endl;
cout<<"Opcion: ";
cin>>opcion;
switch(opcion){
case 1: cout<<"\nDigite un numero: ";
cin>>dato;
insertarNodo(arbol,dato,NULL); //Insertamos un nuevo nodo
cout<<"\n";
system("pause");
break;
case 2: cout<<"\nMostrando el arbol completo:\n\n";
mostrarArbol(arbol,contador);
cout<<"\n";
system("pause");
break;
case 3: cout<<"\nDigite el elemento a buscar: ";
cin>>dato;
if(busqueda(arbol,dato) == true){
cout<<"Elemento "<<dato<<" a sido encontrado en el arbol\n";
}
else{
cout<<"\nElemento no encontrado \n";
}
cout<<"\n";
system("pause");
break;
case 4: cout<<"\nRecorrido en preOrden: ";
preOrden(arbol);
cout<<"\n\n";
system("pause");
break;
case 5: cout<<"\nRecorrido en InOrden: ";
inOrden(arbol);
cout<<"\n\n";
system("pause");
break;
case 6: cout<<"\nRecorrido en PostOrden: ";
postOrden(arbol);
cout<<"\n\n";
system("pause");
break;
case 7: cout<<"\nDigite el numero a borrar: ";
cin>>dato;
borrar(arbol,dato);
cout<<"\n";
system("pause");
break;
}
system("cls");
}while(opcion != 8);
}
//Funcion para crear un nuevo nodo
Nodo *crearNodo(int n,Nodo *padre){
Nodo *nuevo_nodo = new Nodo();
nuevo_nodo ->dato = n;
nuevo_nodo ->der = NULL;
nuevo_nodo ->izq = NULL;
nuevo_nodo ->padre = padre;
return nuevo_nodo;
}
//Funcion para insertar elementos en el arbol
void insertarNodo(Nodo *&arbol,int n,Nodo *padre){
if(arbol == NULL){ //Si el arbol esta vacio
Nodo *nuevo_nodo = crearNodo(n,padre);
arbol = nuevo_nodo;
}
else{ //Si el arbol tiene un nodo o mas
int valorRaiz = arbol->dato; //Obtenemos el valor de la raiz
if(n < valorRaiz){ //Si ele elemento es menor a la raiz, insertamos en izq
insertarNodo(arbol->izq,n,arbol);
}
else{//Si el elemento es mayor a la raiz, insertamos en der
insertarNodo(arbol->der,n,arbol);
}
}
}
//Funcion para mostrar el arbol completo
void mostrarArbol(Nodo *arbol,int cont){
if(arbol == NULL){ //Si el arbol esta vacio
return;
}
else{
mostrarArbol(arbol->der,cont+1);
for(int i=0;i<cont;i++){
cout<<" ";
}
cout<<arbol->dato<<endl;
mostrarArbol(arbol->izq,cont+1);
}
}
//Funcion para buscar un elemento en el arbol
bool busqueda(Nodo *arbol,int n){
if(arbol == NULL){ //Si el arbol esta vacio
return false;
}
else if(arbol->dato == n){//Si el nodo es igual al elemento
return true;
}
else if(n < arbol ->dato){
return busqueda(arbol->izq,n);
}
else{
return busqueda(arbol->der,n);
}
}
//Funcion para recorrido en profundidad - PreOrden
void preOrden(Nodo *arbol){
if(arbol == NULL){ //Si el arbol esta vacio
return;
}
else{
cout<<arbol->dato<<" - ";
preOrden(arbol->izq);
preOrden(arbol->der);
}
}
//Funcion para recorrido en profundidad - InOrden
void inOrden(Nodo *arbol){
if(arbol == NULL){
return;
}
else{
inOrden(arbol->izq);
cout<<arbol->dato<<" - ";
inOrden(arbol->der);
}
}
//Funcion para recorrido en profundidad - PostOrden
void postOrden(Nodo *arbol){
if(arbol == NULL){//Si el arbol esta vacio
return;
}
else{
postOrden(arbol->izq);
postOrden(arbol->der);
cout<<arbol->dato<<" - ";
}
}
//borrar un nodo del arbol
void borrar(Nodo *arbol,int n){
if(arbol == NULL){//Si el arbol esta vacio
return;
}
else if(n < arbol->dato){//Si el valor es menor
borrar(arbol->izq,n);
}
else if(n > arbol->dato){//Si el valor es mayor
borrar(arbol->der,n);
}
else{//Si ya encontraste el valor
borrarNodo(arbol);
}
}
//Funcion para determinar el nodo mas izq posible
Nodo* minimo(Nodo *arbol){
if(arbol == NULL){//Si el arbol esta vacio
return NULL;
}
if(arbol->izq){//Si tiene hijo izq
return minimo(arbol->izq);//buscamos la parte mas izq posible
}
else{//Si no tiene hijo izq
return arbol;//retornamos el mismo nodo
}
}
//Funcion para reemplazar dos nodos
void reemplazar(Nodo *arbol,Nodo *nuevoNodo){
if(arbol->padre){
//arbol->padre hay que asignarle su nuevo hijo
if(arbol->dato == arbol->padre->izq->dato){
arbol->padre->izq = nuevoNodo;
}
else if(arbol->dato == arbol->padre->der->dato){
arbol->padre->der = nuevoNodo;
}
}
if(nuevoNodo){
//Procedemos a asignarle su nuevo padre
nuevoNodo->padre = arbol->padre;
}
}
//Funcion para destruir un nodo
void destruirNodo(Nodo *nodo){
nodo->izq = NULL;
nodo->der = NULL;
delete nodo;
}
//Funcion para borrar el nodo encontrado
void borrarNodo(Nodo *nodoBorrar){
if(nodoBorrar->izq && nodoBorrar->der){//Si el nodo tiene hijo izq y der
Nodo *menor = minimo(nodoBorrar->der);
nodoBorrar->dato = menor->dato;
borrarNodo(menor);
}
else if(nodoBorrar->izq){//Si tiene hijo izq
reemplazar(nodoBorrar,nodoBorrar->izq);
destruirNodo(nodoBorrar);
}
else if(nodoBorrar->der){
reemplazar(nodoBorrar,nodoBorrar->der);
destruirNodo(nodoBorrar);
}
else{//No tiene hijos
reemplazar(nodoBorrar,NULL);
destruirNodo(nodoBorrar);
}
}
Video
https://youtu.be/scnuZa-baYw
Suscribirse a:
Entradas (Atom)
PRESENTACIÓN
Universidad de Panamá Centro Universitario de Coclé Programación II Semestral Arboles y Grafos Profesora: Dayalis Vargas Estudia...
-
■ Aristas: cada una conecta a un vértice con otro, y puede tener un valor almacenado. Una arista es un par de vértices. ■ Vertice o no... -
Operaciones
