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
No hay comentarios.:
Publicar un comentario