December 1999
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 2

Total Marks: 15 Marks

Click here to access other questions

Click to access
SUGGESTED SOLUTIONS
for Question 2

(a)

Describe what is meant by an ordered binary tree .

 

[2]
(b)

Given the arithmetic expression (B ^ A )/(C + D )

(i)Draw a tree structure diagram to represent the expression;[2 marks ]

(ii)Convert the expression into Pre-fix notation;[2 marks ]

(iii)Convert the expression into Post-fix notation.[2 marks ]

 

[6]
(c)

Given the following definition of a binary tree:

TYPE

BTreeNodePtr = ˆBTreeNode
BTreeNode      = RECORD

                         Left, Right : BTreeNodePtr;
                         Datum : INTEGER;

                         END;

(i)Describe what is meant by an In-fix (In-order)traversal of a binary
tree.[2 marks ]


(ii)Write a recursive procedure, the signature of which is given below,which takes in a binary tree of the type given above, and performs an In-fix traversal of the tree. The procedure should print out the value stored at each node as it is traversed, and sum the value stored at each node, returning the sum as a reference parameter [5 marks ]


PROCEDURE InFixTraversalSum(root: BTreeNodePtr, VAR Sum:
INTEGER);

[7]