My program is supposed to take in a text file of words, put the words on a binary search tree then print out the words in alphabetical order with their line number... can anyone help me with my errors?

/* Amanda Sgroi
   Program #9
   Due: November 16, 2006
   This program is designed to take in a text file of words then output the words in alphabetical order along with the corresponding
   line in which the word occured.*/
 
 
import java.io.*;
 
import java.util.Scanner;
 
import java.util.LinkedList;
 
/************************  BST.java  **************************
 *                 generic binary search tree
 */
 
class BST<T> {
 
    protected BSTNode root = null;
 
    public BST() {
    }
 
    public void clear() {
        root = null;
    }
 
    public boolean isEmpty() {
        return root == null;
    }
 
    public void insert(Comparable el) {
        BSTNode<T> p = root, prev = null;
        while (p != null) {  // find a place for inserting new node;
            prev = p;
            if (p.el.compareTo(el) < 0)
                 p = p.right;
            else p = p.left;
        }
        if (root == null)    // tree is empty;
             root = new BSTNode<T>(el);
        else if (prev.el.compareTo(el) < 0)
             prev.right = new BSTNode<T>(el);
        else prev.left  = new BSTNode<T>(el);
    }
 
    public boolean isInTree(Comparable el) {
        return search(el) != null;
    }
 
    public Comparable search(Comparable el) {
        return search(root,el);
	}
 
    protected Comparable search(BSTNode<T> p, Comparable el) {
        while (p != null)
            if (el.equals(p.el))
                 return p.el;
            else if (el.compareTo(p.el) < 0)
                 p = p.left;
            else p = p.right;
        return null;
    }
 
    public void preorder() {
        preorder(root);
    }
 
    public void inorder() {
        inorder(root);
    }
 
    public void postorder() {
        postorder(root);
    }
 
    protected void visit(BSTNode<T> p) {
        System.out.print(p.el + " ");
    }
 
    protected void inorder(BSTNode<T> p) {
        if (p != null) {
             inorder(p.left);
             visit(p);
             inorder(p.right);
        }
    }
 
    protected void preorder(BSTNode<T> p) {
        if (p != null) {
             visit(p);
             preorder(p.left);
             preorder(p.right);
        }
    }
 
    protected void postorder(BSTNode<T> p) {
        if (p != null) {
             postorder(p.left);
             postorder(p.right);
             visit(p);
        }
	}
}
 
/************************  BSTNode.java  **************************
 *             node of a generic binary search tree
 */
 
class BSTNode<T> {
 
    protected Comparable el;
    protected BSTNode<T> left, right;
    protected BSTNode<T> root = null;
 
    public BSTNode() {
        left = right = null;
    }
 
    public BSTNode(Comparable el) {
        this(el,null,null);
    }
 
    public BSTNode(Comparable el, BSTNode lt, BSTNode rt) {
        this.el = el; left = lt; right = rt;
    }
 
}
 
class Tokens extends Word{
 
void readTokens2(String fInName) throws IOException{
	int linecounter = 1;
	BufferedReader fIn = new BufferedReader(new FileReader(fInName));
	String s;
	while((s = fIn.readLine()) != null){
		java.util.StringTokenizer line = new java.util.StringTokenizer(s);
		while(line.hasMoreTokens()){
			BST<Word> tree = new BST<Word>();
			tree.search(line.nextToken());
			if(!(tree.isInTree(line.nextToken()))){
				BSTNode<Word> node = new BSTNode<Word>();
				tree.insert(node);
			}
			else
				list.insertAtTail(linecounter);
			System.out.println(linecounter + " " + line.nextToken());
			tree.inorder();
			}
		}
	++linecounter;
	fIn.close();
	}
}
 
class Word implements Comparable{
 
 
	private String word = "";
	public int freq = 1;
	LinkedList<Integer> list = new LinkedList<Integer>();
 
	public Word(){
	}
 
	public Word(String s){
		word = s;
	}
 
	public boolean equals(Object el){
		return word.equals(((Word)el).word);
	}
 
	public int compareTo(Object el){
		return word.compareTo(((Word)el).word);
	}
 
	public String toString(){
		return word + ": " + freq + "";
	}
}
 
class BSTTest extends BST<Word>{
 
	public static void main(String[] args)throws IOException{
 
		Scanner kb = new Scanner(System.in);
		System.out.println("Please Enter Your File Name: ");
		String fInName  = kb.next();
		Tokens t = new Tokens();
		t.readTokens2(fInName);
	}
}

E:\BSTTest.java:144: insert(java.lang.Comparable) in BST<Word> cannot be applied to (BSTNode<Word>)
tree.insert(node);
^
E:\BSTTest.java:147: cannot find symbol
symbol : method insertAtTail(int)
location: class java.util.LinkedList<java.lang.Integer>
list.insertAtTail(linecounter);
^
Note: E:\BSTTest.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
2 errors

Tool completed with exit code 1

 

 

Hi,

1) Your BSTNode class needs to implement the Comparable interface (the insert() method needs Comparable as an argument )

2) LinkedList doesn't have insertAtTail() method, try addLast()

 

 

ok i understand number 2.. that was a stupid mistake

can you show me what you mean by number one because my insert method looks like this


public void insert(Comparable el)

 

 

Exactly. It expects a Comparable. But the argument you are giving to it (BSTNode) is not Comparable, because BSTNode doesn't implement the Comparable interface like for example your class Word does. Just implement Comparable in your BSTNode class.

 

 

E:\BSTTest.java:111: BSTNode is not abstract and does not override abstract method compareTo(java.lang.Object) in java.lang.Comparable
class BSTNode<T> implements Comparable {
^


no i got this

 

 

Of course, you have to implement the method of that interface, like you did in the Word class.

 

 

If you want to compare the 'el' member of the BSTNode class, the implementation should look like this:

    public int compareTo(Object o) {
    	return el.compareTo(((BSTNode<T>) o).el);
    }

 

 

i don't know what you mean/what to do in order to fix it

 

 

I think your BSTNode class should look like this:

class BSTNode<T> implements Comparable{
 
    protected Comparable el;
    protected BSTNode<T> left, right;
    protected BSTNode<T> root = null;
 
    public BSTNode() {
        left = right = null;
    }
 
    public BSTNode(Comparable el) {
        this(el,null,null);
    }
 
    public BSTNode(Comparable el, BSTNode lt, BSTNode rt) {
        this.el = el; left = lt; right = rt;
    }
 
    public int compareTo(Object o) {
    	return el.compareTo(((BSTNode<T>) o).el);
    }
}

 

 

thanks so much!!!!

 

 

You're welcome. However, it still won't work :)

Change the readTokens2 method as follows:

	void readTokens2(String fInName) throws IOException{
		int linecounter = 1;
		BufferedReader fIn = new BufferedReader(new FileReader(fInName));
		String s;
		String token; // a String for the token
		BST<Word> tree = new BST<Word>(); //you must use the same tree for all the words
		while((s = fIn.readLine()) != null){
			java.util.StringTokenizer line = new java.util.StringTokenizer(s);
			while(line.hasMoreTokens()){
				token = line.nextToken(); // nextToken() must only be called once per cycle
				tree.search(token);
				if(!(tree.isInTree(token))){
					BSTNode<Word> node = new BSTNode<Word>(token);
					tree.insert(node);
				}
				else
					list.addLast(linecounter);
				//System.out.println(linecounter + " " + token); //no need to print this
			}
			linecounter++; //increment after the line is over
		}
		tree.inorder(); // printing the tree after all words are in
		fIn.close();
	}

also, in BSTNode:

	//you have to provide a toString method in order to be able to use
	// System.out.print(p.el + " ") in BST.visit
	public String toString() {
		return el.toString();
	}

 

 

