Monday, March 24, 2014

Binary Tree in Java



import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
private TreeNode root;

/** Inner class tree node */
private class TreeNode {
Object element;
TreeNode left;
TreeNode right;

public TreeNode(Object o) {
element = o;
}

}

/** Create a default binary tree */
public BinaryTree() {
}

/** Create a binary tree from an array of objects */
public BinaryTree(Object[] objects) {
for (int i = 0; i < objects.length; i++) {
insert(objects[i]);
}
}

/** Search element o in this binary tree */
public boolean search(Object o) {
return search(o, root);
}

public boolean search(Object o, TreeNode root) {
if (root == null) {
return false;
}
if (root.element.equals(o)) {
return true;
} else {
return search(o, root.left) || search(o, root.right);
}
}

/** Return the number of nodes in this binary tree */
public int size() {
return size(root);
}

public int size(TreeNode root) {
if (root == null) {
return 0;
} else {
return 1 + size(root.left) + size(root.right);
}
}

/**
* Return the depth of this binary tree. Depth is the number of the nodes in
* the longest path of the tree
*/
public int depth() {
return depth(root);
}

public int depth(TreeNode root) {
if (root == null) {
return 0;
} else {
return 1 + Math.max(depth(root.left), depth(root.right));
}
}

/**
* Insert element o into the binary tree Return true if the element is
* inserted successfully
*/
public boolean insert(Object o) {
if (root == null) {
root = new TreeNode(o); // Create a new root
} else {
// Locate the parent node
TreeNode parent = null;
TreeNode current = root;
while (current != null) {
if (((Comparable) o).compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (((Comparable) o).compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
return false; // Duplicate node not inserted
}
}

// Create the new node and attach it to the parent node
if (((Comparable) o).compareTo(parent.element) < 0) {
parent.left = new TreeNode(o);
} else {
parent.right = new TreeNode(o);
}
}

return true; // Element inserted
}

public void breadth() {
breadthFirst(root);
}

// Implement this method to produce a breadth first
// search traversal
public void breadthFirst(TreeNode root) {
if (root == null)
return;
Queue queue = new LinkedList();
queue.clear();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.remove();

System.out.print(node.element + " ");
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
}

public void depthFirst() {
depthFirst(root);
}

/**
* Depth first traversal.
*/
public void depthFirst(TreeNode root) {
if (root == null)
return;
Deque stack = new ArrayDeque();
stack.clear();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();

System.out.print(node.element + " ");
if (node.left != null)
stack.push(node.left);
if (node.right != null)
stack.push(node.right);
}
}

/** Inorder traversal */
public void inorder() {
inorder(root);
}

/** Inorder traversal from a subtree */
private void inorder(TreeNode root) {
if (root == null) {
return;
}
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}

/** Postorder traversal */
public void postorder() {
postorder(root);
}

/** Postorder traversal from a subtree */
private void postorder(TreeNode root) {
if (root == null) {
return;
}
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}

/** Preorder traversal */
public void preorder() {
preorder(root);
}

/** Preorder traversal from a subtree */
private void preorder(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);

}

}

Test code:

import org.junit.Test;

public class BinaryTreeTest {

@Test
public void test() {
BinaryTree tree = new BinaryTree(new Integer[] {10, 5, 15, 12, 4, 8 });

   System.out.print("\nInorder: ");
   tree.inorder();
   System.out.print("\nPreorder: ");
   tree.preorder();
   System.out.print("\nPostorder: ");
   tree.postorder();

   //call the breadth method to test it

   System.out.print("\nBreadthFirst:");
   tree.breadth();
   System.out.print("\nDepthFirst:");
   tree.depthFirst();
}

}

No comments:

Book notes: Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems, by Martin Kleppmann

My notes from the excellent book on how software has evolved to handle data from hierarchical databases to the NoSQL -  https://www.goodrea...