Problem 1: Write a class that implements a generic binary search tree including
ID: 3833449 • Letter: P
Question
Problem 1: Write a class that implements a generic binary search tree including the methods add, contains and printInorder. (We will do this as a group)
Problem 2: Add a toString method to the class. This method returns a string of the form “[e1, e2, …, en]” containing all of the elements in the tree in order.
Problem 3: Add a method to the class that returns the number of leaves in the tree.
Problem 4: Add a clone method to the class that returns a copy of the tree. Remember that we have three different ways of traversing a tree: preorder, inorder and postorder. Does it matter which one you use in this method?
Problem 5: Add an equals method to the class. Two trees are equal if they include the same elements. The structure of the trees does not have to be the same.
_______
import java.util.Random;
public class Tree<E extends Comparable<E>> {
public static void main(String[] args) {
Random rand = new Random();
Tree <Integer> t = new Tree<Integer>();
for(int i=0; i<20; i++) {
int x = rand.nextInt(100);
System.out.print(x + " ");
t.add(x);
}
System.out.println(" Size: " + t.size());
t.print();
String[] dwarves = {"11", "22", "33", "44", "55", "66", "77"};
Tree<String> dwarfs = new Tree<String>();
for (String s : dwarves){
dwarfs.add(s);
}
dwarfs.print();
System.out.println(dwarfs.toString());
}
private class Node {
E element;
Node left;
Node right;
}
private Node root;
private int size;
public Tree() {
root = null;
size = 0;
}
public String toString(){
String s = new String();
return toString(this.root,s);
}
public String toString(Node current,String s) {
if (current != null) {
toString(current.left,s);
s+=current.element;
toString(current.right,s);
}
return s;
}
public int size() {
return size;
}
public boolean contains(E x) {
return contains(x, root);
}
private boolean contains(E x, Node current) {
if (current == null) {
return false;
} else if (current.element.equals(x)) {
return true;
} else if (x.compareTo(current.element) < 0) {
return contains(x, current.left);
} else {
return contains(x, current.right);
}
}
public void print() {
print(root);
System.out.println();
}
private void print(Node current) {
if (current != null) {
print(current.left);
System.out.print(current.element + " ");
print(current.right);
}
}
public void add(E e) {
root = add(e, root);
size++;
}
private Node add( E e, Node current) {
if(current == null) {
Node n = new Node();
n.element = e;
return n;
} else if (e.compareTo(current.element) < 0) {
current.left = add(e, current.left);
} else {
current.right = add(e, current.right);
}
return current;
}
}
Explanation / Answer
import java.util.Random;
public class Tree<E extends Comparable<E>> {
public static void main(String[] args) {
Random rand = new Random();
Tree <Integer> t = new Tree<Integer>();
for(int i=0; i<20; i++) {
int x = rand.nextInt(100);
System.out.print(x + " ");
t.add(x);
}
System.out.println(" Size: " + t.size());
t.print();
String[] dwarves = {"11", "22", "33", "44", "55", "66", "77"};
Tree<String> dwarfs = new Tree<String>();
for (String s : dwarves){
dwarfs.add(s);
}
dwarfs.print();
System.out.println(dwarfs.toString());
}
private class Node {
E element;
Node left;
Node right;
}
private Node root;
private int size;
public Tree() {
root = null;
size = 0;
}
public String toString(){
String s = new String();
return toString(this.root,s);
}
public String toString(Node current,String s) {
if (current != null) {
toString(current.left,s);
s+=current.element;
toString(current.right,s);
}
return s;
}
public int size() {
return size;
}
public boolean contains(E x) {
return contains(x, root);
}
private boolean contains(E x, Node current) {
if (current == null) {
return false;
} else if (current.element.equals(x)) {
return true;
} else if (x.compareTo(current.element) < 0) {
return contains(x, current.left);
} else {
return contains(x, current.right);
}
}
public void print() {
print(root);
System.out.println();
}
private void print(Node current) {
if (current != null) {
print(current.left);
System.out.print(current.element + " ");
print(current.right);
}
}
public void add(E e) {
root = add(e, root);
size++;
}
private Node add( E e, Node current) {
if(current == null) {
Node n = new Node();
n.element = e;
return n;
} else if (e.compareTo(current.element) < 0) {
current.left = add(e, current.left);
} else {
current.right = add(e, current.right);
}
return current;
}
}