Java Reference
In-Depth Information
TRY IT OUT: Sorting Using a Binary Tree
You need to create a directory to hold the three source files for this program. When you've set that up,
copy the
LinkedList.java
source file from the previous example to the new directory. You can then
add the
BinaryTree.java
source file containing the following code to the directory:
public class BinaryTree<T extends Comparable<T>> {
// Add a value to the tree
public void add(T value) {
if(root == null) {
// If there's no root node
root = new Node(value);
// store it in the root
} else {
// Otherwise...
add(value, root);
// add it recursively
}
}
// Recursive insertion of an object
private void add(T value, Node node) {
int comparison = node.obj.compareTo(value);
if(comparison == 0) {
// If it is equal to the
current node
++node.count;
// just increment the count
return;
}
if(comparison > 0) {
// If it's less than the
current node
if(node.left == null) {
// and the left child node is
null
node.left = new Node(value);
// Store it as the left child
node
} else {
// Otherwise...
add(value, node.left);
// ... call add() again at the
left node
}
} else {
// It must be greater than the
current node
if(node.right == null) {
// so it must go to the
right...
node.right = new Node(value); // store it as the right node
} else {
// ...or when right node is
not null
add(value, node.right);
// ...call add() again at the
right node
}
}
}
