I am trying to implement a set class that creates a binary tree out of Strings.
ID: 3717325 • Letter: I
Question
I am trying to implement a set class that creates a binary tree out of Strings. Currently when you run main you get:
Anna is not an employee of the company! (Find method)
[Ivan, Betty, Raquel, Anna, John, Sam, Valera] (Level Order Traversal)
I am not sure if my Put function is working correctly. I am using the compareTo method to compare strings. Is this right?
I am also not sure why my find function is returning that Anna is not an employee when the String.equal(String) method should yield true.
Please advise.
Here is my class.
//interface in Java
import java.util.LinkedList;
import java.util.Queue;
public class lab4Strashko {
private static Node root;
private static class Node {
public final String key;
public Node left, right;
public Node(String key) { this.key = key; }
}
//returns True if tree is empty
public static boolean isEmpty() {
return root==null;
}
// the number of nodes in the tree
public static int size() {
return size (root);
}
public static int size (Node x) {
if (x == null) return 0;
int sz = 1;
sz += size (x.left);
sz += size (x.right);
return sz;
}
public static void find(String name) {
int result = findhelp(root,name);
if (result==1) { System.out.printf("%s is an employee.", name);
}else {
System.out.printf("%s is not an employee of the company!", name);
}
}
public static int findhelp(Node x, String name) {
if (x==null) return 0;
String s = x.key;
if (s.equals(name)) {
return 1;
}
else {
findhelp(x.left, name);
findhelp(x.right, name);
}
return 2;
}
public static void erase(String s) {
removeLeaves(root, s);
}
public static void removeLeaves(Node x, String s) {
if (x==null) {
return;
}
if (x.key==s) {
x = null;
}
else {
removeLeaves(x.left, s);
removeLeaves(x.right, s);
}
}
public static void put(String key) {
root = put(root, key);
}
private static Node put(Node n, String key) {
if (n == null) return new Node(key);
if ((key.compareTo(n.key)<0)){
n.left = put(n.left, key);
}
else if ((key.compareTo(n.key)>0)){
n.right = put(n.right, key);
}
return n;
}
// Test for equality
public static boolean areEquals (lab4Strashko a, lab4Strashko b) {
return areEquals(lab4Strashko.root, lab4Strashko.root); }
private static boolean areEquals (Node x, Node y) {
if (x == null) {
return (y == null);
} else {
return (y != null) && x.key == y.key && areEquals (x.left, y.left) && areEquals (x.right, y.right);
}
}
// Create a tree from a string
public static lab4Strashko fromString (String ints) {
lab4Strashko set = new lab4Strashko ();
for (String s : ints.split (" "))
try { lab4Strashko.put (s); } catch (NumberFormatException e) {}
return set;
}
public static void print(){
if (root ==null){
return;
}
printhelp(root);
}
public static void printhelp (Node x) {
if (x == null){return;}
else{
System.out.println(x.key);
printhelp(x.left);
printhelp(x.right);
}
}
public static Iterable<String> levelOrder() {
Queue<String> keys = new LinkedList<>();
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node n = queue.remove();
if (n == null) continue;
keys.add(n.key);
queue.add(n.left);
queue.add(n.right);
}
System.out.print(keys);
return keys;
}
// String representation of the tree
public String toString() {
StringBuilder sb = new StringBuilder();
for (String key: levelOrder())
sb.append (key + " ");
return sb.toString ();
}
public static void main(String[] args) {
run (args);
}
// Tests for methods can be placed here
private static void run (String[] args) {
put("Ivan");
put("Raquel");
put("Betty");
put("Anna");
put("Sam");
put("John");
put("Valera");
find("Anna");
levelOrder();
find("Anna");
System.out.print("tests passed");
}
Explanation / Answer
I have corrected the findhelp() method.Please see it .rest all code is fine.
import java.util.LinkedList;
import java.util.Queue;
public class lab4Strashko {
private static Node root;
private static class Node {
public final String key;
public Node left, right;
public Node(String key) { this.key = key; }
}
//returns True if tree is empty
public static boolean isEmpty() {
return root==null;
}
// the number of nodes in the tree
public static int size() {
return size (root);
}
public static int size (Node x) {
if (x == null) return 0;
int sz = 1;
sz += size (x.left);
sz += size (x.right);
return sz;
}
public static void find(String name) {
int result = findhelp(root,name);
if (result==1) { System.out.printf("%s is an employee.", name);
}else {
System.out.printf("%s is not an employee of the company!", name);
}
}
public static int findhelp(Node x, String name) {
if (x==null) return 0;
String s = x.key;
if (s.equals(name)) {
return 1;
}
else {
int d= findhelp(x.left, name); //storing the return number
if(d==1)
return d; //If we found the element return 1(i.e d)
d=findhelp(x.right, name);
return d; //return the number d after goin gthrough the right side
}
// return 2;
}
public static void erase(String s) {
removeLeaves(root, s);
}
public static void removeLeaves(Node x, String s) {
if (x==null) {
return;
}
if (x.key==s) {
x = null;
}
else {
removeLeaves(x.left, s);
removeLeaves(x.right, s);
}
}
public static void put(String key) {
root = put(root, key);
}
private static Node put(Node n, String key) {
if (n == null) return new Node(key);
if ((key.compareTo(n.key)<0)){
n.left = put(n.left, key);
}
else if ((key.compareTo(n.key)>0)){
n.right = put(n.right, key);
}
return n;
}
// Test for equality
public static boolean areEquals (lab4Strashko a, lab4Strashko b) {
return areEquals(lab4Strashko.root, lab4Strashko.root); }
private static boolean areEquals (Node x, Node y) {
if (x == null) {
return (y == null);
} else {
return (y != null) && x.key == y.key && areEquals (x.left, y.left) && areEquals (x.right, y.right);
}
}
// Create a tree from a string
public static lab4Strashko fromString (String ints) {
lab4Strashko set = new lab4Strashko ();
for (String s : ints.split (" "))
try { lab4Strashko.put (s); } catch (NumberFormatException e) {}
return set;
}
public static void print(){
if (root ==null){
return;
}
printhelp(root);
}
public static void printhelp (Node x) {
if (x == null){return;}
else{
System.out.println(x.key);
printhelp(x.left);
printhelp(x.right);
}
}
public static Iterable<String> levelOrder() {
Queue<String> keys = new LinkedList<>();
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node n = queue.remove();
if (n == null) continue;
keys.add(n.key);
queue.add(n.left);
queue.add(n.right);
}
System.out.print(keys);
return keys;
}
// String representation of the tree
public String toString() {
StringBuilder sb = new StringBuilder();
for (String key: levelOrder())
sb.append (key + " ");
return sb.toString ();
}
public static void main(String[] args) {
run (args);
}
// Tests for methods can be placed here
private static void run (String[] args) {
put("Ivan");
put("Raquel");
put("Betty");
put("Anna");
put("Sam");
put("John");
put("Valera");
find("Anna");
levelOrder();
find("Anna");
System.out.print("tests passed");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.