BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO

[falconez]

/*
* 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);
}

[CalgaryCorpus]

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

[Blaster]

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

[rir3760]

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 (cpp) [Seleccionar] Expandir

node *min(node *n)
{
   return n->left ? min(n->left) : n;
}

node *max(node *n)
{
   return n->right ? max(n->right) : n;
}

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

[CalgaryCorpus]

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.

[falconez]

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);

}
   
   
}