elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO  (Leído 17,511 veces)
falconez

Desconectado Desconectado

Mensajes: 18



Ver Perfil
BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO
« en: 27 Julio 2014, 00:09 am »

/*
 * File:   firstTree.cpp
 * Author: Estudiantes
 *
 * Created on 17 de julio de 2014, 06:49 PM
 *
 *
 */

//Necesito saber como sacar el valor máximo y mínimo del árbol binario que esta a //continuación graficado. El problema es que mi función solo toma los valores //extremos del arbol( izquierda y derecha) que son hojas!


#include <cstdlib>
#include <iostream>


using namespace std;

/*
 *
 *
 *
 *
 *
 */

struct misDatos{
    string nombre;
    int edad;
    int num;
};

struct node{
    misDatos datos;
    node *left;
    node *right;
};



node * newTree();
node * insert(int data, string name);


int printPreOrden(node* ptr);
int printRoot(node* head);
int printPostOrden(node *ptr);
int printInOrden(node *ptr);
int findMinimumValueLEFT(node* node);
int findMinimumValueRIGHT(node* node);


int size(node *node); //MAXIMO DE NODOS
int maxALTURA(node *node); //ALTURA


node * insert_right( int data);
node * insert_left( int data);
 int contar_hojas(node *p) ;
int nodosInteriores(node *raiz );

node *max(node *n);
node *min(node *n);


int MAXIMOprintPreOrden(node* ptr);



int main() {
   
   //ARBOL 1
   node *raiz = newTree();
   node *current = raiz;
   node *arbol=raiz;
   
   /*
   
 ----> GRAFICO DEL ARBOL BINARIO
   
        A
     /    \
    B      C
  / \    /  \
  D  E  F    G

*/
   
   
        //A=10
        //B=14
        //C=16
        //D=18
        //E=20
        //F=24
        //G=30
   
        arbol->left = insert(14,"B");
        arbol->right = insert(16,"C");

        current=arbol->left;
 
        current->left = insert(50,"D");
        current->right = insert(60,"E");

        current=arbol->right;
       
       
        current->left = insert(24,"F");
        current->right = insert(30,"G");
   
     
   
            cout << "\tR E C O R R I D O  P R E - O R D E N\n";
            printPreOrden(raiz);
   



    //cout<<endl<<endl;
   // cout << "\tR E C O R R I D O  P O S T - O R D E N\n";
    //printPostOrden(raiz);
   
     //cout<<endl<<endl;
    //cout << "\tR E C O R R I D O  I N - O R D E N\n";
   // printInOrden(raiz);
            cout<<endl<<endl<<endl<<endl;
           
 
           
            cout<<"NUMERO DE NODOS: "<<size(raiz)<<endl;
           
            cout<<"ALTURA :  "<<maxALTURA(raiz)<<endl;
           cout<<"NUMERO DE HOJAS: "<<contar_hojas(raiz)<<endl;
           
           cout<<"NODOS INTERIORES: "<<nodosInteriores(raiz)<<endl;
     
           
           
    return 0;
}

//---------------> NEW TREE
node * newTree() {
    node *nuevo;
    nuevo = new node; 
   
    nuevo->datos.nombre= "A";
    nuevo->datos.edad = 10; // 
    nuevo->right = nuevo;
    nuevo->left = nuevo;

    return nuevo;
}

// -------------> INSERTANDO
node* insert(int data, string name) {
   
    node *nuevo;
    nuevo = new node;
    nuevo->datos.edad=data;
    nuevo->datos.nombre=name;
    nuevo->left=NULL; 
    nuevo->right=NULL;

    return nuevo;
}




// -------------> O R D E N A M I E N T O S

// -----> PREORDEN

int printPreOrden(node* ptr) {
   
    node *current = ptr;
   
   
      printRoot(current);     //RAIZ
 
   
      if(current->left!=NULL){
         printPreOrden(current->left);    //IZQUIERDA     
       }
   
    if(current->right!=NULL){
       printPreOrden(current->right);    //DERECHA
    }
    return current->datos.edad;
}





int printPostOrden(node *ptr){
    node *current= ptr;
   
     if(current->left!=NULL){
         printPostOrden(current->left);    //IZQUIERDA     
       }

     if(current->right!=NULL){
       printPostOrden(current->right);    //DERECHA
    }
   
    printRoot(current);   
   
   
}

int printInOrden(node *ptr){
    node *current= ptr;
   
     if(current->left!=NULL){
         printInOrden(current->left);    //IZQUIERDA     
       }
   
      printRoot(current);
   
      if(current->right!=NULL){
       printInOrden(current->right);    //DERECHA
    }
   
 
   
}


//numero de nodos
int size(node *node){
    if(node==NULL)
        return 0;
    else
        return (size(node->left)+1+size(node->right));
}
//altura del arbol
int maxALTURA(node *node){
    if(node==NULL)
        return 0;
    else{
        int s=maxALTURA(node->left);
     int m=maxALTURA(node->right);
     if (s>m)
         return (m+1);
     else
         return (s+1);
    }return (size(node->left)+1+size(node->right));
}



//IMPRIMIENDO RAIZ

