Create code for Binary Search Tree using compareTo method using I/O

[harvin23]

Hi guys/Girls.. i have been trying this question for the past 3 weeks using java SE... i tried very hard but could get the output... do try to help me out...

Question:
Write a program for a bag of strings, where the strings are stored in binary search tree. In creating the binary search tree, you should use the string’s compareTo method.

Once the tree is built, perform preorder, inorder, and postorder traversal.

Note: The strings should be read from a text file that contains sentences. Create your own text file and limit your sentences to 5.

[masijade]

Well, let's see what you have.

[ejosiah]

maybe this might help. I wrote this a week ago and it has been tested so it works. use it to build your tree

public class Node {
	private Node left;
	private Node right;
	private Node parent;
	private Object value;
	
	public Node(Object value){
		this(value, null, null);
	}
	
	public Node(Object value, Node left, Node right){
		this.value = value;
		this.left = left;
		this.right = right;
		setParent(parent);
	}
	
	private void setParent(Node parent2) {
		if(left != null){
			left.parent = this;
		}
		if(right != null){
			right.parent = this;
		}
		
	}

	public Node getLeftNode(){
		return left;
	}
	
	public Node getRigthNode(){
		return right;
	}
	
	public Object getValue(){
		return value;
	}
	

	public Node minimum() {
		Node minimum = this;
		
		while(minimum.left != null){
			minimum = minimum.left;
		}
		
		return minimum;
		
	}

	public Node maximum() {
		Node maximum = this;
		
		while(maximum.right != null){
			maximum = maximum.right;
		}
		
		return maximum;
	}

	public Node successor() {
		if(right != null){
			return right.minimum();
		}
		
		Node current = this;
		Node successor = current.parent;
		while(successor != null){
			if(successor.left == current){
				break;
			}else{
				current = successor;
				successor = current.parent;
			}
		}
		return successor;
			
		
	}
	
	public String toString(){
		return value.toString();
	}

	public Node predecessor() {
		if(left != null){
			return left.maximum();
		}else{
			Node current = this;
			Node predecessor = current.parent;
			while(predecessor != null){
				if(predecessor.right == current){
					break;
				}else{
					current = predecessor;
					predecessor = current.parent;
				}
			}
			return predecessor;
		}
	}

	public boolean isSmaller() {
		if(isRootNode()){
			return false;
		}
		return parent.left == this;
	}

	public boolean isLarger() {
		if(isRootNode()){
			return false;
		}
		return !isSmaller();
	}
	
	public boolean isRootNode(){
		return parent == null;
	}
	
	public boolean isLeafNode(){
		return left == null && right == null;
	}

	public int size() {
		return size(this);
	}
	
	private int size(Node node){
		if(node == null){
			return 0;
		}
		return 1 + size(node.left) + size(node.right);
	}
	
	public boolean equals(Object obj){
		if(obj == null){
			return false;
		}else if(obj == this){
			return true;
		}else if(obj instanceof Node){
			Node other = (Node)obj;
			return this.value.equals(other.value) && equals(this.left, other.left) && 
				equals(this.right, other.right);
		}else{
			return false;
		}
	}
	
	private boolean equals(Node child, Node node){
		if(child == null){
			return child == node;
		}
		return child.equals(node);
	}
	

}

[ejosiah]

maybe this might help. I wrote this a week ago and it has been tested so it works. use it to build your tree

public class Node {
	private Node left;
	private Node right;
	private Node parent;
	private Object value;
	
	public Node(Object value){
		this(value, null, null);
	}
	
	public Node(Object value, Node left, Node right){
		this.value = value;
		this.left = left;
		this.right = right;
		setParent(parent);
	}
	
	private void setParent(Node parent2) {
		if(left != null){
			left.parent = this;
		}
		if(right != null){
			right.parent = this;
		}
		
	}

	public Node getLeftNode(){
		return left;
	}
	
	public Node getRigthNode(){
		return right;
	}
	
	public Object getValue(){
		return value;
	}
	

	public Node minimum() {
		Node minimum = this;
		
		while(minimum.left != null){
			minimum = minimum.left;
		}
		
		return minimum;
		
	}

	public Node maximum() {
		Node maximum = this;
		
		while(maximum.right != null){
			maximum = maximum.right;
		}
		
		return maximum;
	}

	public Node successor() {
		if(right != null){
			return right.minimum();
		}
		
		Node current = this;
		Node successor = current.parent;
		while(successor != null){
			if(successor.left == current){
				break;
			}else{
				current = successor;
				successor = current.parent;
			}
		}
		return successor;
			
		
	}
	
	public String toString(){
		return value.toString();
	}

	public Node predecessor() {
		if(left != null){
			return left.maximum();
		}else{
			Node current = this;
			Node predecessor = current.parent;
			while(predecessor != null){
				if(predecessor.right == current){
					break;
				}else{
					current = predecessor;
					predecessor = current.parent;
				}
			}
			return predecessor;
		}
	}

	public boolean isSmaller() {
		if(isRootNode()){
			return false;
		}
		return parent.left == this;
	}

	public boolean isLarger() {
		if(isRootNode()){
			return false;
		}
		return !isSmaller();
	}
	
	public boolean isRootNode(){
		return parent == null;
	}
	
	public boolean isLeafNode(){
		return left == null && right == null;
	}

	public int size() {
		return size(this);
	}
	
	private int size(Node node){
		if(node == null){
			return 0;
		}
		return 1 + size(node.left) + size(node.right);
	}
	
	public boolean equals(Object obj){
		if(obj == null){
			return false;
		}else if(obj == this){
			return true;
		}else if(obj instanceof Node){
			Node other = (Node)obj;
			return this.value.equals(other.value) && equals(this.left, other.left) && 
				equals(this.right, other.right);
		}else{
			return false;
		}
	}
	
	private boolean equals(Node child, Node node){
		if(child == null){
			return child == node;
		}
		return child.equals(node);
	}
	

}

[harvin23]

hi ejosiah... thanks for the code but it doesnt have compareTo method... i will try to work on it... this is my code...

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

public class BinarySearchTree {

public BinarySearchTree( ) {
root = null;
}

public void insert( Comparable x ) {
root = insert( x, root );
}


public void remove( Comparable x ) {
root = remove( x, root );
}


public void removeMin( ) {
root = removeMin( root );
}


public Comparable findMin( ) {
return elementAt( findMin( root ) );
}


public Comparable findMax( ) {
return elementAt( findMax( root ) );
}


public Comparable find( Comparable x ) {
return elementAt( find( x, root ) );
}

public void makeEmpty( ) {
root = null;
}

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


private Comparable elementAt( BinaryNode t ) {
return t == null ? null : t.element;
}


protected BinaryNode insert( Comparable x, BinaryNode t ) {
if( t == null )
t = new BinaryNode( x );
else if( x.compareTo( t.element ) < 0 )
t.left = insert( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = insert( x, t.right );
else
;
return t;
}
}


protected BinaryNode remove( Comparable x, BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( x.toString( ) );
if( x.compareTo( t.element ) < 0 )
t.left = remove( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = removeMin( t.right );
} else
t = ( t.left != null ) ? t.left : t.right;
return t;
}


protected BinaryNode removeMin( BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( );
else if( t.left != null ) {
t.left = removeMin( t.left );
return t;
} else
return t.right;
}


protected BinaryNode findMin( BinaryNode t ) {
if( t != null )
while( t.left != null )
t = t.left;

return t;
}


private BinaryNode findMax( BinaryNode t ) {
if( t != null )
while( t.right != null )
t = t.right;

return t;
}


private BinaryNode find( Comparable x, BinaryNode t ) {
while( t != null ) {
if( x.compareTo( t.element ) < 0 )
t = t.left;
else if( x.compareTo( t.element ) > 0 )
t = t.right;
else
return t;
}

return null;
}


protected BinaryNode root;



public static void main( String [ ] args ) {
BinarySearchTree t = new BinarySearchTree( );
final int NUMS = 4000;
final int GAP = 37;

System.out.println( "Checking... (no more output means success)" );

for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( new Integer( i ) );

for( int i = 1; i < NUMS; i+= 2 )
t.remove( new Integer( i ) );

if( ((Integer)(t.findMin( ))).intValue( ) != 2 ||
((Integer)(t.findMax( ))).intValue( ) != NUMS - 2 )
System.out.println( "FindMin or FindMax error!" );

for( int i = 2; i < NUMS; i+=2 )
if( ((Integer)(t.find( new Integer( i ) ))).intValue( ) != i )
System.out.println( "Find error1!" );

for( int i = 1; i < NUMS; i+=2 ) {
if( t.find( new Integer( i ) ) != null )
System.out.println( "Find error2!" );
}

[ejosiah]

hey this is not the binary tree class; it represents a node in a Tree. it implements everything a node needs to do about it self in a tree so what is left for you to do is to create The BinaryTree class and wrap this class inside it

[ejosiah]

Encapsulate your BinaryTree class with the Node class I've given you. instead of using your findMin or findMax and other methods in your class just call minimum, maximum or the required methods on the Node class as in

node.minimum()

.

during your CRUD operations on the Tree get the Nodes value and then perform a comparasion on that value i.e

node.getValue().compareTo(anotherNode.getValue())

can you see where I'm going now