This is an implementation of a binary tree in Java.
Binary Tree
The following java class is the representation of a Binary Tree, which includes common methods such as insert(), maximum() and depth().
public class BinaryTree {
// Define the root node.
private BinaryNode _root;
/**
* Insert into the tree.
* @param value
*/
public void insert(int value){
// If we don't have a root node, make one.
if(_root == null){
// Make the root node.
_root = new BinaryNode(value);
} else {
// Set the current node.
BinaryNode current = _root;
// Find the proper spot.
while(current != null){
// Compare values.
if(value < current.getValue()){
// Insert on the left.
if(current.getLeft() == null){
current.setLeft(new BinaryNode(value));
return;
} else {
current = current.getLeft(); // Go to next left.
}
} else {
// Insert on the right.
if(current.getRight() == null){
current.setRight(new BinaryNode(value));
return;
} else {
current = current.getRight(); // Go to next right.
}
}
}
}
}
/**
* Get the minimum value in the tree.
* @return
*/
public int minimum(){
// Make sure we have at least one node.
if(_root != null){
// Set the current node.
BinaryNode current = _root;
// Iterate until we hit the last left node.
while(current.getLeft() != null){
current = current.getLeft();
}
// Return the value of the last left node.
return current.getValue();
} else {
return 0;
}
}
/**
* Get the maximum value in the tree.
* @return
*/
public int maximum(){
// Make sure we have at least one node.
if(_root != null){
// Set the current node.
BinaryNode current = _root;
// Iterate until we hit the last right node.
while(current.getRight() != null){
current = current.getRight();
}
// Return the value of the last right node.
return current.getValue();
} else {
return 0;
}
}
/**
* Print the binary tree in ascending order of value.
* @param n
*/
public void print(BinaryNode n){
if(n == null){
return;
} else {
print(n.getLeft());
System.out.println(n.getValue());
print(n.getRight());
}
}
public void print(){
print(_root);
}
/**
* Return the number of nodes in the tree.
* @return
*/
public int size(BinaryNode n){
// If the node is null, return 0.
if(n == null){
return 0;
} else {
// We have at least one element. Get the size of it's children.
return 1 + size(n.getLeft()) + size(n.getRight());
}
}
public int size(){
return size(_root);
}
/**
* Return the (max) depth of the tree.
* @return
*/
public int depth(BinaryNode n){
// Base case.
if(n == null){
return 0;
} else {
// Get the depth of the left side.
int leftSideDepth = depth(n.getLeft());
// Get the depth of the right size.
int rightSideDepth = depth(n.getRight());
// Return the maximum depth of the two.
return 1 + Math.max(leftSideDepth, rightSideDepth);
}
}
public int depth(){
return depth(_root);
}
}
Binary Node
This class represents the nodes used in the binary tree. It has simple getValue() and setValue() methods.
public class BinaryNode {
// References to left and right nodes.
private BinaryNode _left;
private BinaryNode _right;
// The value of the node.
private int _value;
// Constructors.
public BinaryNode(int value){
_value = value;
}
public BinaryNode(int value, BinaryNode nL, BinaryNode nR){
_value = value;
_left = nL;
_right = nR;
}
// Getter & setter for the value.
public int getValue(){
return _value;
}
public void setValue(int value){
_value = value;
}
// Getters & setters for left & right nodes.
public BinaryNode getLeft(){
return _left;
}
public BinaryNode getRight(){
return _right;
}
public void setLeft(BinaryNode n){
_left = n;
}
public void setRight(BinaryNode n){
_right = n;
}
}
Tester
This is the tester class for populating the binary tree and checking the validity of its methods.
public class Test {
public static void main(String[] args){
BinaryTree tree = new BinaryTree();
tree.insert(26);
tree.insert(11);
tree.insert(31);
tree.insert(6);
tree.insert(17);
tree.insert(44);
tree.insert(2);
tree.insert(39);
tree.insert(20);
System.out.println("Minimum in tree: " + tree.minimum());
System.out.println("Maximum in tree: " + tree.maximum());
System.out.println("Size of tree: " + tree.size());
System.out.println("Depth of tree: " + tree.depth());
tree.print();
}
}