IntNode class for a tree of integers

public class IntNode {
    private int data;
    private IntNode left;
    private IntNode right;

    public IntNode(int data) {
	this.data = data;
    }
    
    public int getData() {
	return data;
    }

    public IntNode getLeft() {
	return left;
    }

    public void setData(int data) {
	this.data = data;
    }

    public IntNode getRight() {
	return right;
    }

    public void setLeft(IntNode theleft) {
	left = theleft;
    }

    public void setRight(IntNode theright) {
	right = theright;
    } 

    // recursive in-order traversal
    public void inorder() {
	if (left != null) left.inorder();
	System.out.println(data);
	if (right != null) right.inorder();
    }

    public int countNodes() {
	int leftCount = 0, rightCount = 0;
	if (left != null) leftCount = left.countNodes();
	if (right != null) rightCount = right.countNodes();
	return 1 + leftCount + rightCount;
    }
}


The code for binary search tree written in class.

    public class IntBST {
    private IntNode root;

    // constructor
    public IntBST() {
        // do nothing
    }



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

    // returns the address of the IntNode containing n
    // if there is no such node, returns null
    // Author: Nate Fortuna
    public IntNode search (int n) {
        IntNode node = root;
        while(node != null && node.getData() != n){
            if (n > node.getData()){
                node = node.getRight();
            }else{
                node = node.getLeft();
            }
        }
        return node;
    }

    // inserts n into the Binary Search Tree
    // returns the address of the new IntNode containing n
    // if there already is such a node, the method doesn't 
    // create a new node and returns null
    // Author: Rob Jansen
    public IntNode insert (int n) {
    IntNode node = root;

    while(true)
    {
        if(node == null)
        {
            root = new IntNode(n);
            return root;
        }
        else if(n > node.getData())
        {
            if(node.getRight() == null)
            {
                node.setRight(new IntNode(n));
                return node.getRight();
            }
            else
            {
                node = node.getRight();
            }
        }
        else if(n < node.getData())
        {
            if(node.getLeft() == null)
            {
                node.setLeft(new IntNode(n));
                return node.getLeft();
            }
            else
            {
                node = node.getLeft();
            }
        }
        else
        {
            return null;
        }
    }
        //return null;
    }

    public void inorder() {
	if (root != null) root.inorder();
    }

    public int countNodes() {
	if (root != null) return root.countNodes();
	return 0;
    }


}

Testing program:

public class TestIntBST {
    public static void main(String [] args) {
        IntBST bst = new IntBST();

        bst.insert(6);
        bst.insert(2);
        bst.insert(8);
        bst.insert(5);
        bst.insert(3);
        bst.insert(10);
        System.out.println(bst.insert(5));

        for (int i = 1; i <= 10; ++i) {
            IntNode node = bst.search(i);
            if (node != null) {
                System.out.println(node.getData());
            }
        }

	bst.inOrder();
	System.out.println(bst.countNodes());
    }
}

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.