Binary search tree

This is a discussion on Binary search tree within the C Programming forums, part of the General Programming Boards category; Hi at all!This is my new post!I am preparing the examination of algorithms and data structures at the university! Would ...

  1. #1
    Registered User
    Join Date
    May 2013
    Posts
    13

    Talking 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. #2
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    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. #3
    Registered User
    Join Date
    May 2013
    Posts
    13
    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]
    Last edited by ezionice; 05-17-2013 at 06:40 AM.

  4. #4
    Registered User
    Join Date
    May 2013
    Posts
    13
    Someone can help me?This code is correct?Thanks

  5. #5
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by ezionice View Post
    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. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    No your latest code is wrong. "->right" does not appear anywhere, so how is it ever supposed to go down into a right subtree?!
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    May 2013
    Posts
    13
    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. #8
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    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. #9
    Registered User
    Join Date
    May 2013
    Posts
    13
    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. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,955
    Why not? A pointer is like an int in this regard: if you can store an int, you can store a pointer.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    May 2013
    Posts
    13
    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. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,955
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    3,797
    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. #14
    Registered User
    Join Date
    May 2013
    Posts
    13
    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. #15
    Registered User migf1's Avatar
    Join Date
    May 2013
    Location
    Athens, Greece
    Posts
    210
    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.
    Last edited by migf1; 05-21-2013 at 04:50 PM. Reason: typos

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree-search method help?
    By shocklightning in forum C++ Programming
    Replies: 5
    Last Post: 03-25-2012, 10:57 PM
  2. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  3. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 01:12 PM
  4. Binary Search Tree
    By Pyrce in forum C Programming
    Replies: 1
    Last Post: 09-23-2005, 06:04 AM
  5. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 02:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21