Description

In this homework, you are asked to implement the following functions.

        1. Construct a binary tree

        2. Tree traversal

        3. Evaluate the height of a binary tree

        4. Determine whether a binary tree is complete or not

        5. Determine whether a binary tree is foldable or not

        6. QQ addition

        7. Delete all the leaves in a binary tree

You are not allow to use STL.

Implement your own stack to parse s-expression.

Input

Each test case contains multiple inputs. Each input is a string of s-expression.

Please note:

1) The length of each s-expression is at most 10000000.

2) The number of nodes in each tree is at most 1200000.

3) Each node’s weight is between -100000 and 100000.

Output

For each input s-expression, ouput its following things separated by a newline symbol.

• Pre-order traversal^#
• In-order traversal^#
• Post-order traversal^#
• The height of the binary tree
• Whether the binary tree is complete or not
• Whether the binary tree is complete or not
• QQ addition
• Pre-order traversal after deleting all the leaves^#
• In-order traversal after deleting all the leaves^#
• Post-order traversal after deleting all the leaves^#

^#Note: if the tree is empty, print nothing but a new line character for the pre/in/post –order traversal results

Sample Input  Download

Sample Output  Download

Tags

Discuss