TREE

1. What is the difference between a tree and a binary tree?

2. Draw an expression tree for each of the following expressions:

(a) 5

(b) (5+6*4)/2

(c) (5+6*4)/2-3/7

(d) 1+9*((5+6*4)/2-3/7)

(e) A B (C + D) (P /Q)

3. Hand draw binary expression trees that correspond to the expressions for which

(a) The infix representation is P /(Q + R) X Y

(b) The postfix representation is X Y Z P QR +/

(c) The prefix representation is + M N P /RS

4. For each expression tree drawn in the above question, list the sequence of elements encountered in inorder, preorder and postorder traversals.

5. Describe, with an example of 5 nodes, the topological characteristics that distinguish a tree from a linked list.

6. Define a treeNode class for tree nodes that each consists of following 4 fields:

parent leftChild rightChild data

7. Following the above node definition, define and implement a binary tree class with necessary access methods for the 4-field treeNodes, for example, setXXX, getXXX, isEmpty, etc..

8. Write a method that takes two binary trees t1, t2 and a binary tree node v as the arguments. It constructs and returns a new binary tree that has v as its root and whose left subtree is t1 and whose right subtree is t2. Both t1 and t2 should be empty on

completion of the execution.