Ahh, it's still not working. There's a ClassCastException in BST.search method on the line

else if (el.compareTo(p.el) < 0)

I don't use generics, so I don't know exactly what's wrong.

 

 

Ok, here's a working code. It's quite ugly, though. Compare it with what you have to see the differences, then you should clean it up a bit :)

/* Amanda Sgroi
   Program #9
   Due: November 16, 2006
   This program is designed to take in a text file of words then output the words in alphabetical order along with the corresponding
   line in which the word occured.*/
 
 
import java.io.*;
 
import java.util.Scanner;
 
import java.util.LinkedList;
 
 
/************************  BST.java  **************************
 *                 generic binary search tree
 */
 
class BST<T> {
 
	protected BSTNode<T> root = null;
 
	public BST() {
	}
 
	public void clear() {
		root = null;
	}
 
	public boolean isEmpty() {
		return root == null;
	}
 
	public void insert(Comparable el) {
		BSTNode<T> p = root, prev = null;
		while (p != null) {  // find a place for inserting new node;
			prev = p;
			if (p.el.compareTo(el) < 0) {
				p = p.right;
			} else {
				p = p.left;
			}
		}
		if (root == null)    // tree is empty;
			root = new BSTNode<T>(el);
		else if (prev.el.compareTo(el) < 0)
			prev.right = new BSTNode<T>(el);
		else prev.left  = new BSTNode<T>(el);
	}
 
	public boolean isInTree(Comparable el) {
		return search(el) != null;
	}
 
	public Comparable search(Comparable el) {
		return search(root,el);
	}
 
	protected Comparable search(BSTNode<T> p, Comparable el) {
		while (p != null) {
			if (p.el.compareTo(new BSTNode<T>(el)) == 0)
				return p.el;
			else if (p.el.compareTo(new BSTNode<T>(el)) < 0)
				p = p.right;
			else p = p.left;
		}
		return null;
	}
 
	public void preorder() {
		preorder(root);
	}
 
	public void inorder() {
		inorder(root);
	}
 
	public void postorder() {
		postorder(root);
	}
 
	protected void visit(BSTNode<T> p) {
		System.out.println(p.el);
	}
 
	protected void inorder(BSTNode<T> p) {
		if (p != null) {
			inorder(p.left);
			visit(p);
			inorder(p.right);
		}
	}
 
	protected void preorder(BSTNode<T> p) {
		if (p != null) {
			visit(p);
			preorder(p.left);
			preorder(p.right);
		}
	}
 
	protected void postorder(BSTNode<T> p) {
		if (p != null) {
			postorder(p.left);
			postorder(p.right);
			visit(p);
		}
	}
}
 
/************************  BSTNode.java  **************************
 *             node of a generic binary search tree
 */
 
class BSTNode<T> implements Comparable{
 
	protected Comparable el;
	protected BSTNode<T> left, right;
	protected BSTNode<T> root = null;
 
	public BSTNode() {
		left = right = null;
	}
 
	public BSTNode(Comparable el) {
		this(el,null,null);
	}
 
	public BSTNode(Comparable el, BSTNode lt, BSTNode rt) {
		this.el = el; left = lt; right = rt;
	}
 
	public int compareTo(Object o) {
		return el.compareTo(((BSTNode<T>) o).el);
	}
 
	//you have to provide a toString method in order to be able to use
	// System.out.print(p.el + " ") in BST.visit
	public String toString() {
		return el.toString();
	}
}
 
class Tokens extends Word{
 
