Create an add method in JAVA for a Ternary Search Tree in the format: public voi
ID: 3830854 • Letter: C
Question
Create an add method in JAVA for a Ternary Search Tree in the format:
public void add(String s){
}
with a node of format:
public class TernaryTreeNode {
TernaryTreeNode left;
TernaryTreeNode right;
TernaryTreeNode center;
char splitChar;
public TernaryTreeNode(char c)
{
left=null;
center=null;
right=null;
splitChar=c;
}
SUCH THAT IT PASSES A TEST OF FORMAT:
String [] stringList = {"cute", "he", "cup", "at", "as", "us", "i"};
TernarySearchTree tst = new TernarySearchTree();
for (String s : stringList) {
tst.add(s);
System.out.println(tst+"-------");
}
Explanation / Answer
import java.util.scanner;
import java.util.arraylist;
class TSTnode
{
char data;
boolean isend;
TSTnode left ,center,right;
public TSTnode( char data)
{
this.data=data;
this.isend=false;
this.left=null;
this.center=null;
this.right=null;
}
}
class ternarysearchtree
{
private TSTnode root;
private arraylist<string>a1;
public ternarysearchtree()
{
root=null;
}
public boolean isempty()
{
return root==null;
}
public void makeempty()
{
root=null;
}
public void insert(string word)
{
root=insert(root,word.tochararay(),0);
}
public TSTnode insert (TSTnode r ,char[] word,int ptr)
{
if(r==null)
r=new TSTnode (word[ptr]);
if(word[ptr]<r.data)
r.left=insert(r.left,word,ptr);
else if (word[ptr]>r.data)
r.right=insert(r.right,word,ptr);
else
{
if(ptr+1<word.length)
r.center=insert (r.center,word,ptr+1);
else
r.isend=true;
}
return r;
}
public void delete(string word)
{
delete(root,word.tochararray(),0);
}
private void delete(TSTnode r, char[], word,int ptr)
{
if(r==null)
return;
if(word[ptr]<r.data)
delete(r.left,word,ptr);
else if (word[ptr]>r.data)
delete(r.right,word,ptr);
else
{
if(r.isend && ptr==word.length-1)
r.isend=false;
else if (ptr+1<word.length)
delete(r.middle,word,ptr+1);
}
}
public boolean search (string word)
{
return search (root,word.tochararray(),0);
}
private boolean search (TSTnode r ,char[] word,int ptr)
{
if(r==null)
return false;
if(word[ptr]<r.data)
return search (r.left,word,ptr);
else if (word[ptr]>r.data)
return search (r.right,word,ptr);
else
{
if(r.isend&&ptr==word.length-1)
return true;
else if (ptr==word.length-1)
return false;
else
return search (r.middle,word,ptr+1)
}
}
public string tostring()
{
a1=new arraylist<string>();
traverse(root," ");
return "ternery search tree:"+a1;
}
private void traverse(TSTnode r,string str)
{
if(r!=null)
{
traverse(r.left,str);
str=str+r.data;
if(r.isend);
a1.add(str);
traverse(r.center,str);
str=str.substring (0,str.length()-1);
traverse(r.right,str);
}
}
}
public class ternarysearchtreetest
{
public static void main( string [] args)
{
scanner scan =new scanner (system..in);
ternarysearchtree tst=new ternarysearchtree();
system.out.println("ternary search tree test");
char ch;
do
{
system.out.println("ternary search tree operation ");
system.out.println("1.insert word ");
system.out.println("2.search word ");
system.out.println("3.delete word ");
system.out.println("4.check word ");
system.out.println("5.make word ");
int choice=scan .nextint();
switch(choice)
{
case 1:system.out.println("enter word to insert ");
tst.insert(scan.next());
break;
case 2:
system.out.println("enter word to search ");
system.out.println("search result :"+tst.search (scan.next()));
break;
case 3:
system.out.println("enter word to delete ");
test.delete(scan.next());
break;
case 4:
system.out.println("empty status:"+tst.empty());
break;
case 5:system.out.println("ternary search tree cleared");
tst.makeempty();
break;
default:
system.out.println('wrong entry ")
break;
}
system.out.println(tst);
system.out.println(" do you wnat to continue (type y or n) );
ch=scan.next().chatat(0);
}
while(=='y' ||ch=='Y');
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.