int printRoot(node* head)
{
    cout<<"Nombre: "<<head->datos.nombre<<"    Edad: "<< head->datos.edad<<"\n"<<endl;
   
}


//VALORES MAXIMOS Y MINIMOS ERRONEOS
    node *min(node *n) {
        if (n == NULL || n->left == NULL)
            return n;
        else
            return min(n->left);
    }

    node *max(node *n) {
        if (n == NULL || n->left == NULL)
            return n;
        else
            return max(n->left);
    }
   


//-----> CONTAR HOJAS   
int contar_hojas(node *p){
   if (p == NULL)
      return 0;
   else if (p->left == NULL && p->right == NULL)
      return 1;
   else
      return contar_hojas(p->left) + contar_hojas(p->right);
}

//NODOS INTERIORES
   int nodosInteriores(node *raiz ){
      return size(raiz)-contar_hojas(raiz);
}


En línea

CalgaryCorpus


Desconectado Desconectado

Mensajes: 323


Ver Perfil WWW
Re: BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO
« Respuesta #1 en: 27 Julio 2014, 21:04 pm »

tal vez max() deberia tomar la rama derecha, no la izquierda.


En línea

Aqui mi perfil en LinkedIn, invitame un cafe aqui
Blaster

Desconectado Desconectado

Mensajes: 190


Ver Perfil
Re: BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO
« Respuesta #2 en: 27 Julio 2014, 21:28 pm »

tal vez max() deberia tomar la rama derecha, no la izquierda.

Para el caso de buscar el valor mayor seria lo correcto ya que los nodos de la derecha tienen un valor mayor o igual a la raíz

Saludos
« Última modificación: 27 Julio 2014, 21:32 pm por Blaster » En línea

rir3760


Desconectado Desconectado

Mensajes: 1.639


Ver Perfil
Re: BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO
« Respuesta #3 en: 27 Julio 2014, 21:44 pm »

Como ya te comentaron CalgaryCorpus y Blaster debes verificar (de ser necesario) el campo "left" para conocer el minimo y el campo "right" para el maximo.

Ademas se puede sacar la comprobacion de arbol vacio fuera de la funcion dejando esa verificacion para quien llame a la funcion (de forma similar al uso de pilas con las funciones pop e is_empty). De hacerlo las funciones se reducen a:
Código
  1. node *min(node *n)
  2. {
  3.   return n->left ? min(n->left) : n;
  4. }
  5.  
  6. node *max(node *n)
  7. {
  8.   return n->right ? max(n->right) : n;
  9. }

Por ultimo se deben realizar varios cambios al programa, por ejemplo hay que cambiar el tipo de retorno de las funciones "printPostOrden", "printInOrden" y "printRoot" a "void" ya que en ningun momento retornas o utilizas el valor.

Un saludo
En línea

C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language
CalgaryCorpus


Desconectado Desconectado

Mensajes: 323


Ver Perfil WWW
Re: BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO
« Respuesta #4 en: 27 Julio 2014, 23:03 pm »

Alternativamente, dado que siempre recorres hacia la izquierda o derecha para una u otra función, sugiero hacer un ciclo, no invocar recursivamente, deteniendose justo al darse cuenta que no hay mas nodos que visitar a continuación.

Ambas (recursiva o no) son soluciones sencillas, pero la recursiva podría "morir" por hacer crecer el stack indefinidamente, para árboles más grandes.

Ahora, todo esto funciona solo si el árbol binario es un árbol de busqueda binaria, pues si fuera solo binario, irse a la izquierda o derecha no garantiza encontrar el mínimo o máximo y en ese caso, tal vez la versión recursiva sea más sencilla que su equivalente no recursiva.
En línea

Aqui mi perfil en LinkedIn, invitame un cafe aqui
falconez

Desconectado Desconectado

Mensajes: 18



Ver Perfil
Re: BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO
« Respuesta #5 en: 28 Julio 2014, 19:02 pm »

Y como haria para mostrar las hojas y los nodos interiores del arbol?

//ESTA FUNCION ESTOY TRABAJANDO ..

int view_NodosInteriores(node *p){
if (p == NULL)
    return 0;
else{
while (p->left != NULL && p->right != NULL)
   
    return p->datos.edad +view_NodosInteriores(p->right) + view_NodosInteriores(p->left);

}
   
   
}
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[Python] - Mínimo y máximo
Python
Meta 2 21,141 Último mensaje 1 Diciembre 2010, 12:50 pm
por Novlucker
Minimo Valor y Maximo Valor de Un Arbol
Programación C/C++
Jupiter34 1 7,874 Último mensaje 16 Noviembre 2012, 18:17 pm
por Jupiter34
maximo y minimo « 1 2 »
Programación C/C++
m@o_614 10 11,553 Último mensaje 27 Abril 2021, 19:59 pm
por K-YreX
Tabla Java valor minimo y maximo
Java
tcubanito 1 2,752 Último mensaje 7 Agosto 2014, 13:39 pm
por NikNitro!
Maximo y minimo de un vector (Funciones)
Programación C/C++
TheShocker 2 6,972 Último mensaje 27 Diciembre 2014, 20:48 pm
por TheShocker
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines