binary tree

**cutelucks** · 09-25-2007

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

**matsp** · 09-25-2007

Try recursing over the tree, perhaps?

--
Mats

**cutelucks** · 09-25-2007

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

**matsp** · 09-25-2007

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

**cutelucks** · 09-25-2007

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?

**matsp** · 09-25-2007

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

**QuantumPete** · 09-25-2007

Originally Posted by cutelucks

so how can we parse the right part?

Originally Posted by matsp

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

Thread: binary tree

Thread Tools

Search Thread

Display

binary tree

Similar Threads

binary interface to binary search tree giving me SUCH A HEADACHE!!

Binary Search Trees Part III

Tutorial review

Request for comments

BST/Red and Black Tree