Exercise 2.1 For each of the following tree operations, invent an expression whi
ID: 3744006 • Letter: E
Question
Exercise 2.1 For each of the following tree operations, invent an expression which encodes it, briefly describe how it works, and B-reduce an example to show it that works.) .NIL should represent an empty tree. . (MAKETREE e a b) should make a tree with e at the root, and with the given subtrees a, b attached as the left and right children. Give a couple of examples. (ROO ) shouhnttedat the root of the tree. (LEFT ) should return the subtree which is the left child of the root. (RIGHT t) should return the subtree which is the right child of the root. (ISEMPTY t) should return TRUE if the tree is empty, FALSE otherwise. · (ISLEAF t) should return TRUE if the tree is just a leaf, FALSE otherwise. You do not have to include error handling (i.e. it doesn't matter what a nonsense expression like LEFT NIL) reduces to. Exercise 2.2 Using the operations you defined above, write recursive expressions for the following, more complex func- tions. briefly describe how they work, but you do not need to give fully worked examples. (SUM t) should sum all the values stored in the tree. (HEIGHT t) should return the height of the tree. ISPROPER t) should return TRU E if t is a proper tree (every position is either a leaf, or it has 2 children). .(MAKEPROPER t) should return a proper tree, equivalent to the original tree except wherever a position had exactly one child, that child is no longer in the tree (i.e. we return the maximal proper subtree of t.)Explanation / Answer
Basic Structure:
Lets consider the below structure for each node of a tree.
Type Node<Tree>
{
AnyType value;
Node<Tree> parent;
Node<Tree> left;
Node<Tree> right;
….
}
Lets consider t to be node of type Tree described above.
t.parent will return reference to parent node.
t.left will return the reference to the left child
t.right will return reference to right child
t.value will return the element stored at node t.
A Tree will be referenced by its root node t.
Operations:
NIL
A NIL or empty tree can be evaluated with help of ISEMPTY operation.
A tree is NIL (empty tree) if ISEMPTY returns TRUE, otherwise tree is not NIL.
(MAKETREE e a b)
Considering that e, a and b are references to trees, below expressions should construct the required tree;
e.left=a;
Explanation: It will make the left link of root node e refer to the root node a, so that node a will become the left subtree of e.
Similarly subtree b can be added as the right subtree of e-
e.right=b;
(ROOT t)
Considering that t holds the reference to root of the tree, below expression will suffice for this operation:
element_at_t=t.value
where element_at_t is the value or element represented by root node t.
(LEFT t)
Below expression will give a reference to root element of left subtree of the tree t.
a> l=t.left;
where l is the reference to left subtree of Tree t.
(RIGHT t)
Below expression will give a reference to root element of right subtree of the tree t.
r=t.left;
where r is the reference to right subtree of Tree t.
(ISEMPTY t)
ISEMPTY should return TRUE if below condition is TRUE
t.left == null && t.right==null && t.value==null;
Otherwise it should return false.
(ISLEAF t)
ISLEAF will return TRUE if a node has no child
Expression:
If(t.left==null && t.right==null), then the node t is a leaf node.
Otherwise it is a non-leaf node.
Note: For every above operation is necessary to add (ISEMPTY t == FALSE) check to validate that the tree is NOT EMPTY.
Recursive Expressions:
(SUM t)
while ( not ISEMPTY t )
{
if (ISLEAF t)
{
total=total+t.value
continue;
}
if(not LEFT t)
{
total=total + t.value + SUM(RIGHT t)
continue;
}
if(not RIGHT t)
{
total=total + t.value + SUM(LEFT t)
continue;
}
total=total + t.value + SUM(LEFT t) + SUM(RIGHT t)
}
Explanation for SUM t:
There are three situations which may be encountered and should be handled as follows
If current node is a leaf node then add its element and skip to continue with the next iteration.
If the current node has no left subtree then add its element and proceed with taking sum of right subtree.
If the current node has no right subtree then add its element and proceed with taking sum of left subtree.
For other nodes, add its element and proceed with calculating sum of the left subtree and then the right subtree.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.