/ Binary search tree node class Node { private int info; //element stored in thi
ID: 3587841 • Letter: #
Question
/ 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();
}
}
Add a recursive function getHeight to the BinarySearchTree class in Exercise 1 that returns the height of the tree. Create a Main class to test it. Continue to display list of values added to tree and the sorted list resulting from display(), as in Exercise 1, followed by a print-out of the tree height. Repeat for several trees of different numbers of nodes.
PLEASE INCLUDE OUTPUT SCREENSHOT
Explanation / Answer
Tested on Eclipse
/******************************BinarySearchTree.java*********************/
/**
* The Class BinarySearchTree.
*/
public class BinarySearchTree {
/** The root. */
private Node root; // root of the bst. It's implemented as a dummy node.
/**
* Instantiates a new binary search tree.
*/
// 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);
}
/**
* Checks if is empty.
*
* @return true, if is empty
*/
// Determines whether the bst is empty
public boolean isEmpty() {
return root.getLeftChild() == null;
}
// Prints the bst elements using inorder traversal
/**
* Display.
*/
// 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
/**
* Contains.
*
* @param x the x
* @return true, if successful
*/
// 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
/**
* Adds the.
*
* @param x the x
*/
// 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
/**
* Gets the min.
*
* @return the min
*/
// 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 display.
*
* @param p the p
*/
// 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
/**
* Search.
*
* @param x the x
* @param p the p
* @return true, if successful
*/
// 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
/**
* Insert.
*
* @param x the x
* @param p the p
*/
// 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
/**
* Gets the min.
*
* @param p the p
* @return the min
*/
// the leftmost node.
private int getMin(Node p) {
if (p.getLeftChild() == null)
return p.getInfo();
else
return getMin(p.getLeftChild());
}
/**
* Gets the height.
*
* @return the height
*/
public int getHeight() {
int height = getHeightRecursive(root);
return height;
}
/**
* Gets the height recursive.
*
* @param node the node
* @return the height recursive
*/
private int getHeightRecursive(Node node) {
if (node == null)
return 0;
else {
/* compute the depth of each subtree */
int lDepth = getHeightRecursive(node.getLeftChild());
int rDepth = getHeightRecursive(node.getRightChild());
/* use the larger one */
if (lDepth > rDepth)
return lDepth + 1;
else
return rDepth + 1;
}
}
}
/***************************************Node.java************************/
/**
* The Class Node.
*/
public class Node {
/** The info. */
private int info; // element stored in this node
/** The left. */
private Node left; // link to left child
/** The right. */
private Node right; // link to right child
// Initializes the node
/**
* Instantiates a new node.
*/
Node() {
info = 0;
left = right = null;
}
/**
* Sets the node.
*
* @param x the x
* @param l the l
* @param r the r
*/
// Sets this node
void setNode(int x, Node l, Node r) {
info = x;
left = l;
right = r;
}
/**
* Gets the info.
*
* @return the info
*/
// Returns the value in this node
int getInfo() {
return info;
}
/**
* Gets the left child.
*
* @return the left child
*/
// Returns the link to the left child
Node getLeftChild() {
return left;
}
/**
* Gets the right child.
*
* @return the right child
*/
// Returns the link to the right child
Node getRightChild() {
return right;
}
/**
* Sets the info.
*
* @param x the new info
*/
// Sets the value for this node
void setInfo(int x) {
info = x;
}
/**
* Sets the left child.
*
* @param l the new left child
*/
// Sets the link to the left child
void setLeftChild(Node l) {
left = l;
}
/**
* Sets the right child.
*
* @param r the new right child
*/
// Sets the link to the right child
void setRightChild(Node r) {
right = r;
}
}
/*************************************Lab6A.java******************************************/
/**
* The Class Lab6A.
*/
public class Lab6A {
/**
* The main method.
*
* @param args the arguments
*/
public static void main(String[] args) {
// randomly added node to bst tree
// we are generating random value 10 times
for (int j = 0; j < 10; j++) {
System.out.println("**************************************");
BinarySearchTree bst = new BinarySearchTree();
System.out.println("Inserting element into BST");
for (int i = 0; i < 10; i++) {
int x = (int) (Math.random() * 100);
System.out.print(x + " ");
bst.add(x);
}
System.out.println();
System.out.println("Printing Element in to sorted order");
bst.display();
System.out.println("Height of tree: " + bst.getHeight());
}
}
}
/****************************output******************************/
**************************************
Inserting element into BST
25 14 52 39 37 75 55 43 55 79
Printing Element in to sorted order
14 25 37 39 43 52 55 55 75 79
Height of tree: 6
**************************************
Inserting element into BST
6 91 2 27 30 56 32 61 37 83
Printing Element in to sorted order
2 6 27 30 32 37 56 61 83 91
Height of tree: 8
**************************************
Inserting element into BST
97 30 74 41 4 61 56 90 81 5
Printing Element in to sorted order
4 5 30 41 56 61 74 81 90 97
Height of tree: 7
**************************************
Inserting element into BST
78 63 61 83 62 38 24 4 88 88
Printing Element in to sorted order
4 24 38 61 62 63 78 83 88 88
Height of tree: 7
**************************************
Inserting element into BST
73 15 27 8 39 82 67 63 54 2
Printing Element in to sorted order
2 8 15 27 39 54 63 67 73 82
Height of tree: 8
**************************************
Inserting element into BST
46 39 65 79 25 96 9 10 41 87
Printing Element in to sorted order
9 10 25 39 41 46 65 79 87 96
Height of tree: 6
**************************************
Inserting element into BST
82 95 16 30 56 47 84 70 32 89
Printing Element in to sorted order
16 30 32 47 56 70 82 84 89 95
Height of tree: 7
**************************************
Inserting element into BST
92 34 19 8 80 11 1 13 55 48
Printing Element in to sorted order
1 8 11 13 19 34 48 55 80 92
Height of tree: 7
**************************************
Inserting element into BST
44 57 28 48 80 70 37 48 84 48
Printing Element in to sorted order
28 37 44 48 48 48 57 70 80 84
Height of tree: 6
**************************************
Inserting element into BST
51 93 93 67 26 42 41 65 53 33
Printing Element in to sorted order
26 33 41 42 51 53 65 67 93 93
Height of tree: 6
Thanks a lot. Please let me know if you have any doubt.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.