Spiga

JAVA WAY TO WRITE TREE

JAVA WAY TO WRITE BINARY SEARCH TREE

A binary search tree (BST),is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree. The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node.BST is also known as an ordered binary tree.
BST
Here is the Code to create a binary search tree in java.

import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Stack;
/**
* Creates a Binary Search Tree.
* @author Sonu Mishra
*/
public class BinarySearchTree<E extends Comparable<? super E>>
{
private TreeNode<E> root = null;
public BinarySearchTree() {
root = new TreeNode(null, null, null);
}
public BinarySearchTree(E value) {
root = new TreeNode(null, null, value);
}
public void add(E value) {
addBefore(value, this.root);
}
private TreeNode<E> addBefore(E value, TreeNode root) {
if (root == null)
return new TreeNode<E>(null, null, value);
int compare = root.value.compareTo(value);
if (compare < 1) {
root.right = addBefore(value, root.right);
} else {
root.left = addBefore(value, root.left);
}
return root;
}
public void printInorder() {
root.printInorder(root);
}
public void printLeafNode() {
System.out.println();
System.out.println("Finding the leaf Node");
root.printLeafNode(root);
}
public int heightOfTree() {
System.out.println();
int height = root.heightOfTree(root);
System.out.println("Height Of Tree is " + height);
return height;
}
public TreeNode<E> getRoot() {
return root;
}
public E findMax() {
return findMax(root).value;
}
public TreeNode<E> find(E value) {
return find(value, root);
}
private TreeNode<E> find(E value, TreeNode entry) {
while (entry != null) {
if (value.compareTo(entry.value) < 0)
entry = entry.left;
else if (value.compareTo(entry.value) > 0)
entry = entry.right;
else
return entry;
}
return null;
}
private TreeNode<E> remove(E value, TreeNode entry) {
if (entry == null)
throw new NoSuchElementException("Entry not found : "
+ value.toString());
if (value.compareTo(entry.value) < 0)
entry.left = remove(value, entry.left);
else if (value.compareTo(entry.value) > 0)
entry.right = remove(value, entry.right);
else {
/**
* Entry found.
*/
if (entry.left != null && entry.right != null) {
/**
* Replace with in-order successor (the left-most child of the
* right subtree)
*/
entry.value = findMin(entry.right).value;
entry.right = removeInorderSuccessor(entry.right);
/**
* Replace with in-order predecessor (the right-most child of
* the left subtree) entry.element =
* findMax(entry.left).element; entry.left =
* removeInorderPredecessor(entry.left);
*/
} else
entry = (entry.left != null) ? entry.left : entry.right;
}
return entry;
}
private TreeNode<E> removeInorderSuccessor(TreeNode entry) {
if (entry == null)
throw new NoSuchElementException();
else if (entry.left != null) {
entry.left = removeInorderSuccessor(entry.left);
return entry;
} else
return entry.right;
}
private TreeNode<E> removeInorderPredecessor(TreeNode entry) {
if (entry == null)
throw new NoSuchElementException();
else if (entry.right != null) {
entry.right = removeInorderPredecessor(entry.right);
return entry;
} else
return entry.left;
}   /* Here is the main method to test this tree. */ public static void main(String args[]) {

 BinarySearchTree"<"Integer">" intBinaryTree = new BinarySearchTree"<"Integer">"(15);
intBinaryTree.add(9);  intBinaryTree.add(5);  intBinaryTree.add(11);
intBinaryTree.add(4);  intBinaryTree.add(6);  intBinaryTree.add(10);
intBinaryTree.add(12);  intBinaryTree.add(25);  intBinaryTree.add(20);
intBinaryTree.add(30);  intBinaryTree.add(17);  intBinaryTree.add(21);
intBinaryTree.add(27);  intBinaryTree.add(35);

initBinaryTree.printInorder();
}
}

For the Code of the TreeNode, see the other post in the tree label postings.

0 comments: