Skip to Main Content

Java Programming

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

Binary Search Tree Problems

807606Nov 15 2006 — edited Mar 7 2007
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
Comments
Locked Post
New comments cannot be posted to this locked post.
Post Details
Locked on Apr 4 2007
Added on Nov 15 2006
14 comments
444 views