Título: BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO Publicado por: falconez 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); } Título: Re: BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO Publicado por: CalgaryCorpus en 27 Julio 2014, 21:04 pm tal vez max() deberia tomar la rama derecha, no la izquierda.
Título: Re: BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO Publicado por: Blaster 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 Título: Re: BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO Publicado por: rir3760 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
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 Título: Re: BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO Publicado por: CalgaryCorpus 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. Título: Re: BUSCAR EL VALOR MAXIMO Y MINIMO DEL ARBOL BINARIO Publicado por: falconez 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); } } |