April 2000
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 3

Total Marks: 15 Marks

• Question 1
• Question 2
• Question 4
• Question 5
• Cover Page

Click to access
SUGGESTED SOLUTIONS
for Question 3

(a)Explain what is meant by a binary search tree with respect to a binary
tree.[2 marks ]

(b)Assume the following arithmetic expression:
A + B ˆ C /D
(i)Give the fully bracketed form of this expression.[2 marks ]
(ii)Draw a tree structure to represent the expression.[2 mark ]
(iii)Convert the expression into Pre-fix notation;[2 marks ]
(iv)Convert the expression into Post-fix notation.[2 marks ]

(c)Assume the following definition of a binary tree:

TYPE
  BTreeNodePtr = ˆBTreeNode;
  BTreeNode = RECORD
      Left, Right : BTreeNodePtr;
      Datum : INTEGER;
      END;

Write a recursive procedure,called PrintCountTree the signature of which is given below,which will perform a post order traversal of the tree root printing out the value of Datum stored at each node.
PROCEDURE PrintCountTree(root: BTreeNodePtr);
[5 marks ]