CODEWITHSUNDEEP
calgorithmdata-structures
Hoang Nam
Hoang Nam

Reputation: 548

Binary Tree Implemetation in C for calculating

I'm reading a book about Data structures and I'm getting into trouble with the implementation example of binary tree in that book. The problem is I need to calculate and implement this parse tree below:

enter image description here

This is the source code of the example I mentioned above:

enter image description here

I've known about trees but I cannot understand what the source code really means because the book I'm reading does not explain each step. I really need the deeper explanation for the source code. EDIT : You can focus on the loop step, it is the most difficult one for me to understand

Upvotes: 0

Views: 402

Answers (1)

bereal
bereal

Reputation: 34282

This code seems to implement the Reverse polish notation, i.e. a notation where operators follow their operands. It reads an expression recorded in the RPN and builds the corresponding binary tree. For example, for the tree above the RPN form will be:

ABC+DE**F+*

The logic is pretty straightforward and is based on a stack that contains nodes of the tree:

  • Every time you encounter an operand (i.e. a letter), you create a new leaf node with an operand and push it to the stack.
  • Every time you encounter an operator, you create a new operator node, that replaces the two top-most nodes from the stack. The replaced nodes become the new node's children.

In the end, you get the expression tree on the top of the stack.

Update: As for the specific lines you mentioned: z is a special kind of tree node, a sentinel, that is depicted as a tiny rectangle on the picture. That's a no-value node, which allows you to know when you reach the tree bottom. Another way is just to use a null pointer (the link above compares the approaches).

z->l = z; 
z->r = z;

is what makes the node it's own child. A sentinel node can also represent an empty tree.

Now in the loop:

x->info = c;
x->l = z;
x->r = x;

creates a new leaf node (operand nodes don't have children). If we then find than the node is actually an operator, the children are immediately replaced with the operands from the stack.

Upvotes: 2

Related Questions