Thread: Binary search tree

1. 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

2. 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

3. ok thanks!I have correct :
[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);

else{
if( r->left != NULL) Push(S,r->left);
}

}

return nvalm;
}
[/tag]

4. Someone can help me?This code is correct?Thanks

5. 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

6. No your latest code is wrong. "->right" does not appear anywhere, so how is it ever supposed to go down into a right subtree?!

7. 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?

8. 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

9. 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?

10. Why not? A pointer is like an int in this regard: if you can store an int, you can store a pointer.

11. 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!

12. Your stack is implemented using a linked list, from what I see. Each node contains the value in a member named d. So, if you want a stack of pointers instead of ints, just change the type of d. Since it is the tree, not the stack (and hence not the linked list) that owns these pointers, you just need to get d to point to the right node in the tree.

13. 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

14. 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]

15. You may try a more sanitized wording, to help you understand better what your are trying to achieve.

Perhaps something along the following lines...

Code:
typedef struct TreeNode TreeNode;
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
};

typedef struct StackNode StackNode;
struct StackNode {
TreeNode  *treenode;
StackNode *prev;
};

/* this is not really needed, but I followed your example */
typedef struct Stack Stack;
struct Stack {
int nelems;
StackNode *top;
};
Please note that forward declarations with typedef's are optional in your case (for example, it's not that you are implementing a library with opaque objects), but they help in writing shorter code later on.

Then define the basic operations for your stack. For example...
Code:
void        stack_push( Stack *stack, const TreeNode *treenode );
TreeNode   *stack_pop( Stack *stack );
int         stack_empty( const Stack *stack );
void        stack_destroy( Stack *stack );
Finally define your stack, lets say...
Code:
...
int main( void )
{
Stack s = {0, NULL};
...
and you should be good to go.

PS. Btw, hi everybody, this is my first post in the forum.

Popular pages Recent additions