Consider a relation parent(X,Y) which means \'X\' is a parent of \'Y\' 3. (10 po
ID: 3748076 • Letter: C
Question
Consider a relation parent(X,Y) which means 'X' is a parent of 'Y'
3. (10 points) Consider a relation parent (X, Y) which means 'X' is a parent of Y (a) (5 points) Write all the facts (tuples) that describe the following tree VO V1 V2 V3 V4 V5 (b) (5 points) Consider the following rules for defining ancestor(X, Y): X is an ancestor of Y if X is a parent of Y. X is an ancestor of Y if X is a parent of some Z, and Z is an ancestor of Y. . . Write a datalog program and apply it to find all ancestors of all nodes in the above tree.Explanation / Answer
Answer:
3(a) (V0,V1) (V0,V2)(V1,V3)(V2,V4)(V2,V5)
3 (B) AN ANCESTOR OF A NODES V1 IS THE LOSWEST NODE WHICH HAS THE NODE V1 AS DESCENDANTS .
class Node
{
int data;
Node left, right, nextRight;
Node(int item)
{
data = item;
left = right = nextRight = null;
}
}
class BinaryTree
{
Node root;
/* If target is present in tree, then prints the ancestors
and returns true, otherwise returns false. */
boolean printAncestors(Node node, int target)
{
if (node == null)
return false;
if (node.data == target)
return true;
if (printAncestors(node.left, target)
|| printAncestors(node.right, target))
{
System.out.print(node.data + " ");
return true;
}
/* Else return false */
return false;
}
// code to test the program
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
/* Construct the binary tree
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.left.left.left = new Node(7);
tree.printAncestors(tree.root, 7);
}
}