You will see the program is set up as a single Java file including 3 classes, No
ID: 3547698 • Letter: Y
Question
You will see the program is set up as a single Java file including 3 classes, Node, BinarySearchTree and a public Lab6A with the main method. Leave it as one file!
// Binary search tree node
class Node {
private int info; //element stored in this node
private Node left; //link to left child
private Node right; //link to right child
// Initializes the node
Node() {
info = 0;
left = right = null;
}
// Sets this node
void setNode(int x, Node l, Node r) {
info = x;
left = l;
right = r;
}
// Returns the value in this node
int getInfo() {
return info;
}
// Returns the link to the left child
Node getLeftChild() {
return left;
}
// Returns the link to the right child
Node getRightChild() {
return right;
}
// Sets the value for this node
void setInfo(int x) {
info = x;
}
// Sets the link to the left child
void setLeftChild(Node l) {
left = l;
}
// Sets the link to the right child
void setRightChild(Node r) {
right = r;
}
}
///////////////////////////////////////////////////////////////////////////////
// Class implementing a binary search tree
class BinarySearchTree {
private Node root; //root of the bst. It's implemented as a dummy node.
// Initializes the bst to empty creating a dummy root node
public BinarySearchTree() {
root = new Node(); //dummy node as the root
root.setLeftChild(null);
root.setRightChild(null);
root.setInfo(-1);
}
// Determines whether the bst is empty
public boolean isEmpty() {
return root.getLeftChild() == null;
}
// Prints the bst elements using inorder traversal
// This method invokes the private inorderDisplay mehod
public void display() {
inorderDisplay(root.getLeftChild());
System.out.println();
}
// Determines if an item exists in the bst. This method invokes the private
// method search, passing to it the element to be found and the root
// of the actual tree.
public boolean contains(int x) {
return search(x, root.getLeftChild());
}
// Adds the element x to the bst. This method invokes the private method
// insert, passing to it the element to be added to the bst and the root
// of the actual tree.
public void add(int x) {
if (root.getLeftChild() == null) {
Node p = new Node();
p.setNode(x, null, null);
root.setLeftChild(p);
} else
insert(x, root.getLeftChild());
}
// Finds the smallest element in the bst. This method invokes the overloaded
// method getMin, passing to it the root of the tree.
public int getMin() {
return getMin(root);
}
////////////////// Private methods ////////////////////////////////////////
// Prints the elements of the subtree whose root is referenced by p. Uses
// inorder traversal.
private void inorderDisplay(Node p) {
if (p != null) {
inorderDisplay(p.getLeftChild());
System.out.print(p.getInfo() + " ");
inorderDisplay(p.getRightChild());
}
}
// Finds if x is inserted in the subtree whose root is referenced by p. The
// search is conducted recursively, using the bst property: keys in the left
// subtree of a node are smaller than or equal to the key in the node, while
// the keys in the right subtree of the node are greater.
private boolean search(int x, Node p) {
if (p == null)
return false;
else if (x == p.getInfo())
return true;
else if (x < p.getInfo())
return search(x, p.getLeftChild());
else
return search(x, p.getRightChild());
}
// Adds x to the subtree referenced by p. The search for the location to
// insert the new node is conducted recursively, using the bst property:
// keys in the left subtree of a node are smaller than or equal to the key
// in the node, while the keys in the right subtree of the node are greater.
private void insert(int x, Node p) {
if (x < p.getInfo())
if (p.getLeftChild() == null) {
Node q = new Node();
q.setNode(x, null, null);
p.setLeftChild(q);
}
else
insert(x, p.getLeftChild());
else if (p.getRightChild() == null) {
Node q = new Node();
q.setNode(x, null, null);
p.setRightChild(q);
}
else
insert(x, p.getRightChild());
}
// Recursively finds the smallest element in the subtree referenced by p.
// The method uses this property of BSTs: the smallest value is stored in
// the leftmost node.
private int getMin(Node p) {
if (p.getLeftChild() == null)
return p.getInfo();
else
return getMin(p.getLeftChild());
}
}
///////////////////////////////////////////////////////////////////////////////
// Class testing the binary search tree.
public class Lab6A {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
for (int i = 0; i < 10; i++) {
int x = (int) (Math.random() * 100);
System.out.print(x + " ");
bst.add(x);
}
System.out.println();
bst.display();
}
}
Explanation / Answer
please rate
// modified code given in red
class Node {
private int info; // element stored in this node
private Node left; // link to left child
private Node right; // link to right child
// Initializes the node
Node() {
info = 0;
left = right = null;
}
// Sets this node
void setNode(int x, Node l, Node r) {
info = x;
left = l;
right = r;
}
// Returns the value in this node
int getInfo() {
return info;
}
// Returns the link to the left child
Node getLeftChild() {
return left;
}
// Returns the link to the right child
Node getRightChild() {
return right;
}
// Sets the value for this node
void setInfo(int x) {
info = x;
}
// Sets the link to the left child
void setLeftChild(Node l) {
left = l;
}
// Sets the link to the right child
void setRightChild(Node r) {
right = r;
}
}
// /////////////////////////////////////////////////////////////////////////////
// Class implementing a binary search tree
class BinarySearchTree {
private Node root; // root of the bst. It's implemented as a dummy node.
private String inOrderString = "";
// Initializes the bst to empty creating a dummy root node
public BinarySearchTree() {
root = new Node(); // dummy node as the root
root.setLeftChild(null);
root.setRightChild(null);
root.setInfo(-1);
}
// Determines whether the bst is empty
public boolean isEmpty() {
return root.getLeftChild() == null;
}
// Prints the bst elements using inorder traversal
// This method invokes the private inorderDisplay mehod
public void display() {
inorderDisplay(root.getLeftChild());
System.out.println();
}
private int nodeCountHelper(Node p,int count){
if (p != null) {
count = nodeCountHelper(p.getLeftChild(),count);
count ++;
count = nodeCountHelper(p.getRightChild(),count);
}
return count;
}
public int nodeCount(){
return nodeCountHelper(root.getLeftChild(), 0);
}
private void inOrderToString(Node p){
if (p != null) {
inOrderToString(p.getLeftChild());
inOrderString += p.getInfo() + " ";
inOrderToString(p.getRightChild());
}
}
public String toString(){
inOrderString = "";
inOrderToString(root.getLeftChild());
return inOrderString;
}
// Determines if an item exists in the bst. This method invokes the private
// method search, passing to it the element to be found and the root
// of the actual tree.
public boolean contains(int x) {
return search(x, root.getLeftChild());
}
// Adds the element x to the bst. This method invokes the private method
// insert, passing to it the element to be added to the bst and the root
// of the actual tree.
public void add(int x) {
if (root.getLeftChild() == null) {
Node p = new Node();
p.setNode(x, null, null);
root.setLeftChild(p);
} else
insert(x, root.getLeftChild());
}
// Finds the smallest element in the bst. This method invokes the overloaded
// method getMin, passing to it the root of the tree.
public int getMin() {
return getMin(root);
}
public int getMax(){
return getMax(root.getLeftChild());
}
// //////////////// Private methods ////////////////////////////////////////
// Prints the elements of the subtree whose root is referenced by p. Uses
// inorder traversal.
private void inorderDisplay(Node p) {
if (p != null) {
inorderDisplay(p.getLeftChild());
System.out.print(p.getInfo() + " ");
inorderDisplay(p.getRightChild());
}
}
// Finds if x is inserted in the subtree whose root is referenced by p. The
// search is conducted recursively, using the bst property: keys in the left
// subtree of a node are smaller than or equal to the key in the node, while
// the keys in the right subtree of the node are greater.
private boolean search(int x, Node p) {
if (p == null)
return false;
else if (x == p.getInfo())
return true;
else if (x < p.getInfo())
return search(x, p.getLeftChild());
else
return search(x, p.getRightChild());
}
// Adds x to the subtree referenced by p. The search for the location to
// insert the new node is conducted recursively, using the bst property:
// keys in the left subtree of a node are smaller than or equal to the key
// in the node, while the keys in the right subtree of the node are greater.
private void insert(int x, Node p) {
if (x < p.getInfo())
if (p.getLeftChild() == null) {
Node q = new Node();
q.setNode(x, null, null);
p.setLeftChild(q);
}
else
insert(x, p.getLeftChild());
else if (p.getRightChild() == null) {
Node q = new Node();
q.setNode(x, null, null);
p.setRightChild(q);
}
else
insert(x, p.getRightChild());
}
// Recursively finds the smallest element in the subtree referenced by p.
// The method uses this property of BSTs: the smallest value is stored in
// the leftmost node.
private int getMin(Node p) {
if (p.getLeftChild() == null)
return p.getInfo();
else
return getMin(p.getLeftChild());
}
private int getMax(Node p) {
if(p.getRightChild()==null){
return p.getInfo();
}else{
return getMax(p.getRightChild());
}
}
}
// /////////////////////////////////////////////////////////////////////////////
// Class testing the binary search tree.
public class Lab6A {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
for (int i = 0; i < 10; i++) {
int x = (int) (Math.random() * 100);
System.out.print(x + " ");
bst.add(x);
}
System.out.println();
bst.display();
System.out.println("Max node: "+bst.getMax());
System.out.println("BST to string function: "+bst);
System.out.println("Node count: "+bst.nodeCount());
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.