Introduction
Binary search tree (BST) is a node-based binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
From the above properties, it naturally follows that each node (item in the tree) has a distinct key. Generally, the information represented by each node is an Object element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.
The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.
Using the Code
As said in the introduction, every node has left and right nodes. Below is how a node should look like:
public class BNode {
public BNode leftBNode, rightBNode;
public AnyClass anyClass;
public BNode(AnyClass anyClass ) {
this.anyClass= anyClass;
this.leftBNode = null;
this.rightBNode = null;
}
public void show() {
System.out.print(anyClass.show());
}
}
Below is a simple class that traverses, adds, and searches for a particular node value:
public class BinTree {
BNode theBTRootNode;
public BinTree()
{
theBTRootNode = null;
}
protected BNode insertAB(BNode theRootNode, BNode myNewNode) {
if (theRootNode == null) {
theRootNode = myNewNode;
} else if (myNewNode.anyClass.surname.compareTo(
theRootNode.anyClass.surname) < 0) {
theRootNode.leftBNode = insertAB(theRootNode.leftBNode, myNewNode);
} else {
theRootNode.rightBNode =
insertAB(theRootNode.rightBNode, myNewNode);
}
return theRootNode;
}
public void insertBST(AnyClass anyClass) {
BNode anyClassBTNode = new BNode(anyClass);
theBTRootNode = insertAB(theBTRootNode, anyClassBTNode);
}
protected void inorder(BNode theRootNode) {
if (theRootNode != null) {
inorder(theRootNode.leftBNode);
theRootNode.show();
inorder(theRootNode.rightBNode);
}
}
public void inorderBST() {
inorder(theBTRootNode);
}
protected BNode search(BNode theRootNode, String keyName) {
if (theRootNode == null) {
return null;
} else {
if (keyName.compareTo(theRootNode.anyClass.surname) == 0) {
return theRootNode;
} else if (keyName.compareTo(theRootNode.anyClass.surname) < 0) {
return search(theRootNode.leftBNode, keyName);
} else {
return search(theRootNode.rightBNode, keyName);
}
}
}
public AnyClass searchBST(String keyName) {
BNode temp = search(theBTRootNode, keyName);
if (temp == null) {
return null;
} else {
return temp.anyClass;
}
}
}
Points of Interest
This should help you a lot in achieving faster applications when traversing through a list.
You can add this method to the BinTree
class object to transfer your lists to a binary tree:
public void populateBinTree(List theList) {
theBTRootNode = null;
for(int i = 0;i < theList.size();i++)
Node temporaryNode = null;
insertBST((AnyClass)theList.get(i));
}
}
History