Functions Max in binary tree
Hello everyone, I have a problem with the C code . I created two functions, one that runs through the tree inorder, the other that returns the maximum value in the tree. The problem is when I use in the main the method "max", which goes in a loop and not print anything on the screen . If I remove the call to method "max" it works fine. Here's the code:
Quote:
Code:
#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);
int lessthan(struct tNode * r,int val);
/* 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()
{
/* 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);
int maxValue=0;
inOrder(root);
maxValue= max(root);
printf("%d",maxValue);
getchar();
return 0;
}
int max(struct tNode *r){
if(r==NULL)
return 0;
struct sNode *s = NULL;
int max=r->data;
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->left!=NULL)
push(&s,r->left);
}
return max;
}
Someone can help me please??Thank u!!!
