Funzione Max in albero binario

di il
4 risposte

Funzione Max in albero binario

Ciao a tutti,ho un problema con del codice C.Ho creato due funzioni,una che attraversa l'albero in ordine simmetrico,l'altra che mi restituisce il valore massimo presente nell'albero.Il problema sorge quando nel main chiamo la funzione max,che va in loop e non stampa nulla a video.Se tolgo la chiamata funziona tutto.Ecco il codice:

#include<stdio.h>
#include<stdlib.h>
#define bool int

/* A binary tree tNode has data, pointer to left child
   and a pointer to right child */
struct tNode
{
   int data;
   struct tNode* left;
   struct tNode* right;
};
 
/* Structure of a stack node. Linked List implementation is used for 
   stack. A stack node contains a pointer to tree node and a pointer to 
   next stack node */
struct sNode
{
  struct tNode *t;
  struct sNode *next;
};
 
/* Stack related functions */
int Fmax(struct tNode *root);
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);
 int max(struct tNode*r);
/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
  /* set current to root of binary tree */
  struct tNode *current = root;
    /* Initialize stack s */
  bool done = 0;
 struct sNode *s = NULL;
  while (!done)
  {
    /* Reach the left most tNode of the current tNode */
    if(current !=  NULL)
    {
      /* place pointer to a tree node on the stack before traversing 
        the node's left subtree */
      push(&s, current);                                               
      current = current->left;  
    }
        
    /* backtrack from the empty subtree and visit the tNode 
       at the top of the stack; however, if the stack is empty,
      you are done */
    else                                                             
    {
      if (!isEmpty(s))
      {
        current = pop(&s);
        printf("%d ", current->data);
 
        /* we have visited the node and its left subtree.
          Now, it's right subtree's turn */
        current = current->right;
      }
      else
        done = 1; 
    }
  } /* end of while */ 
}     
 
/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
  /* allocate tNode */
  struct sNode* new_tNode =
            (struct sNode*) malloc(sizeof(struct sNode));
 
  if(new_tNode == NULL)
  {
     printf("Stack Overflow \n");
     getchar();
     exit(0);
  }            
 
  /* put in the data  */
  new_tNode->t  = t;
 
  /* link the old list off the new tNode */
  new_tNode->next = (*top_ref);   
 
  /* move the head to point to the new tNode */
  (*top_ref)    = new_tNode;
}
 
/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
   return (top == NULL)? 1 : 0;
}   
 
/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
  struct tNode *res;
  struct sNode *top;
 
  /*If sNode is empty then error */
  if(isEmpty(*top_ref))
  {
     printf("Stack Underflow \n");
     getchar();
     exit(0);
  }
  else
  {
     top = *top_ref;
     res = top->t;
     *top_ref = top->next;
     free(top);
     return res;
  }
}
 
/* Helper function that allocates a new tNode with the
   given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
  struct tNode* tNode = (struct tNode*)
                       malloc(sizeof(struct tNode));
  tNode->data = data;
  tNode->left = NULL;
  tNode->right = NULL;
 
  return(tNode);
}
 
/* Driver program to test above functions*/
int main()
{
    int Massimo=0;
   
 
  /* Constructed binary tree is
            1
          /   \
        2      3
      /  \
    4     5
  */
  struct tNode *root = newtNode(1);
  root->left        = newtNode(2);
  root->right       = newtNode(3);
  root->left->left  = newtNode(4);
  root->left->right = newtNode(5); 
 
 
  inOrder(root);
  Massimo=max(root);
  printf("%d",Massimo);
  
  
  getchar();
   
  return 0;
}

int max(struct tNode *r){
struct sNode *s = NULL;
    int max=r->data;
	if(r==NULL)
	 return 0;
	 push(&s,r);
	 while(!isEmpty(s)){
	 if(r->data>max)
		max=r->data;
		pop(&s);
		if(r->right!=NULL)
                    push(&s,r->right);
		if(r->right!=NULL)
                    push(&s,r->right);
	 
                
	 }
	 return max;


}

4 Risposte

  • Re: Funzione Max in albero binario

    Nella funzione max sposta questa riga dopo la verifica del NULL nel if
     int max=r->data;
    e cioè
    
       if(r==NULL)
        return 0;
    struct sNode *s = NULL;
        int max=r->data;
    
  • Re: Funzione Max in albero binario

    Grazie skynet ma purtroppo va sempre in loop e non restituisce nulla! !!
  • Re: Funzione Max in albero binario

    Non mi ricordo una cippa dell'algoritmo ma qui hai un codice ripetuto.
     if(r->right!=NULL)
                        push(&s,r->right);
          if(r->right!=NULL)
                        push(&s,r->right);
  • Re: Funzione Max in albero binario

    Ok grazie skynet,ho corretto ma non va...
Devi accedere o registrarti per scrivere nel forum
4 risposte