The code for binary search tree written in class on Wedn., Oct. 20th. Includes the IntNode class, the IntBST class, and the testing program.

public class IntNode {
    private IntNode left, right;
    private int data;
    
    public IntNode(int d){
	data = d;
    }
    
    public IntNode getLeft(){
	return left;
    }
    
    public IntNode getRight(){
	return right;
    }
    public void setLeft(IntNode in){
	left = in;
    }
    public void setRight(IntNode in){
	right = in;
    }
    
    public int getData() {
	return data;
    }
    
}


public class IntBST {
    private IntNode root;
    
    public IntBST() {
    }
    
    public boolean isEmpty() {
	return (root == null);
    }
    
    public IntNode getRoot(){
	return root;
    }
    
    // return the reference to the IntNode containing data
    // null if there is no such node
    // This is the search method written by Steve and, independently,
    // by Kyle and Eugene
    public IntNode search(int data ) {
        IntNode node = root;

        while (node != null && node != node.getData){
            if (data > node.getData){
                node = node.getRight();
            } else {
                node = node.getLeft();
            }
        }
        return node;
    }

    // This is a search method written by Scott. It's close
    // to insert method, so we will use it write 'insert'
    public IntNode search2(int data ) {
	if(!isEmpty()){
	    IntNode parent = getRoot();
	    IntNode child;
	    if(data < parent.getData){
		child = parent.getLeft();
	    } else {
		child = parent.getRight();
	    }
	    
	    while(child != null){
		if(data < child.getData()){
		    parent = child;
		    child = child.getLeft();
		} else {
		    parent = child;
		    child = child.getRight();
		}
	    }
	    if(child.getData() == data){
		return child;
	    }
	}
	return null;
    }
    
    // insert the data into the binary serach tree
    // return the reference to the new node containing data
    // if there already is such a node, return null
    public IntNode insert(int data) {
	
    }
}

This is the testing program for the IntBST class. Can you think of a way to test the search method without writing the insert method?

public class TestIntBST {
    public static void main(String [] args) {
	IntBST bst = new IntBST();
	System.out.println(bst.isEmpty());
	System.out.println(bst.getRoot());
    }
}


This is an example from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.