Labels

algorithms (22) Design Patterns (20) java (19) linux (14) Snippet (13) service mix (6) soa (4)

Binary Search Tree

Binary Search Tree


import java.*;
import java.lang.*;
//node of the binary tree
class bnode {
String key;
bnode left;
bnode right;

bnode() {
key = null;
left = null;
right = null;
}

bnode(String key) {

this.key = key;
left = null;
right = null;
}
};
//binary tree
class btree {
bnode root;
btree() {
root = null;
}
//insert a node into the tree
void put(String key) {
bnode current = root;
bnode prev = current;
if (root == null) {
root = new bnode(key);
}
else {
boolean insert = false;
while (insert == false) {

prev = current;
if (key.compareTo(current.key) < 0) {
if (current.left == null) {
current.left = new bnode(key);
insert = true;
}
current = current.left;

}
else {
if (current.right == null) {
current.right = new bnode(key);
insert = true;
}
current = current.right;
}

}

}

}
//delete a node with a key
boolean delete(String key) {
boolean deleted = true;
bnode current = root;
bnode prev = current;
while (current != null) {
if (key.compareTo(current.key) > 0) {
prev = current;
current = current.right;
}
else if (key.compareTo(current.key) < 0) {
prev = current;
current = current.left;
}
else if (key.compareTo(current.key) == 0) {
deleted = false;
break;
}

}

if (check(current) == 0) {
if (current.key.compareTo(prev.key) > 0) {
prev.right = null;
}
else {
prev.left = null;
}
}
else if (check(current) == 1) {

if (current.key.compareTo(prev.key) > 0) {
if (current.left != null) {
prev.right = current.left;
}
else {
prev.right = current.right;
}
}
else {
if (current.left != null) {
prev.left = current.left;
}
else {
prev.left = current.right;
}
}
}
else if (check(current) == 2) {
bnode temp = inord(current);
if (current == root) {
root.key = temp.key;

}
else {
if (current.key.compareTo(prev.key) > 0) {
prev.right.key = temp.key;
}
else {
prev.left.key = temp.key;
}
}
}

return deleted;
}
//in order
bnode inord(bnode a) {
int t = 0;
bnode ret, prev = new bnode();
prev = a;
a = a.right;
while (a.left != null) {
prev = a;
a = a.left;
t = 1;
}
ret = a;
if (t == 0) {
prev.right = null;
}
else {
prev.left = null;
}
a = null;
return ret;
}
//check if a node is there
int check(bnode a) {
int ret;
if ( (a.left != null) && (a.right != null)) {
ret = 2;
}
else if ( (a.left == null) && (a.right == null)) {
ret = 0;
}
else {
ret = 1;
}
return ret;
}
//print the node
void printIn(bnode oot) {
if (oot.left != null) {
printIn(oot.left);
}
System.out.println("--------" + oot.key + "----------");
if (oot.right != null) {
printIn(oot.right);
}
}

public static void main(String[] args) {

btree a = new btree();
a.put("h");
a.put("g");
a.put("e");
a.put("d");
a.put("f");
a.put("c");
a.put("b");
a.put("a");
a.put("i");

a.printIn(a.root);

a.delete("h");
a.delete("e");

a.printIn(a.root);
}
}

No comments:

Post a Comment

Search 24 Bytes