binary tree

This is a discussion on binary tree within the C Programming forums, part of the General Programming Boards category; hii, i have problem writing a binary tree program.actually we can directly search and insert left and right node for ...

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    21

    binary tree

    hii,

    i have problem writing a binary tree program.actually we can directly search and insert left and right node for any normal expression with left child being less than and the right side being greater than the parent.but i am not getting the logic for search and insert for an arithemetic expression with precedence like a+b*c-d;
    here the tree will be like
    Code:
                                  +
    
                           a            -
    
                                     *       d
    
                                 b        c
    how can we construct such a tree.like we need to parse the entire expression before deciding even the root.

    please help me out with this
    regards,
    cutelucks
    Last edited by Prelude; 09-25-2007 at 08:11 AM. Reason: Preserved formatting.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Try recursing over the tree, perhaps?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Apr 2007
    Posts
    21
    no thatz what i have doubt.we create a structure for the tree like:
    struct node
    Code:
    {
      int type;
      char *name;
      struct node *left, *right;
    };

    and then we start searching for our node and add it to the tree.so everytime do we need to destroy athe temp tree and create a new one like if the expr is
    d+a*b+c:

    first it will parsed like
    d
    a
    b
    *
    +
    c
    +

    but our output shud be like(d+(a*b))+c)..
    i donno how to assign prioritiez for the operatorz..may be like
    * or /: 1
    + or -: 2
    char: 3
    but i donno how to implement it in a c program

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Both the generation of the tree and the evaluation of the tree can be done by recursion. Just think of it as partial expressions where you know what's on the left, and need to calculate the right side.

    If you search the forum, you'll find some code that does this, I'm sure. Or try google "binary tree expression evaluation"

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Apr 2007
    Posts
    21
    i already got the logic on paper.but i am not able to code my logic in C.i want to know how it stores while parsing.i guess it shud use double linked lists where every node has left and right child pointers.but how do we implement it in c coz we start evaluating from the left mode node and everytime we change the pointer.so how can we parse the right part?

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    So write it out as "pseudocode" or "english recepie" - one step at a time, and you shouldn't have to do that much to get the C code from that.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    Quote Originally Posted by cutelucks View Post
    so how can we parse the right part?
    Quote Originally Posted by matsp View Post
    Both the generation of the tree and the evaluation of the tree can be done by recursion.
    Do read the answers that are posted...

    QuantumPete
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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