Example Input: h c ( b ( a ( null null ) null ) f ( e ( null null ) g ( null nul

Question

Example Input:

h c ( b ( a ( null null ) null ) f ( e ( null null ) g ( null null ) ) )

Expected Output:

Could not find h
END OF OUTPUT

==================================================================

/**
A binary tree in which each node has two children.
*/
public class BinaryTree
{
private Node root;

/**
Constructs an empty tree.
*/
public BinaryTree() { root = null; }

/**
Constructs a tree with one node and no children.
@param rootData the data for the root
*/
public BinaryTree(Comparable rootData)
{
root = new Node();
root.data = rootData;
root.left = null;
root.right = null;
}

/**
Constructs a binary tree.
@param rootData the data for the root
@param left the left subtree
@param right the right subtree
*/
public BinaryTree(Comparable rootData, BinaryTree left, BinaryTree right)
{
root = new Node();
root.data = rootData;
root.left = null;
root.right = null;
if (left != null) { root.left = left.root; }
if (right != null){ root.right = right.root; }
}

class Node
{
public Comparable data;
public Node left;
public Node right;
}

/**
Checks whether this tree is empty.
@return true if this tree is empty
*/
public boolean isEmpty() { return root == null; }

/**
Gets the data at the root of this tree.
@return the root data
*/
public Comparable data() { return root.data; }

/**
Gets the left subtree of this tree.
@return the left child of the root
*/
public BinaryTree left()
{
BinaryTree result = new BinaryTree();
result.root = root.left;
return result;
}

/**
Gets the right subtree of this tree.
@return the right child of the root
*/
public BinaryTree right()
{
BinaryTree result = new BinaryTree();
result.root = root.right;
return result;
}
}

====================================================

import java.util.*;

public class PoD
{

//=============================================================================

/**
* Tries to find an object within the binary tree and
* returns true if found and false if not
*
* @param obj Comparable to search for in tree
* @param tree BinaryTree of interest
* @return boolean value true if object is found, false if not
*/

public static boolean findValue(Comparable value, BinaryTree tree)
{

}

//=============================================================================

public static void main(String[] args)
{

Scanner in = new Scanner(System.in);

Comparable value = in.next();
BinaryTree newTree = buildTree(in);

boolean foundItem = findValue(value, newTree);

if (foundItem)
{
System.out.println("Found " + value);
}
else
{
System.out.println("Could not find " + value);
}

in.close();
System.out.print("END OF OUTPUT");
}

public static BinaryTree buildTree(Scanner in)
{
String data = in.next();
BinaryTree left = null;
BinaryTree right = null;

if (data.equals("null")) { return null;}

if (!in.next().equals("(")) { System.out.println("BAD INPUT: (L"); }

left = buildTree(in);
right = buildTree(in);

if (!in.next().equals(")")) { System.out.println("BAD INPUT: R)"); }

return new BinaryTree(data, left, right);
}

}

Input The main method (already completed) creates a binary tree and passes a Comparable object to search for and the binary tree to search to the method findValue. Processing You are going to complete the details of findValue method. Details of each method and their expected parameters are described in the Javadoc comments preceding it. The method should return true if the value is found within the binary tree, and return false if not. Output Output will be handled by the main method based on the value you return

Explanation / Answer

public static boolean findValue(Comparable value, BinaryTree tree) { if(tree == null) { return false; } else if(tree.data().compareTo(value) == 0) { return true; } else { return findValue(value, tree.left()) || findValue(value, tree.right()); } }

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.