Java Launguge Design and implement the binary search tree that is suitable for t
ID: 3714316 • Letter: J
Question
Java Launguge
Design and implement the binary search tree that is suitable for the following problem. A social networking website stores information about its users in a binary search tree. In addition to the components that provide access to the left and right branches of the tree, each node in the tree contains a unique user number (the key value), the user's name, and a list of the names of each of the user's friends.
1- Design and implement a method friend-count which takes a user number and returns the number of friends that the person with the given user number has. You may assume the user number exists in the tree. Your function should be written efficiently, such that it performs as few comparisons in the tree as is necessary.
2- Design and implement a method friend-everyone which takes the name of a person and returns a new binary search tree such that the named person has been added to each user's friend list.
3- Design and implement a method list-names-in-order which takes a binary search tree and produces a list of the names of users in the tree, such that the list of names is in ascending numeric order by user number. (Hint: you don't have to write a sorting algorithm. Use what you know about the order of items in a binary search tree to help you.)
4- Design and implement a method add-new-user which takes a user number, and a user name, and adds a new user with the given information to the binary search tree. The user's list of friends should be empty. Make sure that the tree that is produced is a binary search tree. You may assume that the user number does not already exist in the given tree.
5- Design and implement a method delete-user which takes a user number, and deletes this user from the binary search tree. Make sure that the tree that is produced is a binary search tree. You may assume that the user number exists in the given tree.
6-Design and implement the main method to test your program. Tis method should presents the user with a menu of suitable choices to use your program.
Explanation / Answer
import java.util.Scanner;
class SampleBst
{
SampleBst l, r;
int d;
public SampleBst()
{
l = null;
r = null;
d = 0;
}
public SampleBst(int n)
{
l = null;
r = null;
d = n;
}
public void setLS(SampleBst n)
{
l = n;
}
public void setRS(SampleBst n)
{
r = n;
}
public SampleBst getLS()
{
return l;
}
public SampleBst getRS()
{
return r;
}
public void setNum(int d)
{
d = d;
}
public int getNum()
{
return d;
}
}
class SampleTree
{
private SampleBst rt;
public SampleTree()
{
rt = null;
}
public void addNewUser(int d)
{
rt = addNewUser(rt, d);
}
private SampleBst addNewUser(SampleBst node, int d)
{
if (node == null)
node = new SampleBst(d);
else
{
if (d <= node.getNum())
node.l = addNewUser(node.l, d);
else
node.r = addNewUser(node.r, d);
}
return node;
}
public int friendCount()
{
return friendCount(rt);
}
private int friendCount(SampleBst nr)
{
if (nr == null)
return 0;
else
{
int l = 1;
l += friendCount(nr.getLS());
l += friendCount(nr.getRS());
return l;
}
}
public void displayNumber()
{
displayNumber(rt);
}
private void displayNumber(SampleBst nr)
{
if (nr != null)
{
System.out.print(nr.getNum() +" ");
displayNumber(nr.getLS());
displayNumber(nr.getRS());
}
}
}
public class BSTExample
{
public static void main(String[] args)
{
Scanner s = new Scanner(System.in);
SampleTree newbst = new SampleTree();
System.out.println(" Binary Search Tree ");
char opt;
do
{
System.out.println("1. addNewUser ");
System.out.println("2. friendCount");
System.out.println("Enter your option: ");
int c = s.nextInt();
switch (c)
{
case 1 :
System.out.println("Enter NewUser number: ");
newbst.addNewUser(s.nextInt() );
break;
case 2 :
System.out.println("Count= "+ newbst.friendCount());
break;
}
System.out.print(" Display number: ");
newbst.displayNumber();
System.out.println(" Enter Y to continue or n to exit: ");
opt = s.next().charAt(0);
} while (opt == 'Y'|| opt == 'y');
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.