Arboles Binarios

[pnsativo]

Bueno... Soy Nuevo En El Foro ...Poseo un Código De Arboles binarios ,
ya logre que arrojara InOrden, PostOrden y PreOrden, Pero Lo que
ahora necesito es Que Me Arroje el resultado del numero de hojas
totales que posee este arbol... Ayuda !!!!

Código C++:

#include <stdio.h>
#include <stdlib.h>
 
struct nodo
{
   struct nodo *izquierdaPtr;
   int dato;
   struct nodo *derechaPtr;
};
 
typedef struct nodo NODO;
typedef NODO *ARBOLNODOPTR;
 
void insertaNodo(ARBOLNODOPTR *arbolPtr, int valor)
{
 if (*arbolPtr == NULL)
 {
    *arbolPtr = (ARBOLNODOPTR)malloc(sizeof(NODO));
    if (*arbolPtr != NULL)
    {
     (*arbolPtr)->dato = valor;
     (*arbolPtr)->izquierdaPtr = NULL;
     (*arbolPtr)->derechaPtr = NULL;
    }
    else
    {
     printf("%d no insertado. No hay memoria disponible.\n", valor);
    }
 }
 else
 if (valor < (*arbolPtr)->dato)
 {
    insertaNodo(&((*arbolPtr)->izquierdaPtr), valor);
 }
 else
 if (valor > (*arbolPtr)->dato)
    insertaNodo(&((*arbolPtr)->derechaPtr), valor);
    else
    printf("Igual");
}
 
void inOrder(ARBOLNODOPTR arbolPtr)
{
 if (arbolPtr != NULL)
 {
    inOrder(arbolPtr->izquierdaPtr);
    printf("%3d", arbolPtr->dato);
    inOrder(arbolPtr->derechaPtr);
 }
}
 
 
 
void preOrder(ARBOLNODOPTR arbolPtr)
{
 if (arbolPtr != NULL)
 {
    printf("%3d", arbolPtr->dato);
    preOrder(arbolPtr->izquierdaPtr);
    preOrder(arbolPtr->derechaPtr);
 }
}
 
void postOrder(ARBOLNODOPTR arbolPtr)
{
 if (arbolPtr != NULL)
 {
    postOrder(arbolPtr->izquierdaPtr);
    postOrder(arbolPtr->derechaPtr);
    printf("%3d", arbolPtr->dato);
 }
}
 
 
main()
{
 int i, item;
 ARBOLNODOPTR raizPtr = NULL;
 
 for (i=1; i <= 10; i++)
 {
     printf("ingrese elemento: ");
     scanf("%d",&item);
     insertaNodo(&raizPtr, item);
 }
 printf("\n\nEl preOrden es:\n");
 preOrder(raizPtr);
 printf("\n\nEl inOrden es:\n");
 inOrder(raizPtr);
 printf("\n\nEl postOrden es:\n");
 postOrder(raizPtr);
 printf("\n");
 system("pause");
}
 

[sam90]

Viendo tu metodo:

Código C:

void inOrder(ARBOLNODOPTR arbolPtr)
{
 if (arbolPtr != NULL)
 {
    inOrder(arbolPtr->izquierdaPtr);
    printf("%3d", arbolPtr->dato);
    inOrder(arbolPtr->derechaPtr);
 }
}
 

Cada vez que llegamos a la condicion de que arbolPtr es NULL eso quiere decir que es una hoja. Ahora simplemente deberias returnar un uno idicando que es una hoja. Luego cada llamada recursiva recoje esos valores y simplemente los suma y los devuelve.

Código C:

int NumHoja(ARBOLNODOPTR arbolPtr)
{
 if (arbolPtr != NULL)   return ( NumHoja(arbolPtr->izquierdaPtr) +    NumHoja(arbolPtr->derechaPtr) ) ;
 else return 1;
}
 

[pnsativo]

Iniciado por sam90

Viendo tu metodo:

Código C:

void inOrder(ARBOLNODOPTR arbolPtr)
{
 if (arbolPtr != NULL)
 {
    inOrder(arbolPtr->izquierdaPtr);
    printf("%3d", arbolPtr->dato);
    inOrder(arbolPtr->derechaPtr);
 }
}
 

Cada vez que llegamos a la condicion de que arbolPtr es NULL eso quiere decir que es una hoja. Ahora simplemente deberias returnar un uno idicando que es una hoja. Luego cada llamada recursiva recoje esos valores y simplemente los suma y los devuelve.

Código C:

int NumHoja(ARBOLNODOPTR arbolPtr)
{
 if (arbolPtr != NULL)   return ( NumHoja(arbolPtr->izquierdaPtr) +    NumHoja(arbolPtr->derechaPtr) ) ;
 else return 1;
}
 

Muchas Gracias por la ayuda ... Pero Como Quedaria dentro del codigo??... Y Una Vez maz Gracias

[CalgaryCorpus]

La idea de usar la recursion me parece buena, pero la idea de retornar 1 cuando el (sub)arbol es vacio no.

Una mejora a eso es retornar 0 cuando el arbol (o subarbol) es vacio, retornar 1 cuando ambos hijos son null
y retornar
elnumerodehojas( izquierda ) + elnumerodehojas( derecha )

en otro caso.