Talk:Binary expression tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.


The input is: a b + c d e + * *

Expression Tree

Since the first two symbols are operands, one-node trees are created and pointers are pushed to them onto a stack. For convenience the stack will grow from left to right.

Stack growing from Left to Right

The next symbol is a '+'. It pops the two pointers to the trees, a new tree is formed, and a pointer to it is pushed onto to the stack.

Formation of a New Tree

Next, c, d, and e are read. A one-node tree is created for each and a pointer to the corresponding tree is pushed onto the stack.

Creating One-Node Tree

Continuing, a '+' is read, and it merges the last two trees.

Merging Two Trees

Now, a '*' is read. The last two tree pointers are popped and a new tree is formed with a '*' as the root.

Forming a New Tree with a Root

Finally, the last symbol is read. The two trees are merged and a pointer to the final tree remains on the stack.

Steps to Construct an Expression tree a b + c d e + * *

[1] PratikNadagouda (talk) 18:10, 14 September 2011 (UTC)

Saurabh29 (talk) 18:28, 14 September 2011 (UTC)

  1. ^ Cite error: The named reference Gopal2010 was invoked but never defined (see the help page).