Construct binary tree of pre-order, post-order and in-order expression

0
votes

I searched internet and "you tube" but I didn't find any good tutorial for this. How can I draw corresponding "binary tree" of a given expression in “postfix”?

And how would this expression look in infix and prefix?

I don’t know how I should do this step by step :(

18 5 1 + / 4 * 3 5 18 6 / - + -

Note:

The rule for drawing pre-order, post-order and in-order is: 1. pre-order traversal: root, left, right 2. post-order traversal: left, right, root 3. in-order traversal: left root, right

Please I need it for exam

1
inorderpreorderpostorder
Please clarify what you need. Drawing binary tree means building a binary tree or actually plotting something? - Stefano Sanfilippo
I want to show this expression as binary tree. (the tree that has root as parent and left/right node as children). Actually I give the nodes of the tree (in this question 15 nodes) - Omid7
Yes, we know what a binary tree is. I do not know what is you request. Recursively printing a tree is a basic exercise and, since you appear to be a CS student, you should know it. Building a tree from postfix is detailed below. - Stefano Sanfilippo

1 Answers

1
votes

Scan the expression left to right. When you find a number, build a (leaf) node, then push it in a stack. When you find an operator, build a node, pop two nodes from the stack, connect them as left and right son of the current node, then push the node on the stack and continue. At the end of the string, you must have only the root on the stack

When you have the tree, finding prefix and infix is trivial.

Note that this is based on the assumption that every operator takes two values (could be adapted to unary operators easily), that is, every internal node has two children. In general, it is impossible to build a tree from postfix (see wikipedia).