I found this exact question asked elsewhere but the answer isn\'t helpful to me.

Question

I found this exact question asked elsewhere but the answer isn't helpful to me.

Use a binary search tree to implement a dictionary that contains the keywords in the Java language. Test it. Note that you can use the programs from the previous exercises. For a list of the keywords in Java, visit http://docs.oracle.com/javase/tutorial/java/nutsandbolts/_keywords.html.

I am planning on manually adding all keywords through the bst.add("string name"). I have tried altering the BinarySearchTree.java class to allow String data types but this isn't going well. I'm not proficient enough at importing files with delimeters to use a .txt file to import the dictionary. I am looking for explanations and hints so that I can understand this more, not just a textbook answer. Thank you.

Main.java

//Week 7 - lecture: driver program (bst)

public class Main
{
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();
}
}

Node.java

//Week 7 - lecture: Node class

class Node
{
Node()
{
info = 0;
left = right = null;
}

void setNode(int x, Node l, Node r)
{
info = x;
left = l;
right = r;
}

int getInfo()
{
return info;
}

Node getLeftChild()
{
return left;
}

Node getRightChild()
{
return right;
}

void setInfo(int x)
{
info = x;
}

void setLeftChild(Node l)
{
left = l;
}

void setRightChild(Node r)
{
right = r;
}

private int info;
private Node left;
private Node right;
}

BinarySearchTree.java

//Week 7 - lecture: BST class

public class BinarySearchTree
{
public BinarySearchTree()
{
root = new Node(); //dummy node as the root
root.setLeftChild(null);
root.setRightChild(null);
root.setInfo(-1);
}

public boolean isEmpty()
{
return root.getLeftChild()==null;
}

public void display()
{
inorderDisplay(root.getLeftChild());
System.out.println();
}

public boolean contains(int x)
{
return search(x, root.getLeftChild());
}

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());
}

public int getMin()
{
return getMin(root);
}

private Node root;

private void inorderDisplay(Node p)
{
if (p != null)
{
inorderDisplay(p.getLeftChild());
System.out.print(p.getInfo() + " ");
inorderDisplay(p.getRightChild());
}
}

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());
}


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());
}

private int getMin(Node p)
{
if (p.getLeftChild() == null) return p.getInfo();
else return getMin(p.getLeftChild());
}
}

Explanation / Answer

1) Generally, Dictionary works faster for adding items (tested on 50000 items): DateTime StartTime = new DateTime(); DateTime EndTime = new DateTime(); StartTime = DateTime.Now; for (int i = 1; i < 50000; i++) { dict.Add(i, i); } EndTime = DateTime.Now; long Time; Time = EndTime.Ticks - StartTime.Ticks; this.Text = Time.ToString; The result was: 400576 ticks. 2) Compared to SortedDictionary with the same code (changed Dictionary to SortedDictionary): The result was: 1201728 ticks. 3) Speaking about getting items from Dictionary: DateTime GetStart = new DateTime(); DateTime GetEnd = new DateTime(); GetStart = DateTime.Now; foreach (int a in dict.Keys) { listBox1.Items.Add(dict[a]); } GetStop = DateTime.Now; long Result; Result = GetStop.Ticks - GetStart.Ticks; this.Text = Result.ToString(); The result was: 717531760 ticks. 4) Compared to SortedDictionary with the same code (changed Dictionary to SortedDictionary): The result was: 704412896 ticks.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.