java binary tree implementation
Binary tree is a data structure that keeps the data in order by having each data wrapped in a node, and each node contains two pointers, one point to the left and one point to the right. the left pointer points to a node that contains data with value less than the current node, the right pointer points to a node that contains data with value greater than the current node. The java class IntBinaryTree below implements the binary tree with each node containing an integer value. It is an unbalanced binary tree. Binary tree contains no duplicates.
import java.util.Random; import java.util.concurrent.atomic.AtomicBoolean; public class IntBinaryTree { // Node class for creating each node in the tree class Node { public Node left; public Node right; int value; public Node(int value) { this.value = value; } } // private fields private Node rootNode; private int size = 0; // tree size, the number of nodes in the tree // Insert the node private void insertNode(Node node, int value) { if (value < node.value) { if (node.left != null) { insertNode(node.left, value); } else { node.left = new Node(value); this.size++; } } else if (value > node.value) { if (node.right != null) { insertNode(node.right, value); } else { node.right = new Node(value); this.size++; } } } // Search a node in the tree private void findNode(Node node, int n, AtomicBoolean found) { if (node != null) { findNode(node.left, n, found); if (node.value == n) { found.set(true); } findNode(node.right, n, found); } } // Print the tree from left to right private void printBT(Node node) { if (node != null) { printBT(node.left); System.out.println(node.value); printBT(node.right); } } // Public insert method, gets the value and then call insertNode to insert the value // in the appropriate position public void insert(int value) { if (this.rootNode == null) { this.rootNode = new Node(value); this.size++; } else { insertNode(this.rootNode, value); } } // Public find method to find a value in the tree public boolean find(int n) { AtomicBoolean found = new AtomicBoolean(); findNode(this.rootNode, n, found); return found.get(); } // Return the size of the binary tree public int getSize() { return this.size; } // Public print method to print the values in the binary tree from left to right public void print() { printBT(this.rootNode); } // Test code // Even though the test size here is 100, but the number to be inserted are from 1 to 10 // Since binary tree contains no duplicates, thus, the result will likely be 1 to 10 public static void main(String[] args) { IntBinaryTree bt = new IntBinaryTree(); Random rand = new Random(); int testSize = 100, maxNum = 10; for(int i=0; i<testSize; i++) { bt.insert(rand.nextInt(maxNum)+1); } bt.print(); System.out.println("Tree size: " + bt.getSize()); System.out.println("Found 2: " + bt.find(2)); System.out.println("Found 22: " + bt.find(22)); } }
Output:
1 2 3 4 5 6 7 8 9 10 Tree size: 10 Found 2: true Found 22: false
Search within Codexpedia
Custom Search
Search the entire web
Custom Search
Related Posts