/*
* 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);
}
tal vez max() deberia tomar la rama derecha, no la izquierda.
Cita de: CalgaryCorpus en 27 Julio 2014, 21:04 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
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:
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
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.
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);
}
}