	void readTokens2(String fInName) throws IOException{
		int linecounter = 1;
		BufferedReader fIn = new BufferedReader(new FileReader(fInName));
		String s;
		BSTNode<Word> node;
		String token; // a String for the token
		BST<Word> tree = new BST<Word>(); //you must use the same tree for all the words
		while((s = fIn.readLine()) != null){
			java.util.StringTokenizer line = new java.util.StringTokenizer(s);
			while(line.hasMoreTokens()){
				token = line.nextToken(); // nextToken() must only be called once per cycle
				//tree.search(token);
				if(!(tree.isInTree(new Word(token)))){
					node = new BSTNode<Word>(new Word(token));
					tree.insert(node);
				} else {
					node = (BSTNode<Word>) tree.search(new Word(token));
				}
				((Word) (node.el)).list.addLast(linecounter);
				//System.out.println(linecounter + " " + token); //no need to print this
			}
			linecounter++;
		}
		tree.inorder(); // printing the tree after all words are in
		fIn.close();
	}
}
 
class Word implements Comparable{
 
 
	private String word = "";
	public int freq = 1;
	LinkedList<Integer> list = new LinkedList<Integer>();
 
	public Word(){
	}
 
	public Word(String s){
		word = s;
	}
 
	public boolean equals(Object el){
		return word.equals(((Word)el).word);
	}
 
	public int compareTo(Object el){
		return word.compareTo(((Word)el).word);
	}
 
	public String toString(){
		String result = word + "; lines: ";
		for (int i = 0; i < list.size(); i++) {
			result += list.get(i) + "; ";
		}
		return result;
	}
}
 
public class BSTTest extends BST<Word>{
 
	public static void main(String[] args)throws IOException{
 
		Scanner kb = new Scanner(System.in);
		System.out.println("Please Enter Your File Name: ");
		String fInName  = kb.next();
		Tokens t = new Tokens();
		t.readTokens2(fInName);
	}
}

 

 

Sorry I don't have enough time to write a detailed explanation.
I hope you try this code and learn from it.

/* save as BST2Test.java */
/* ignore compiler warnings for generics */
/*** test.txt ***************************************************
you are my love
my love is wine
you are my love
you are my love
my love is wine
you are my love
*****************************************************************/
import java.io.*;
import java.util.*;
 
class BST2<T> {
  protected BST2Node<T> root, nextLeft, nextRight;
 
  public BST2(){
    root = null;
  }
 
  public BST2(BST2Node<T> node){
    root = node;
  }
 
  public void clear() {
    root = null;
  }
 
  public boolean isEmpty() {
    return root == null;
  }
 
  public void insert(Comparable newel) {
    BST2Node<T> n = new BST2Node<T>(newel);
 
    insert (root, n);
  }
 
  void insert(BST2Node<T> p, BST2Node<T> n){
    BST2Node<T> pv = null;
 
    if (p == root && root == null){
      root = n;
      return;
    }
 
    while (p != null) {
      pv = p;
      if (p.compareTo(n) < 0){
        p = p.right;
      }
      else{
        p = p.left;
      }
    }
    if (pv.compareTo(n) < 0){
      pv.right = n;
    }
    else{
      pv.left = n;
    }  
  }
 
  public Comparable isInTree(Comparable el) {
    return search(el);
  }
 
  public Comparable search(Comparable el) {
    return search(root, el);
  }
 
  public void updateNode(Comparable newel){
    BST2Node<T> p = root;
    BST2Node<T> n = new BST2Node<T>(newel);
 
    while (p != null){
      if (n.equals(p)){
        p = n;
        break;
      }
      else if (n.compareTo(p) < 0){
        p = p.left;
      }
      else{
        p = p.right;
      }
    }
  }
 
  protected Comparable search(BST2Node<T> p, Comparable el) {
    BST2Node<T> node = new BST2Node<T>(el);
    
    while (p != null){
      if (node.equals(p)){
        return p.el;
      }
      else if (node.compareTo(p) < 0){
        p = p.left;
      }
      else{
        p = p.right;
      }
    }
    return null;
  }
 
  public void preorder() {
    preorder(root);
  }
 
  public void inorder() {
    inorder(root);
  }
 
  public void postorder() {
    postorder(root);
  }
 
  protected void visit(BST2Node<T> p) {
    System.out.println(p.el.toString());
  }
 
