1. Write a class ParseTree that transforms a postfix algebraic expression into a parse tree. The argument for the constructor is the string containing the expression. Operands are single letters and the allowed operators are +, -, *, and /.

The only methods you need for the tree are:

ParseTree(std::string expression) constructor; create a tree based on expression

~ParseTree() destructor; clean up any allocated memory

std::string preOrder() perform a pre-order traversal, returning the resulting prefix expression

std::string inOrder() perform a in-order traversal, returning the resulting infix expression

std::string postOrder() perform a post-order traversal, returning the resulting postfix expression

Note that your in-order traversal (infix) will need to add parentheses to the output to avoid generating ambiguous expressions. You can do this by adding an opening parenthesis before the first recursive call and a closing parenthesis after the second recursive call. If you want to have a cleaner output, you can check for nulls before making the recursive calls and only display parentheses when needed.

2. For this problem, you are to create a max-heap where the root is the largest value and the leaves are the smallest. You can either use the example code provided in Moodle as a starting point or code it yourself.

Your Heap class should implement the following methods:

Heap(int size) constructor; create an array of size integers to hold your heap. Use 16 for your default size.

~Heap() destructor; clean up any allocated memory

void insert(int value) add value to the heap in the proper location. If the heap is too small, double it before adding

int remove() remove the largest value from the heap. Throw std::length_error if the heap is empty

int largest() return the largest value, but do not delete it. Throw std::length_error if the heap is empty.

The methods you need to implement in the priority queue class are:

PriorityQueue(int size) constructor; create an heap of size length

~PriorityQueue() destructor; clean up any allocated memory

void insert(int value) add value to the priority queue

int peek() return the largest value in the priority queue.

int remove() remove and return the largest value in the priority queue