Thread: Binary search tree

Hi at all!This is my new post!I am preparing the examination of algorithms and data structures at the university! Would I need an opinion on an exercise for the final exam! Here is the text:Consider a binary search tree whose nodes are C structures defined by
[tag]

Code:

struct node {
int val;
 struct node*left;
 struct node *right;
}

[/tag]
and defined a nonrecursive method "lessthan" that receives an input tree and an integer, and returns the number of values ​​in the tree less than the value specified market. Suppose that
is available a stack S (global variable) where can be insert or remove pointers to nodes
(an empty tree is represented by a pointer with a NULL value).

This is my solution:
[tag]

Code:

int lessthan(struct nodo*r,int val){
    if (r == NULL) return 0;


    int nvalm=0;
    
    Push(S,r);
    
    while ((r=Pop(S)))
    {
        if( r->val < val) ++nvalm;
        if( r->left != NULL) Push(S,r->left);
        if( r->right != NULL) Push(S,r->right);
    }
    
    return nvalm;
}

​[/tag]
Thanks to all and sorry for my English

Code:

    while ((r=Pop(S)))
    {
        if( r->val < val) ++nvalm;
        if( r->left != NULL) Push(S,r->left);
        if( r->right != NULL) Push(S,r->right);
    }

As soon as

Code:

r->val >= val

you don't need to go down the right subtree anymore.

Bye, Andreas

Someone can help me?This code is correct?Thanks

Originally Posted by ezionice

This code is correct?

One important part of programming is testing the code you write.
So instead of asking people on the internet whether some code is correct you should write your own tests and find out yourself.

Did you test your first version? Did you get the correct results?
Does the second version fail your tests?

Bye, Andreas

I'd like to test it I do not know how to develop a stack that contains pointers to a binary tree! Can you help me create a stack with these characteristics?

Do you know how to implement a stack for a simple data type like int or char?

What have you tried so far?

Bye, Andreas

I implemented a Stack consists of Linked-List. But the problem is that I can not implement a stack that can contain pointers to nodes of a binary tree!How can i do it?

ok, so I have to create a stack consists of elements that contain pointers. But how do I declare the pointer type?For example:
[tag]

Code:

struct elem{
   int d;
struct elem *next;
}
typedef struct elem elem;

struct stack {
    int cnt;
    elem *top;
};
typedef struct stack stack;

[/tag]

this is a Stack with a type elem,but how can i create a stack that can contains pointers?
Thanks to all!

But how do I declare the pointer type?

O_o

You didn't write that code did you?

*shrug*

Would you know what to change if you wanted a `double' stack?

Soma

ok thank u laserlight!I have write this code:

[tag]
typedef struct node data;


struct elem{
data d;
struct elem *next;
};
typedef struct elem elem;


struct stack {
elem a;
elem*top;
};
typedef struct stack stack;
[/tag]