questions 5, 6 and 7, If any of your methods call other methods, you must write
ID: 3568012 • Letter: Q
Question
questions 5, 6 and 7, If any of your methods call other methods, you must write the called methods as well. (18 points each) 5. Write a method called Ancestors that prints the value of all the ancestors of a node whose value is passed as a parameter. Notes: 1) If a node with the parameter value is not in the tree, do NOT print the ancestors, but print message specifying that the value is not in the tree 2) If the node has no ancestors, specify it in a message. 6. Write a method called Greater that returns the number of nodes in a binary tree that have a value greater than a parameter value. 7. Write a non-recursive postorder.Explanation / Answer
5)
Method for Ancestors, that prints the ancestor nodes.
//If target is present in tree, then prints the ancestors
and returns true, otherwise returns false.
bool Ancestors(Node root, int target)
{
// initial cases
if (root == NULL)
return false;
// initial cases
if (root.data == target)
{
return true;
}
// If target is present in either left or right subtree of this node,
// then print this node
if (Ancestors(root.left, target) ||
Ancestors(root.right, target) )
{
System.out.println( root.data+" ");
return true;
}
Else
{
System.out.println("There are no ancestors.");
}
/* Else return false */
return false;
}
------------------------------------------------------------------------------------------------------
6)
Method Greater, that returns the number of nodes greater than the target value.
Static int Greater(int target)
{
Node rt=root;
int count=0;
if(rt.data>target)
{
//calling the countNodes, where it returns
//the number of nodes greater than the target value
count=countNodes(rt.right);
}
return count+1;
}
//countNodes method, this returns the number of values greater than the target value
private int countNodes(Node root)
{
// Count the nodes in the binary tree whose values are greater
// the target value.
if ( root == null )
return 0;
else {
int count = 1; // Start by counting the root.
count += countNodes(root.left); // Add the number of nodes
// in the left subtree.
count += countNodes(root.right); // Add the number of nodes
// in the right subtree.
return count;
}
}
---------------------------------------------------------------------------------------------------------------------------
7)
An iterative method is an alternative method for non-recursive method of post order.
public void iterative(Node node)
{
Stack<Node> s = new Stack<Node>();
while(true)
{
while(node != null)
{
s.push(node);
node = node.left;
}
if(s.peek().right == null)
{
node = s.pop();
System.out.print(node.getData()+" --> ");
if(node == s.peek().right)
{
System.out.print(s.peek().getData()+" --> ");
s.pop();
}
}
if(s.isEmpty())
break;
if(s.peek() != null)
{
node = s.peek().right;
}
else
{
node = null;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.