public class BinarySearchTree { BinaryNode root; public void insert(int k){ if (
ID: 654967 • Letter: P
Question
public class BinarySearchTree {
BinaryNode root;
public void insert(int k){
if (root==null)
root = new BinaryNode(k);
else
insert(k, root);
}
private void insert(int k, BinaryNode node){
if (k>=node.value)
if (node.right!=null) //keep looking for a spot on the right branch
insert(k, node.right);
else { //we found an empty spot to put it
BinaryNode aux = new BinaryNode(k);
node.right = aux;
}
else
if (node.left!=null) // keep looking for a spot on the left branch
insert(k, node.left);
else {
BinaryNode aux = new BinaryNode(k);
node.left = aux;
}
}
public boolean search(int k){
return search(k, root);
}
private boolean search(int k, BinaryNode node){
if (node==null) return false;
if (node.value==k) return true;
if (node.value<k) return search(k, node.right);
else return search(k,node.left);
}
public void printTree(){
printTree(root, 0);
}
private void printTree(BinaryNode node, int level){
if (node==null) return;
printTree(node.left , level + 1 );
for ( int i=0 ; i < level ; i++ )
System.out.print(" ");
System.out.println(node.value);
printTree(node.right , level + 1 );
}
public int countNodes(){
return countNodes(root);
}
private int countNodes(BinaryNode node){
if (node==null) return 0;
return 1 + countNodes(node.left) +countNodes(node.right);
}
public int sum(){
return sum(root);
}
private int sum(BinaryNode node){
if (node==null) return 0;
return node.value + sum(node.left) + sum(node.right);
}
public int average(){
return average(root);
}
private int average(BinaryNode node){
return (node.value
+ countNodes(node.left)*average(node.left)
+ countNodes(node.right)*average(node.right))
/ countNodes(node);
}
public static void main(String[] args){
BinarySearchTree tree = new BinarySearchTree();
/*
tree.insert(4);
tree.insert(6);
tree.insert(2);
tree.insert(3);
tree.insert(1);
tree.insert(5);
tree.insert(7);
*/
for(int i=0; i<10; i++){
int aux = (int) (Math.random()*99)+1;
System.out.println("inserting " + aux);
tree.insert(aux);
}
System.out.println(tree.countNodes() + " nodes in the tree.");
tree.printTree();
for(int i=0; i<10; i++){
int aux = (int) (Math.random()*99)+1;
System.out.print("searching for " + aux + ": ");
System.out.println(tree.search(aux));
}
}
}
Write the intTree demo program.
tree.min() would return -2 and tree.max() would return 94. If the tree is empty, the methods throw an IllegalStateException.
Here is the code for min using method override to complete the functionality. The max would be written in the same fashion, but with 'max' in place of 'min' everywhere in the code.
Your Task
Rewrite the min and max methods so that they work with a Binary Search Tree. Add these methods to the code BinarySearchTree The methods should take advantage of the fact that the tree is sorted and should not examine nodes unless necessary.
Explanation / Answer
find Min for binarysearchtree
BinaryNode *findMin(BinaryNode *t)const //t is the smallest item in subtree
{
if(t==NULL)
return NULL;
if(t->left==NULL)
return t;
return find(t->left);
}
find Max for BinarySearchtrees
Binary node *findMax(BinaryNode *t) const // t is largest item of subtee
{
if(t!=NULL)
while(t->righy !=NULL)
t=t->right;
retun t;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.