Welcome to HBH! If you have tried to register and didn't get a verification email, please using the following link to resend the verification email.
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.