Question
Instructions Copy the methods from your BinarySearchTree class from previous assignment In this assignment, add the following methods. You are also given a method that
Instructions
Copy the methods from your BinarySearchTree class from previous assignment
In this assignment, add the following methods. You are also given a method that will return a String that prints out the tree in a nice visual format.
// returns the lowest value according
// to the classes natural orderingpublic Comparable getLowest()
// returns the highest value according
// to the classes natural orderingpublic Comparable getHighest()
// returns true if the left and right side
// of the tree differ by 1 or less. public boolean isBalanced()
// returns a levelOrder representation of// the tree. You will need to use a queue
// datastructure for this.public String levelOrder()
Example output:
In order [10, 15, 20, 25, 35, 40, 45, 55, 60, 70, 80]
Pre order [60, 25, 15, 10, 20, 40, 35, 55, 45, 80, 70]
Post order [10, 20, 15, 35, 45, 55, 40, 25, 70, 80, 60]
Level Order [60, 25, 80, 15, 40, 70, 10, 20, 35, 55, 45]
Width 7
Levels 5
Lowest 10
Highest 80
isBalanced false
Binary Search Tree (Maximum of 5 levels shown.
60
|-----------------------^-----------------------|
25 80
|-----------^-----------| |.-----------^
15 40 70 |-----^-----| |-----^-----|
10 20 35 55
|--^
45
BinarySearchTree.java
public class BinarySearchTree {
private Node root;
public BinarySearchTree() { root = null; }
public void add(Comparable val) { root = add(val, root); }
private Node add(Comparable val, Node current) { if (current == null) { return new Node(val); }
if (val.compareTo(current.data) < 0) { current.left = add(val, current.left); } else if (val.compareTo(current.data) > 0) { current.right = add(val, current.right); } return current; } public boolean contains (Comparable val) { return contains(val, root); }
private boolean contains (Comparable val, Node current) { if (current == null) { return false; } else if (val.compareTo(current.data) < 0) { return contains(val, current.left); } else if (val.compareTo(current.data) > 0) { return contains(val, current.right); } else { return true; } }
// The following three methods should include commas and square brackets // For example, [1, 3, 5, 7, 9] public String inOrder() { String str = inOrder(root); return "[" + str.substring(0, str.length() - 2) + "]"; }
private String inOrder(Node current) { if (current == null) { return ""; } return inOrder(current.left) + current.data + ", "+ inOrder(current.right); }
public String preOrder(){ String str = preOrder(root); return "[" + str.substring(0, str.length() - 2) + "]"; } private String preOrder(Node current) { if (current == null) { return ""; } return current.data + ", "+ preOrder(current.left) + preOrder(current.right); } public String postOrder(){ String str = postOrder(root); return "[" + str.substring(0, str.length() - 2) + "]"; } private String postOrder(Node current) { if (current == null) { return ""; } return postOrder(current.left) + postOrder(current.right) + current.data + ", "; }
public int getHeight() { return getNumLevels()-1; }
public int getWidth(){ return getWidthLeft(root) + getWidthRight(root) -1; }
private int getWidthLeft(Node current){ if(current == null){ return 0; } else { if(current.left != null){ return 1 + getWidthLeft(current.left); } else { return 1 + getWidthLeft(current.right); } } }
private int getWidthRight(Node current){ if(current == null){ return 0; } else { if(current.right != null){ return 1 + getWidthRight(current.right); } else { return 1 + getWidthRight(current.left); } } }
public int getNumLeaves(){ return (getNumLeaves(root))/2; }
private int getNumLeaves(Node current){ if(current == null){ return 1; } else{ return getNumLeaves(current.right) + getNumLeaves(current.left); } }
public int getNumLevels(){ return (getNumLevels(root)); }
private int getNumLevels(Node current){ if (current == null) { return 0; } else { int numLeft = getNumLevels(current.left); int numRight = getNumLevels(current.right); if (numLeft > numRight) { return 1 + numLeft; } else { return 1 + numRight; } } }
public int size(){ return size(root); }
private int size(Node current){ if(current == null){ return 0; } else{ return 1+size(current.right)+size(current.left); } }
public String toString(){ return inOrder(); }
}
Main.java
class Main { public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree();
tree.add(60); tree.add(25); tree.add(15); tree.add(40); tree.add(80); tree.add(10); tree.add(70); tree.add(40); tree.add(55); tree.add(20); tree.add(35); tree.add(45);
System.out.println(); System.out.println("In order " + tree.inOrder()); System.out.println("Pre order " + tree.preOrder()); System.out.println("Post order " + tree.postOrder()); System.out.println("Level Order " + tree.levelOrder()); System.out.println("Width " + tree.getWidth()); System.out.println("Levels " + tree.getNumLevels()); System.out.println("Lowest " + tree.getLowest()); System.out.println("Highest " + tree.getHighest()); System.out.println("isBalanced " + tree.isBalanced());
System.out.println(tree.printTree(5));
} }
Node.java
class Main { public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree();
tree.add(60); tree.add(25); tree.add(15); tree.add(40); tree.add(80); tree.add(10); tree.add(70); tree.add(40); tree.add(55); tree.add(20); tree.add(35); tree.add(45);
System.out.println(); System.out.println("In order " + tree.inOrder()); System.out.println("Pre order " + tree.preOrder()); System.out.println("Post order " + tree.postOrder()); System.out.println("Level Order " + tree.levelOrder()); System.out.println("Width " + tree.getWidth()); System.out.println("Levels " + tree.getNumLevels()); System.out.println("Lowest " + tree.getLowest()); System.out.println("Highest " + tree.getHighest()); System.out.println("isBalanced " + tree.isBalanced());
System.out.println(tree.printTree(5));
} }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started