Preliminaries
Download the template class and the driver file.
Objective
Learn how to traverse a binary search tree in order.
Description
For the template class BinarySearchTree, fill in the following methods:
insert - Inserts values greater than the parent to the right, and values lesser than the parent to the left.parameters
elem - The new element to be inserted into the tree.
printInOrder - Prints the values stored in the tree in ascending order.
Hint: Use a recursive method to visit the left subtree, then print out the value, then visit the right subtree.
getDepth - Finds the depth of a node within the tree. Depth is defined as the number of edges from the root to the nodeparameters
elem - The element to find the depth of
return The depth of the element within the tree. If the value is not found, -1 is returned.
Template Class:
public class BinarySearchTree<E extends Comparable<E>> { private class Node<E> { private E data; private Node<E> left; private Node<E> right; public Node(E data) { this.data = data; this.left = null; this.right = null; } } private Node<E> root; public BinarySearchTree() { root = null; } /** * Inserts an element into the tree. * @param elem The new element to be inserted into the tree. */ public void insert(E elem) { // Finish this method } /** * Prints the values stored in the tree in ascending order. */ public void printInorder() { // Finish this method } /** * Finds the depth of a node within the tree. Depth is defined * as the number of edges from the root to the node. * @param elem The element to find the depth of * @return The depth of the element within the tree. If the value * is not found, -1 is returned. */ public int getDepth(E elem) { // Finish this method } /* Do not modify below this line! */ /* -------------------------------------------------------------- */ /** * Checks whether the nth bit within an integer is set. * @param number The number to check * @param index The index of the bit to find * @return True if the nth bit is set. For example, (5, 1) is true * since 5 = b101, and the ones place is set. Similarly, (5, 2) * is false. */ private static boolean nthBitSet(int number, int index) { int constant = 1 << (index - 1); return (number & constant) != 0; } /** * Prints an ascii representation of the tree. * @param root The current node to print * @param depth The level of the tree in which the current node lies. * Levels are counted with the root starting at 0. * @param isLeft Whether the current node is a left child. * @param parBits A bitstring (integer) representing the parents * in the path above this node. Used to 'fill in * the gaps' in the drawing. * @param buffered Whether this was called to specifically include * additional whitespace on the left */ public void printAscii(Node<E> root, int depth, boolean isLeft, int parBits, boolean buffered) { if (root == null) { return; } for (int i = 0; i < (depth - 1) * 3; i++) { if (i % 3 == 1 && nthBitSet(parBits, depth - (i / 3))) { System.out.print("|"); } else { System.out.print(" "); } } if (isLeft && depth != 0 && !buffered) { System.out.print(" `- "); } else if (depth != 0 && !buffered) { System.out.print(" |- "); } if (buffered) { for (int i = 0; i < depth * 3; i++) { System.out.print(" "); } } System.out.println(root.data); boolean hasRight = root.right != null; boolean hasLeft = root.left != null; int newParBits = parBits << 1; if (hasLeft) { newParBits++; } printAscii(root.right, depth + 1, !hasLeft, newParBits, false); printAscii(root.left, depth + 1, true, --newParBits, false); } /** * Prints an ascii representation of the tree. */ public void printAscii() { printAscii(root, 0, false, 0, false); } }
Driver file:
import java.util.ArrayList; import java.util.Random; public class TreeTester { public static final int RANDOM_TEST_SIZE = 15; /** * Run tests. */ public static void main(String[] args) { System.out.println("Integer test"); testInt(); System.out.println("----------"); System.out.println("Randomized Char test"); randomCharTest(); } /** * Test BinarySearchTree on a predetermined selection of integers. */ public static void testInt() { BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>(); int[] valArr = {4,8,10,2,1,7,3,5,9,6}; for (int i : valArr) { tree.insert(i); } System.out.println("Tree:"); tree.printAscii(); System.out.println("Testing insertion by in-order traversal"); tree.printInorder(); System.out.print("Depth of 6: "); System.out.println(tree.getDepth(6)); System.out.print("Getting depth of 14: "); System.out.println(tree.getDepth(14)); } /** * Test BinarySearchTree on a random selection of characters. */ public static void randomCharTest() { BinarySearchTree<Character> tree = new BinarySearchTree<Character>(); // Create the list of chars ArrayList<Character> alphabet = new ArrayList<Character>(); for (int i = 97; i < 123; i++) { alphabet.add((char) i); } Random rand = new Random(); ArrayList<Character> inTree = new ArrayList<Character>(); for (int i = 0; i < RANDOM_TEST_SIZE; i++) { int removeIndex = rand.nextInt(alphabet.size()); Character charToAdd = alphabet.remove(removeIndex); tree.insert(charToAdd); inTree.add(charToAdd); } tree.printAscii(); System.out.println("Testing insertion by in-order traversal"); tree.printInorder(); // Test the depth of two elements in the tree System.out.println("Finding depth of random elements within the tree:"); for (int i = 0; i < 2; i++) { int randIndex = rand.nextInt(inTree.size()); System.out.print("Depth of " + inTree.get(randIndex) + ": "); System.out.println(tree.getDepth(inTree.get(randIndex))); } ArrayList<Character> outOfTree = alphabet; System.out.println("Finding depth of random elements outside the tree:"); int randIndex = rand.nextInt(outOfTree.size()); System.out.print("Depth of " + outOfTree.get(randIndex) + ": "); System.out.println(tree.getDepth(outOfTree.get(randIndex))); } }
Example Dialog
Integer test Tree: 4 |- 8 | |- 10 | | `- 9 | `- 7 | `- 5 | `- 6 `- 2 |- 3 `- 1 Testing insertion by in-order traversal 1 2 3 4 5 6 7 8 9 10 Depth of 6: 4 Getting depth of 14: -1 ---------- Randomized Char test i |- t | |- w | | `- y | | `- z | `- r | |- s | `- k | `- n | `- p `- c |- e | `- h | `- f `- b Testing insertion by in-order traversal b c e f h i k n p r s t w y z Finding depth of random elements within the tree: Depth of e: 2 Depth of z: 4 Finding depth of random elements outside the tree: Depth of x: -1
Provided java code as per your requirements.
Java Code:
public class BinarySearchTree<E extends
Comparable<E>> {
private class Node<E> {
private E data;
private Node<E> left;
private Node<E> right;
public Node(E data) {
this.data = data;
this.left = null;
this.right = null;
}
}
private Node<E> root;
public BinarySearchTree() {
root = null;
}
/**
* Inserts an element into the tree.
*
* @param elem
*
The new element to be inserted into the tree.
*/
public void insert(E elem) {
Node<E> newNode = new
Node<E>(elem);
if (root == null)
root = newNode;
else {
Node<E> current = root;
Node<E> parent;
while (true) {
parent = current;
if (((Comparable<E>)
elem).compareTo(current.data) < 0) {
current = current.left;
if (current == null) {
parent.left = newNode;
return;
}
} else {
current = current.right;
if (current == null) {
parent.right = newNode;
return;
}
}
}
}
}
/**
* Prints the values stored in the tree in ascending order.
*/
public void printInorder() {
printInInorder(root);
}
private void printInInorder(Node<E> root) {
if (root != null) {
printInInorder(root.left);
System.out.print(root.data + " ");
printInInorder(root.right);
}
}
/**
* Finds the depth of a node within the tree. Depth is defined as
the number
* of edges from the root to the node.
*
* @param elem
*
The element to find the depth of
* @return The depth of the element within the tree. If the value is
not
* found, -1 is
returned.
*/
public int getDepth(E elem) {
Node<E> temp = get(elem);
return getDepth(temp);
}
public Node<E> get(E elem) {
if (root == null) {
return null;
}
Node<E> runner = root;
while (true) {
if (((Comparable<E>)
runner.data).compareTo(elem) > 0) {
if (runner.left == null) {
return null;
}
runner = runner.left;
} else if (((Comparable<E>)
runner.data).compareTo(elem) < 0) {
if (runner.right == null) {
return null;
}
runner = runner.right;
} else {
return runner;
}
}
}
public int getDepth(Node<E> node) {
if (node == null)
return 0;
else {
int lheight = getDepth(node.left);
int rheight = getDepth(node.right);
if (lheight > rheight)
return (lheight + 1);
else
return (rheight + 1);
}
}
/* Do not modify below this line! */
/* --------------------------------------------------------------
*/
/**
* Checks whether the nth bit within an integer is set.
*
* @param number
*
The number to check
* @param index
*
The index of the bit to find
* @return True if the nth bit is set. For example, (5, 1) is true
since 5 =
* b101, and the
ones place is set. Similarly, (5, 2) is false.
*/
private static boolean nthBitSet(int number, int index) {
int constant = 1 << (index - 1);
return (number & constant) != 0;
}
/**
* Prints an ascii representation of the tree.
*
* @param root
*
The current node to print
* @param depth
*
The level of the tree in which the current node lies. Levels
*
are counted with the root starting at 0.
* @param isLeft
*
Whether the current node is a left child.
* @param parBits
*
A bitstring (integer) representing the parents in the path
*
above this node. Used to 'fill in the gaps' in the drawing.
* @param buffered
*
Whether this was called to specifically include additional
*
whitespace on the left
*/
public void printAscii(Node<E> root, int depth, boolean
isLeft,
int parBits, boolean buffered) {
if (root == null) {
return;
}
for (int i = 0; i < (depth - 1) * 3; i++) {
if (i % 3 == 1 && nthBitSet(parBits,
depth - (i / 3))) {
System.out.print("|");
} else {
System.out.print(" ");
}
}
if (isLeft && depth != 0 && !buffered)
{
System.out.print(" `- ");
} else if (depth != 0 && !buffered) {
System.out.print(" |- ");
}
if (buffered) {
for (int i = 0; i < depth * 3; i++) {
System.out.print(" ");
}
}
System.out.println(root.data);
boolean hasRight = root.right != null;
boolean hasLeft = root.left != null;
int newParBits = parBits << 1;
if (hasLeft) {
newParBits++;
}
printAscii(root.right, depth + 1, !hasLeft,
newParBits, false);
printAscii(root.left, depth + 1, true, --newParBits,
false);
}
/**
* Prints an ascii representation of the tree.
*/
public void printAscii() {
printAscii(root, 0, false, 0, false);
}
}
import java.util.ArrayList;
import java.util.Random;
public class TreeTester {
public static final int RANDOM_TEST_SIZE = 15;
/**
* Run tests.
*/
public static void main(String[] args) {
System.out.println("Integer test");
testInt();
System.out.println("----------");
System.out.println("Randomized Char test");
randomCharTest();
}
/**
* Test BinarySearchTree on a predetermined selection of
integers.
*/
public static void testInt() {
BinarySearchTree<Integer> tree = new
BinarySearchTree<Integer>();
int[] valArr = { 4, 8, 10, 2, 1, 7, 3, 5, 9, 6 };
for (int i : valArr) {
tree.insert(i);
}
System.out.println("Tree:");
tree.printAscii();
System.out.println("Testing insertion by in-order
traversal");
tree.printInorder();
System.out.print("Depth of 6: ");
System.out.println(tree.getDepth(6));
System.out.print("Getting depth of 14: ");
System.out.println(tree.getDepth(14));
}
/**
* Test BinarySearchTree on a random selection of characters.
*/
public static void randomCharTest() {
BinarySearchTree<Character> tree = new
BinarySearchTree<Character>();
// Create the list of chars
ArrayList<Character> alphabet = new
ArrayList<Character>();
for (int i = 97; i < 123; i++) {
alphabet.add((char) i);
}
Random rand = new Random();
ArrayList<Character> inTree = new
ArrayList<Character>();
for (int i = 0; i < RANDOM_TEST_SIZE; i++) {
int removeIndex =
rand.nextInt(alphabet.size());
Character charToAdd =
alphabet.remove(removeIndex);
tree.insert(charToAdd);
inTree.add(charToAdd);
}
tree.printAscii();
System.out.println("Testing insertion by in-order
traversal");
tree.printInorder();
// Test the depth of two elements in the tree
System.out.println("Finding depth of random elements
within the tree:");
for (int i = 0; i < 2; i++) {
int randIndex =
rand.nextInt(inTree.size());
System.out.print("Depth of " +
inTree.get(randIndex) + ": ");
System.out.println(tree.getDepth(inTree.get(randIndex)));
}
ArrayList<Character> outOfTree = alphabet;
System.out
.println("Finding depth of random elements
outside the tree:");
int randIndex = rand.nextInt(outOfTree.size());
System.out.print("Depth of " + outOfTree.get(randIndex)
+ ": ");
System.out.println(tree.getDepth(outOfTree.get(randIndex)));
}
}
Output:
Preliminaries Download the template class and the driver file. Objective Learn how to traverse a binary...
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
Hello, I've been working on this for a while and I can't figure the rest out. Need asap if anyone can help. maxBSt,minBST,isBST, and inOrder package lab7; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; public class TreeExercise { /* * Construct BST from preorder traversal */ public static Node<Integer> consBSTfromPreOrder(int[] arr, int start, int end) { if(start > end) return null; Node<Integer> root = new Node<Integer>(arr[start],...
public class Buildbst { private int data; private Buildbst left; private Buildbst right; //Set the binary search tree public Buildbst(int data) { this.data = data; this.left = null; this.right =null; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Buildbst getLeft() { return left; } public void setLeft(Buildbst left) { this.left = left; } public Buildbst getRight() { return right; } public void setRight(Buildbst right) { this.right = right; } }...
In Java. How would this method look? LinkedBinaryTree.java import java.util.Iterator; public class LinkedBinaryTree implements BinaryTreeADT { private BinaryTreeNode root; /** * Creates an empty binary tree. */ public LinkedBinaryTree() { root = null; } /** * Creates a binary tree from an existing root. */ public LinkedBinaryTree(BinaryTreeNode root) { this.root = root; } /** * Creates a binary tree with the specified element...
write a new test program called RemoveDuplicates.java. The program reads text input from keyboard or a text file and adds the words to a BST. The program then traverses the BST and prints out the words in order (based on ASCII/UNICODE order) on the screen (or to output text file). Note that you may need to make some changes to BST.java. Sample test: ----jGRASP exec: java -ea removeDuplicates Original Text: a B 2 n w C q K l 0...
BST JAVA FILE import java.util.*; public class BST <E extends Comparable <E>> { private TreeNode<E> overallRoot; public BST() { overallRoot = null; } // ************ ADD ************ // public void add(E addThis) { if (overallRoot == null) { overallRoot = new TreeNode<>(addThis); } else { add(overallRoot, addThis); } } private TreeNode<E> add(TreeNode<E> node, E addThis) { if...
Since we do not want to have to rewrite this code when the element type changes, this classes uses a Comparator to assist in ordering the elements. You will need to complete the siftUpComparator() and siftDownComparator() methods in the LinkedHeap Class. siftUp §Added element may violate heap-order property §siftUp() restores order starting at added node §Processing will continue working up the tree until: úFinds properly ordered node & parent úReaches the root (reaches node without parent) siftDown §Restores heap’s order...
I have a Graph.java which I need to complete four methods in the java file: completeGraph(), valence(int vid), DFS(int start), and findPathBFS(int start, int end). I also have a JUnit test file GraphTest.java for you to check your code. Here is Graph.java: import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /* Generic vertex class */ class Vertex<T> { public T data; public boolean visited; public Vertex() { data = null; visited = false; } public Vertex(T _data) { data =...
Using the following implementation of Tree class Node { public int iData; // data item (key) public double dData; // data item public Node leftChild; // this node's left child public Node rightChild; // this node's right child public void displayNode() // display ourself { System.out.print('{'); System.out.print(iData); System.out.print(", "); System.out.print(dData); System.out.print("} "); } } // end class Node //------------------------------------------------------------------ import java.io.IOException; import java.util.Stack; public class Tree { private Node root; // first node of tree // ------------------------------------------------------------- public Tree() // constructor { root = null; }...
Java help! Please help complete the min method below in bold. import java.util.Arrays; import java.util.ArrayList; import java.util.Collections; import java.util.Iterator; import java.util.List; /** * Provides an implementation of a binary search tree * with no balance constraints, implemented with linked nodes. * * * */ public class Bst<T extends Comparable<T>> implements Iterable<T> { ////////////////////////////////////////////////////////////////// // I M P L E M E N T T H E M I N M E T H O D B E L O W...