The code for binary search tree written in class on Thursday.,
Oct. 21th. Includes the IntNode class, the IntBST class. Demonstrates
a recursive in-order traversal.
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 void setData(int data) {
this.data = data;
}
public void inOrder() {
if (left != null) left.inOrder();
System.out.println(data);
if (right != null) right.inOrder();
}
}
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 && data != node.getData()){
if (data > node.getData()){
node = node.getRight();
} else {
node = node.getLeft();
}
}
return node;
}
// 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) {
if(!isEmpty()){
IntNode parent = getRoot();
IntNode child;
if (data == parent.getData()) {
return null;
}
if(data < parent.getData()){
child = parent.getLeft();
} else {
child = parent.getRight();
}
while(child != null){
if(data < child.getData()){
parent = child;
child = child.getLeft();
}
else if (data > child.getData()) {
parent = child;
child = child.getRight();
}
else return null;
}
IntNode node = new IntNode(data);
if(parent.getData() < data){
parent.setRight(node);
}
else{
parent.setLeft(node);
}
return node;
}
// if the tree is empty
IntNode node = new IntNode(data);
root = node;
return node;
}
public void inOrder() {
if (root != null) root.inOrder();
}
}
This is an example from CSci 2101 course.