In this assignment, you will implement structures that contain pointers and a set of functions. You will read a sequence of words from the std. input using cin. Store the incoming words in a tree structure as shown below:

struct node{

string word;

node* left;

node* right;

node* father;

};

All structure objects should be allocated dynamically using new operator. Assume that you read 6 words, in this order: A B C D E F. The structure of the tree will be constructed such that the following node relations will be formed between the nodes:

Notice that the tree isn't created by comparing the values and sorted. It's unsorted. Just took the values one by one.

Each incoming node will be placed in the next empty slot in a tree level, from left to right order. When that level is filled, the incoming node is stores to the leftmost position of the next level. In this tree, the node at the top of the tree is called the root node. Each node can have at most two child nodes. The one on the left is called as left child, on the right is called as the right child. The tree definition is recursive, i.e. the left child of A, is also a tree that is rooted at B with the left child D and the right child E.

The incoming word list will be terminated with the end string.

You will implement the following four functions. Note that each function has an ID, which will be provided in the input format to specify the requested function.

Function id [1]: traverses and prints the words in the tree in pre-order form: (1) print the word at the root, (2) print the word at the left subtree in pre-order, (3) print the word at the right subtree in pre-order. Ex: The output for the example tree will be: A B D E C F

Function id [2]: traverses and prints the words in the tree in post-order form: (1) print the word at the left subtree in post-order, (2) print the word at the right subtree in postorder, (3) print the word at the root. Ex: The output for the example tree will be: D E B F C A

Function id [3]: traverses and prints the words in the tree in in-order form: (1) print the word at the left subtree in in-order, (2) print the word at the root, (3) print the word at the right subtree in in-order. Ex: The output for the example tree will be: D B E A F C

Function id [4]: prints the nodes that does not have any child, from left to right. Ex: The output for the example tree will be: D E F

The function id will be provided as input to your program; you will call the corresponding function. Functions can be queried in any order. Your program will be terminated when -1 is given from the input as a function id.

Input format: [ WS]

end

[ WS]

-1 [..] encodes at least one relation. WS: represents white space characters Ouput format: *****Newline [Newline] Done!

root level 0 level 1 level 2