Source Code

Get programs to develop you own applications.

Binary Search Tree

Posted by mohammedmoulana on March 26, 2012

A binary search tree is a binary tree that is either empty or in which every node contains a key and satisfies the conditions:
(1)The key in the left child of a node (if it exists) is less than the key in its parent node.
(2)The key in the right child of a node (if it exists) is greater than the key in its parent node.
(3)The left and right subtrees of the root are again binary search trees.
The first two properties describe the ordering relative to the key in the root node, and that the third property extends them to all nodes in the tree; hence we can continue to use the recursive structure of the binary tree. After we examine the root of the tree, we shall move to either its left or right subtree, and this subtree is again a binary search tree. Thus we can use the same method again on this smaller tree. This definition assumes that no duplicate keys are permitted.

Binary search tree

Binary search tree operations

class BSTNode
{
int data;
BSTNode left;
BSTNode right;
BSTNode( int d ) // constructor
{ data = d; }
}
class BinarySearchTree
{

public BSTNode insertTree(BSTNode p, int key) // create BST
{
if( p == null )
p = new BSTNode(key);
else if( key < p.data)
p.left = insertTree( p.left, key);
else p.right = insertTree( p.right, key);
return p; // return root
}
public BSTNode search(BSTNode root, int key)
{
BSTNode p = root; // initialize p with root
while( p != null )
{ if( key == p.data ) return p;
else if( key < p.data ) p = p.left;
else p = p.right;
}
return null;
}
public int leafNodes(BSTNode p)
{
int count = 0;
if( p != null)
{ if((p.left == null) && (p.right == null))
count = 1;
else
count = count + leafNodes(p.left)
+ leafNodes(p.right);
}
return count;
}

public BSTNode deleteTree(BSTNode root, int key)
{
BSTNode p; // refer to node to be deleted
BSTNode parent = root; // refer to parent of node to be deleted
BSTNode inorderSucc; //refer to inorder succ. of node to be deleted
if(root == null)
{ System.out.println(“Tree is empty”);
return null;
}
p = root; // initialize p with root
/* find node being deleted & its parent */
while( p != null && p.data != key)
{ parent = p;
if( key < p.data) p = p.left;
else p = p.right;
}
if( p == null )
{ System.out.println(“\n Node ” + key + ” not found for deletion”);
return null;
}
/* find inorder successor of the node being deleted and its parent */

if(p.left != null && p.right != null) // case-3
{ parent = p;
inorderSucc = p.right;
while(inorderSucc.left != null)
{
parent = inorderSucc;
inorderSucc = inorderSucc.left;
}
p.data = inorderSucc.data;
p = inorderSucc;
}
if(p.left == null && p.right == null) // case-1
{
if( parent.left == p ) parent.left = null;
else parent.right = null;
}
if(p.left == null && p.right != null) // case-2(a)
{
if(parent.left == p) parent.left = p.right;
else parent.right = p.right;
}
if(p.left != null && p.right == null) // case-2(b)
{
if(parent.left == p) parent.left = p.left;
else parent.right = p.left;
}
return root;
}

public void inorder(BSTNode p) // ‘p’ starts with root
{ if( p != null )
{ inorder(p.left);
System.out.print(p.data + ” “);
inorder(p.right);
}
}
public void preorder(BSTNode p)
{ if( p != null )
{ System.out.print(p.data + ” “);
preorder(p.left);
preorder(p.right);
}
}
public void postorder(BSTNode p)
{ if( p != null )
{ postorder(p.left);
postorder(p.right);
System.out.print(p.data + ” “);
}
}
}

BinarySearchTreeDemo.java
class BinarySearchTreeDemo
{ public static void main(String args[])
{
int arr[] = { 45, 25, 15, 10, 20, 30, 65, 55, 50, 60, 75, 80 };
BinarySearchTree bst = new BinarySearchTree();

BSTNode root = null;
// build tree by repeated insertions
for( int i = 0; i < arr.length; i++ )
root = bst.insertTree( root, arr[i]);
BSTNode root2 = root; // copy BST
int key = 66;
BSTNode item = bst.search(root2, key);
if( item != null )
System.out.print(“\n item found: ” + item.data);
else System.out.print(“\n Node ” + key + ” not found”);
System.out.print(“\n Number of leaf nodes: ” + bst.leafNodes(root));
System.out.print(“\n Inorder: “);
bst.inorder(root);
System.out.print(“\n Preorder: “);
bst.preorder(root);
System.out.print(“\n Postorder: “);
bst.postorder(root);
key = 55; // delete 55
bst.deleteTree(root, key);
System.out.print(“\n Inorder, after deletion of ” + key + “: “);
bst.inorder(root);
key = 44; // insert 44
bst.insertTree(root, key);
System.out.print(“\n Inorder, after insertion of ” + key + “: “);
bst.inorder(root);
}}

Output of this program is as follows:
Node 66 not found
Number of leaf nodes: 6
Inorder: 10 15 20 25 30 45 50 55 60 65 75 80
Preorder: 45 25 15 10 20 30 65 55 50 60 75 80
Postorder: 10 20 15 30 25 50 60 55 80 75 65 45
Inorder, after deletion of 55: 10 15 20 25 30 45 50 60 65 75 80
Inorder, after insertion of 44: 10 15 20 25 30 44 45 50 60 65 75 80

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

Join 442 other followers

%d bloggers like this: