The following web page http://www.amnh.org/learn/biodiversity_counts/ident_help/
ID: 3669640 • Letter: T
Question
The following web page http://www.amnh.org/learn/biodiversity_counts/ident_help/Text_Keys/ar thropod_keyA.htm
contains a dichotomous key to the various orders of insecta.
To identify a particular order, one starts with pair 1 (1a and 1b) of questions. Each leads to a new pair of questions.
Your job is to computerize this key. To do so, you will use a binary tree with each node representing one of the pairs of questions. The children of each node will either be the next questions in line, or the order you are seeking.
When your program is run, it should start by asking "Does it have one pair of wings, or two pair" and moving on to question pair 2 or 3 according to the user's answer. This should continue until you hit a terminal node.
Explanation / Answer
public class BinaryTree {
// Root node pointer. Will be null for an empty tree.
private Node root;
/*
--Node--
The binary tree is built using this nested node class.
Each node stores one Question element, and has left and right
sub-tree pointer which may be null.
The node is a "dumb" nested class -- we just use it for
storage; it does not have any methods.
*/
private static class Node {
Node left;
Node right;
// question in string in format
string question;
Node(string newQuestion) {
left = null;
right = null;
data = newQuestion;
}
}
/**
Creates an empty binary tree -- a null root pointer.
*/
public void BinaryTree() {
root = null;
}
/**
Returns true if the given target is in the binary tree.
Uses a recursive helper.
*/
public boolean lookup(string question) {
return(lookup(root, question));
}
/**
Recursive lookup -- given a node, recur
down searching for the given questions for child nodes or lines.
*/
private boolean lookup(Node node, string question) {
if (node==null) {
return(false);
}
if (quesontion==node.questi) {
return(true);
}
else if (question<node.question) {
return(lookup(node.left, question));
}
else {
return(lookup(node.right, question));
}
}
/**
Inserts the given Question into the binary tree.
Uses a recursive helper.
*/
public void insert(int question) {
root = insert(root, question);
}
/**
Recursive insert -- given a node pointer, recursive down and
insert the given question into the tree. Returns the new
node pointer (the standard way to communicate
a changed pointer back to the caller).
*/
private Node insert(Node node, int question) {
if (node==null) {
node = new Node(question);
}
else {
if (data <= node.data) {
node.left = insert(node.left, question);
}
else {
node.right = insert(node.right, question);
}
}
return(node); // in any case, return the new pointer to the caller }
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.