|
(a) State one similarity and one difference
between the nodes of a binary tree and an n-ary tree. [2 marks]
(b) Draw a tree structure to represent
the expression ( ((a + b) * c) ^d ) [3 marks]
(c) Given the following dynamic tree
structure, used to model arithmetic expressions:
TYPE BTreeNodeDatum= (Leaf, Plus, Minus);
TYPE BTreeNodePtr= ^BTreeNode;
BTreeNode= RECORD
Left, Right : BTreeNodePtr;
Datum : BTreeNodeDatum;
END;
Write a function, called Calculate, which will return the value of
an arithmetic expression given in the above binary tree format. [5
marks]
(d) Given the following (alternative)
definition of a static binary tree:
TYPE BTreeNodeDatum = (Leaf, Plus, Minus);
TYPE BTreeNode = RECORD
LeftNodeIndex, RightNodeIndex : INTEGER;
Datum : INTEGER;
END;
BTree = ARRAY[1 .. MaxNodes] OF BTreeNode;
Write a function Position, the signature of which is given below,
which will traverse a tree of the type given above for a given entry
d, and will return the index in the array corresponding to the the
position of d. The LeftNodeIndex and teh RightNodeIndexin each BTreeNode
give the indices in the array of the left adn right subtrees respectively.
You can assume that a value of 0 for a left or right index indicates
there is no subtree on that node.
FUNCTION Position(rootTree: BTree;
d: INTEGER; currentNode: INTEGER): INTEGER; [5 marks]
|