  protected void inorder(BST2Node<T> p) {
    if (p != null) {
      inorder(p.left);
      visit(p);
      inorder(p.right);
    }
  }
 
  protected void preorder(BST2Node<T> p) {
    if (p != null) {
      visit(p);
      preorder(p.left);
      preorder(p.right);
    }
  }
 
  protected void postorder(BST2Node<T> p) {
    if (p != null) {
      postorder(p.left);
      postorder(p.right);
      visit(p);
    }
  }
} // class BST2
 
class BST2Node<T> implements Comparable{
  protected Comparable el;
  protected BST2Node<T> left, right;
  protected BST2Node<T> root = null;
 
  public BST2Node() {
    left = right = null;
    el = null;
  }
 
  public BST2Node(Comparable el) {
    this(el, null, null);
  }
 
  public BST2Node(Comparable el, BST2Node lt, BST2Node rt) {
    this.el = el; left = lt; right = rt;
  }
 
  public boolean equals(Object node){
    BST2Node<T> nd = (BST2Node<T>)node;
    return (el.equals(nd.el));
  }
 
  public int compareTo(Object node){
    BST2Node<T> nd = (BST2Node<T>)node;
    return (el.compareTo(nd.el));
  }
} // class BST2Node
 
class Tokens{
 
  static BST2<Word> readTokens(String fInName){
    String line;
    int linenum;
    Word wdn, wdo;
 
    wdn = wdo = null;
    BST2<Word> tree = new BST2<Word>();
 
    try{
      LineNumberReader fIn = new LineNumberReader(new FileReader(fInName));
 
      while((line = fIn.readLine()) != null){
        if (line.length() < 1){
          continue;
        }
        linenum = fIn.getLineNumber();
        String[] words = line.split("\\W+");
        if (words.length < 1){
          continue;
        }
        for (String s : words){
          if (s.length() < 2){
            continue;
          }
          wdn = new Word(s);
          wdo = (Word)(tree.isInTree(wdn));
          if (wdo == null){ // new word
            wdn.addLineNum(linenum);
            tree.insert(wdn);
          }
          else{
            wdo.addLineNum(linenum);
            wdo.incrFreq();
            tree.updateNode(wdo);
          }
        }
      }
      fIn.close();
    }
    catch (Exception e){
      e.printStackTrace();
    }
    return tree;
  }
} // class Tokens
 
class Word implements Comparable{
  private String text;
  int freq;
  LinkedList<Integer> list;
 
  public Word(String s){
    text = s.toLowerCase();
    freq = 1;
    list = new LinkedList<Integer>();
  }
 
  public void addLineNum(int n){
    list.add(n);
  }
 
  public int grtFreq(){
    return freq;
  }
 
  public String getText(){
    return text;
  }
 
  public LinkedList<Integer> getList(){
    return list;
  }
 
  public void incrFreq(){
    ++freq;
  }
 
  public boolean equals(Object el){
    Word w = (Word)el;
    String t = w.getText();
    return text.equalsIgnoreCase(t);
  }
 
  public int compareTo(Object el){
    Word w = (Word)el;
    String t = w.getText();
    return text.compareToIgnoreCase(t);
  }
 
  public String toString(){
    return text + " : " + freq + " times, lines at : " + list.toString();
  }
} // class Word
 
public class BST2Test{
 
  public static void main(String[] args)throws IOException{
    BST2<Word> bst;
    String fInName = "test.txt";
 
    Scanner kb = new Scanner(System.in);
    System.out.println("Please Enter Your File Name: ");
    String fn  = kb.nextLine();
    if (fn.length() > 0){
      fInName = fn;
    }
    bst = Tokens.readTokens(fInName);
    bst.inorder();
  }
} // test driver BST2Test

 

 

Why does Node implement Comparable and not class BST2? Arent the methods for the class BST2? How does implementing Comparable on the Node work?