Binary tree data structure is one of the fundamental data structures that appears in the beginning of the computer science course. In this post, I will explain a very simple binary tree class implementation in Java. As someone who has come from C/C++ language, it was a wonder for me how Java implements binary tree data structure, for Java supposedly does not have the concept of a pointer. However after studying Java for some time, it appears to me that Java actually does make use of pointers extensively. All the primitive data types, such as int, char, boolean are passed by its values while all objects are passed by reference. It turns out that Java's implementation makes it easier for programmers to write code at the expense of perhaps sacrificing the speed compared to C/C++; with C/C++ programmers have the maximum capability to manipulate every single details of the code and optimize for speed boost whereas with Java programmers are stuck with Java's built-in optimization.
In any case, here is the Java code for implementation of the tree class
// Tree.java
public class Tree {
private static class Node {
int data;
Node left;
Node right;
/** Node constructor that adds the data
*
* @param data to be inserted
*/
Node (int data) {
data = data;
left = null;
right = null;
}
}
private Node root;
Tree () {
root = null;
}
/** insert a new data into the tree incapsulation method
*
* @param data to be inserted
*/
public void insert (int data) {
root = insert(root, data);
}
/** insert data actual implementation method
* in this version of binary tree, the data will be appended
* to the right tree if it is equal
*
* @param node is the current node
* @param data to be inserted
* @return the node in which data is inserted
*/
private Node insert (Node node, int data) {
if (node == null)
node = new Node (data);
else if (data < node.data)
node.left = insert (node.left, data);
else // if (data >= node.data)
node.right = insert (node.right, data);
return node;
}
/** lookup data incapsulation method
*
* @param data to be searched within the tree
* @return the total number of nodes that contain the data
*/
public int lookup (int data) {
return lookup (root, data);
}
/** lookup data actual implementation method
*
* @param node is the current node
* @param data is the data to be searched
* @return the number of nodes containing the data in the
* subtree starting from node
*/
private int lookup (Node node, int data) {
if (node == null)
return 0;
else if (node.data == data)
return lookup (node.right, data) + 1;
else if (data < node.data)
return lookup (node.left, data);
else
return lookup (node.right, data);
}
}
Any experienced C++ programmers should immediately understand what the code is doing and what each method is doing. For actual implementation of the binary tree, below is the Main class that builds a tree from Tree.java
// Main.java
public class Main {
/** main method
*
* @param args is the argument strings passed from the user
*/
public static void main(String[] args) {
Tree binaryTree = new Tree();
binaryTree.insert(2);
binaryTree.insert(1);
binaryTree.insert(-2);
binaryTree.insert(1);
System.out.println("lookup(1) = " + binaryTree.lookup(1));
}
}
No comments:
Post a Comment