April 1999
AP207: ADVANCED PROGRAMMING TECHNIQUES

QUESTION 4

Total Marks: 20 Marks

 Click here to access other questions

Click to access
SAMPLE STUDENT'S SOLUTIONS
for Question 4

 
(a) (i) Describe what is meant by a binary tree. [2]
(ii) Explain the difference between a binary tree and an N-ary tree. [1]
(iii) Write a declaration for a suitable type to represent a (dynamic) binary tree, which contains an Integer at each node.

 

 [3]
(b) Assume the following arithmetic expressions:
  • (A - B) * (C + D)
  • A * B + C

 
(i) Draw a tree structure diagram for each expression. [2]
(ii) Convert each expression into Pre-fix notation. [2]
(iii) Convert each expression into Post-fix notation.

 

 [2]
(c) (i) Write a recursive procedure - the prototype for which is given below - which takes the root of the binary tree above, and will perform a preorder traversal printing out the contents of each node as it traverses the tree. The nodes are of type Integer.

PROCEDURE PreOrderTraverser(Tree : TreeType);

 

 [4]
(ii) Write a recursive function, the prototype for which is given below, which will take the root of the binary tree above, and count the number of nodes in the tree by performing a postorder traversal

FUNCTION PostOrderTraverser(Tree : TreeType) : Integer;

 [4]