Welcome to HBH! If you had an account on hellboundhacker.org you will need to reset your password using the Lost Password system before you will be able to login.
binary search tree in java
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package datastructures;
import java.io.*;
/**
*
* @author unwanted
*/
public class bitree {
static class tnode
{
int data;
tnode left;
tnode right;
tnode(int i)
{
data=i;
}
}
tnode root;
bitree()
{
root=null;
}
boolean isEmpty()
{
if(root==null)
return true;
else
return false;
}
void insert(tnode temp,int obj)
{
if(obj<temp.data)
{
if(temp.left!=null)
insert(temp.left,obj);
else
temp.left=new tnode(obj);
}
else if(obj>temp.data)
{
if(temp.right!=null)
insert(temp.right,obj);
else
temp.right=new tnode(obj);
}
else
System.out.println("element already exits");
}
void create(int obj)
{
if(isEmpty())
{
root=new tnode(obj);
}
else
{
insert(root,obj);
}
}
int deletemin(tnode p)
{
int c;
if(p.left==null)
{
c=p.data;
p=p.right;
return c;
}
else
c=deletemin(p.left);
return c;
}
int del(tnode temp,int i)
{
int dummy=-1;
if(temp==null)
dummy=-1;
else if(i<temp.data)
{
del(temp.left,i);
}
else if(i>temp.data)
{
del(temp.right,i);
}
else if(temp.left==null)
{
dummy=temp.data;
temp=temp.right;
System.out.print(dummy);
}
else if(temp.right==null)
{
dummy=temp.data;
temp=temp.left;
}
else if((temp.left==null)&&(temp.right==null))
{
dummy=temp.data;
temp=null;
}
else
dummy=deletemin(temp.right);
return dummy;
}
int delete(int i)
{
if(isEmpty())
return -1;
else
{
int ans=del(root,i);
return ans;
}
}
void in(tnode temp1)
{
if(temp1!=null)
{
in(temp1.left);
System.out.println(temp1.data);
in(temp1.right);
}
}
void inorder()
{
if(isEmpty())
System.out.println("no elements found");
else
{
in(root);
}
}
public static void main(String args[]) throws IOException
{
bitree b=new bitree();
Integer ch,i;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
out: while(true)
{
System.out.println("1.insert \n2.delete \n 3.display \n4.exit");
ch=Integer.parseInt(br.readLine());
switch(ch)
{
case 1: try
{
System.out.println("enter element to be inserted");
Integer j=Integer.parseInt(br.readLine());
b.create(j);
}
catch(NumberFormatException e1)
{
System.out.println("enter integers only");
}
break;
case 2: try
{
System.out.println("enter element to delete");
int j=Integer.parseInt(br.readLine());
int rm=b.delete(j);
if(rm==-1)
{
//System.out.println(rm);
throw new NullPointerException();
}
else
System.out.println("deleted element is"+rm);
}
catch(NullPointerException e)
{
System.out.println("element not found exce");
}
catch(NumberFormatException e3)
{
System.out.println("enter integers only");
}
break;
case 3: b.inorder();
break;
case 4: break out;
default : System.out.println("enter correct choice");
}
}
}
}
insertion and display works fine but deletion operation not working properly :( dont know whats wrong in it.. help me with deletion operation thank u :D im not gud at english :|
Your lack of booleans makes me want to kill myself. throwing -1 is useless when you could just use false. Also, your node constructor sucks and you don't catch duplicate errors. Also, throw yourself off a bridge if you think your syntax is good. I'm not even going to get into why your delete doesn't work. I'll let you figure out why making p = p.right without checking if p.right is not null and returning its value is not going to work.
Also, why the hell are you importing java.io.* ?
Here is a proper recursive BST:
public class BinarySearchTree {
protected TreeNode root;
int size;
public BinarySearchTree () {
root = null;
}
public void insert (int x) throws Exception {
root = insert(x, root);
size++;
}
protected TreeNode insert(int x, TreeNode y) throws Exception {
if (y == null || isEmpty() == true) {
y = new TreeNode(x);
}
else if (x < y.data)
y.left = insert(x, y.left);
else if (x > y.data)
y.right = insert(x, y.right);
else
throw new Exception();
return y;
}
public void remove (int x) {
root = remove (x , root);
size--;
}
protected TreeNode remove (int x, TreeNode y) {
if (y == null || isEmpty() == true) {
throw new NullPointerException();
}
else if (x < y.data)
y.left = remove(x, y.left);
else if (x > y.data)
y.right = remove(x, y.right);
else if (y.left != null && y.right != null) {
y.data = findMin(y.right).data;
y.right = removeMin(y.right);
}
else
y = y.left != null ? y.left : y.right;
return y;
}
public void removeMin() {
root = removeMin( root );
size--;
}
protected TreeNode removeMin(TreeNode x) {
if(x == null || isEmpty() == true) {
throw new NullPointerException();
}
else if (x.left != null) {
x.left = removeMin(x.left);
return x;
}
else
return x.right;
}
public void removeMax() {
root = removeMax( root );
size--;
}
protected TreeNode removeMax(TreeNode x) {
if(x == null || isEmpty() == true) {
throw new NullPointerException();
}
else if (x.right != null) {
x.right = removeMax(x.right);
return x;
}
else
return x.left;
}
public int findMin() {
return elementAt(findMin(root));
}
protected TreeNode findMin(TreeNode x) {
if (x != null || isEmpty() == false) {
while( x.left != null)
x = x.left;
}
return x;
}
public int findMax() {
return elementAt(findMax(root));
}
protected TreeNode findMax(TreeNode x) {
if (x != null || isEmpty() == false) {
while( x.right != null)
x = x.right;
}
return x;
}
public int findElement(int x) {
return elementAt(findElement(x, root));
}
private TreeNode findElement(int x, TreeNode y) {
while(y != null && isEmpty() == false) {
if( x < y.data)
y = y.left;
else if ( x > y.data) {
y = y.right;
}
else
return y;
}
return null;
}
public boolean isEmpty() {
if(root == null)
return true;
else
return false;
}
public void makeEmpty() {
root = null;
}
private int elementAt(TreeNode x) {
if (x == null)
return -1;
else
return x.data; // return x == null ? null : x.data;
}
public int sizeOf() {
return size;
}
public void inOrder() {
inOrder(root);
}
private void inOrder(TreeNode x) {
if(x != null) {
inOrder(x.left);
System.out.println(x.data);
inOrder(x.right);
}
}
public static void main( String [ ] args ) throws Exception {
BinarySearchTree t = new BinarySearchTree( );
final int NUMS = 4000;
final int GAP = 37;
System.out.println("Building tree ::");
for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( i );
for( int i = 1; i < NUMS; i += 2 )
t.remove( i );
System.out.println("Maximum: " + t.findMax() + "\tMinimum: " + t.findMin());
System.out.println("Now printing inOrdered tree: ");
t.inOrder();
System.out.println("Size: " + t.sizeOf());
System.out.println("Removing maximum: " + t.findMax());
t.removeMax();
System.out.println("New Maximum: " + t.findMax());
t.makeEmpty();
System.out.println("Called makeEmpty(). New size: " + t.sizeOf());
}
}
class TreeNode {
public TreeNode left;
public TreeNode right;
public int data;
TreeNode(int data) {
this.data = data;
}
TreeNode(TreeNode node) {
left = node.left;
right = node.right;
data = node.data;
}
}```
P.S.: PM me if you wanna learn more about searches and tree types. I'm not a bad guy, I just hate everything about your coding style. :)
EDIT: Updated test cases so you know it works.
import java.io.*;
public class bitree {
class tnode
{
int data;
tnode left;
tnode right;
tnode(int i)
{
data=i;
left=null;
right=null;
}
}
tnode root;
int dummy;
tnode parent;
bitree()
{
root=null;
dummy=-1;
}
boolean isEmpty()
{
if(root==null)
return true;
else
return false;
}
void insert(tnode temp,int obj)
{
if(obj<temp.data)
{
if(temp.left!=null)
insert(temp.left,obj);
else
// insert(temp.left,obj);
temp.left=new tnode(obj);
}
else if(obj>temp.data)
{
if(temp.right!=null)
insert(temp.right,obj);
else
// insert(temp.right,obj);
temp.right=new tnode(obj);
}
else
System.out.println("element already exits");
}
void create(int obj)
{
if(isEmpty())
{
root=new tnode(obj);
}
else
{
insert(root,obj);
}
}
int deletemin(tnode temp1,tnode parent)
{
int c;
if(temp1.left==null)
{ //System.out.println("left\n"+temp1.data);
c=temp1.data;
if(temp1.right==null)
{
if(parent.data<temp1.data)
parent.right=null;
else
parent.left=null;
temp1=null;
}
else
{
parent.left=temp1.right;
temp1=null;
}
return c;
}
else
c=deletemin(temp1.left,temp1);
return c;
}
int del(tnode temp,int i,tnode parent)
{
if(temp==null)
{
System.out.println("element no found");
dummy=-1;
}
else if(i<temp.data)
{
del(temp.left,i,temp);
}
else if(i>temp.data)
{
del(temp.right,i,temp);
}
else if((temp.left==null)&&(temp.right==null))
{
dummy=temp.data;
if(i<parent.data)
parent.left=null;
else
parent.right=null;
temp=null;
}
else if(temp.left==null)
{
dummy=temp.data;
if(i<parent.data)
parent.left=temp.right;
else
parent.right=temp.right;
temp=temp.right;
}
else if(temp.right==null)
{
dummy=temp.data;
if(i<parent.data)
parent.left=temp.left;
else
parent.right=temp.left;
temp=temp.left;
}
else
{
temp.data=deletemin(temp.right,temp);
dummy=i;
}
return dummy;
}
int delete(int i)
{
if(isEmpty())
return -1;
else
{
//tnode alias;
int ans=del(root,i,root);
return ans;
}
}
void in(tnode temp1)
{
if(temp1!=null)
{
in(temp1.left);
System.out.println(temp1.data);
in(temp1.right);
}
}
void pre(tnode temp1)
{
if(temp1!=null)
{
System.out.println(temp1.data);
in(temp1.left);
in(temp1.right);
}
}
void post(tnode temp1)
{
if(temp1!=null)
{
in(temp1.left);
in(temp1.right);
System.out.println(temp1.data);
}
}
void inorder()
{
if(isEmpty())
System.out.println("no elements found");
else
{
in(root);
}
}
void postorder()
{
if(isEmpty())
System.out.println("no elements found");
else
{
post(root);
}
}
void preorder()
{
if(isEmpty())
System.out.println("no elements found");
else
{
pre(root);
}
}
public static void main(String args[]) throws IOException
{
bitree b=new bitree();
Integer ch,i;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
out: while(true)
{
System.out.println("1.insert \n2.delete \n 3.preorder \n 4.inorder \n 5.postorder \n6.exit");
ch=Integer.parseInt(br.readLine());
switch(ch)
{
case 1: try
{
System.out.println("enter element to be inserted");
Integer j=Integer.parseInt(br.readLine());
if(j<0)
throw new NumberFormatException();
b.create(j);
}
catch(NumberFormatException e1)
{
System.out.println("enter integers (positive) only");
}
break;
case 2: try
{
System.out.println("enter element to be element");
int j=Integer.parseInt(br.readLine());
int rm=b.delete(j);
if(rm==-1)
{
//System.out.println(rm);
throw new NullPointerException();
}
else
System.out.println("deleted element is"+rm);
}
catch(NullPointerException e)
{
System.out.println("element not found");
}
break;
case 3: b.preorder();
break;
case 4: b.inorder();
break;
case 5: b.postorder();
break;
case 6: break out;
default : System.out.println("enter correct choice");
}
}
}
}
i modified code now insertion,deletion and inorder working properly i m inserting only positive values so -1 indicate element not found i know its not a gud way to program the thing is preorder and postorder not working properly .. plz check once i think problem is at insertion of node.. plz tell wer i went wrong im not gud at english :(
the_unwanted wrote:
i modified code now insertion,deletion and inorder working properly i m inserting only positive values so -1 indicate element not found i know its not a gud way to program the thing is preorder and postorder not working properly .. plz check once i think problem is at insertion of node.. plz tell wer i went wrong im not gud at english :(
Why are you calling in() in your post and preorder methods? You make no sense.