<![CDATA[
/**********************************************************************
Binary Search Tree
**********************************************************************/
class Node{
public String word;
public Node left;
public Node right;
public Node(String someWord ){
word=new String(someWord);
left=null;
right=null;
}
}
class BinTree{
private Node root;
private Node curNode, prevNode;
private void inorder(Node curRoot){
if (curRoot!=null){
inorder(curRoot.left);
System.out.println(curRoot.word);
inorder(curRoot.right);
}
}
private Node find(String someWord){
prevNode=root;
curNode=root;
while(curNode!=null){
if (someWord.compareTo(curNode.word)==0)
break;
prevNode=curNode;
if (someWord.compareTo(curNode.word) < 0)
curNode=curNode.left;
else curNode=curNode.right;
}
return curNode;
}
private Node findPred(Node someNode){
prevNode=someNode;
if (someNode.left==null) return null;
curNode=someNode.left;
while(curNode.right!=null){
prevNode=curNode;
curNode=curNode.right;
}
return curNode;
}
public BinTree(){
root=null;
}
public void display(){
System.out.println("---------------");
inorder(root);
System.out.println("---------------");
}
public int insert(String someWord){
// word already in tree:
if(find(someWord)!=null) return -1;
Node newNode=new Node(someWord);
// tree was empty, and word is the first:
if (root==null){
root=newNode;
return 1;
}
// word has to be inserted sometime after the root:
curNode=root;
prevNode=root;
while(curNode!=null){
prevNode=curNode;
if (someWord.compareTo(curNode.word)<0)
curNode=curNode.left;
else curNode=curNode.right;
}
if (someWord.compareTo(prevNode.word)<0)
prevNode.left=newNode;
else prevNode.right=newNode;
return 1;
}
public int delete(String someWord){
Node nodeToDelete=find(someWord);
Node nodesParent=prevNode;
// word not found:
if (nodeToDelete==null) return -1;
// word found in root node:
if (nodeToDelete==root) {
// root node with no children:
if ((root.left==null)&&(root.right==null)){
root=null;
return 1;
}
// root node with one child:
if ((root.left!=null)&&(root.right==null)){
root=root.left;
return 1;
}
if ((root.left==null)&&(root.right!=null)){
root=root.right;
return 1;
}
// root node with two children:
if ((root.left!=null)&&(root.right!=null)){
Node pred=findPred(nodeToDelete);
Node predsParent=prevNode;
// relinking predecessor's parent:
if (predsParent.left==pred)
predsParent.left=pred.left;
else predsParent.right=pred.left;
root.word=new String(pred.word);
// actually, the pred node is delinked
return 1;
}
}
// word found in a leaf node:
if ((nodeToDelete.left==null)&&
(nodeToDelete.right==null)){
if (nodesParent.left==nodeToDelete)
nodesParent.left=null;
else nodesParent.right=null;
return 1;
}
// word found in node with only one child:
if ((nodeToDelete.left!=null)&&
(nodeToDelete.right==null)) {
if (nodesParent.left==nodeToDelete)
nodesParent.left=nodeToDelete.left;
else nodesParent.right=nodeToDelete.left;
return 1;
}
if ((nodeToDelete.left==null)&&
(nodeToDelete.right!=null)) {
if (nodesParent.left==nodeToDelete)
nodesParent.left=nodeToDelete.right;
else nodesParent.right=nodeToDelete.right;
return 1;
}
// word found in node with 2 children:
if ((nodeToDelete.left!=null)&&
(nodeToDelete.right!=null)){
Node pred=findPred(nodeToDelete);
Node predsParent=prevNode;
// relinking predecessor's parent:
if (predsParent.left==pred)
predsParent.left=pred.left;
else predsParent.right=pred.left;
nodeToDelete.word=new String(pred.word);
// actually,the pred node is delinked
return 1;
}
return 0;
}
/* Test tools:
private Node node1,node2,node11,node21,node22,node212;
public void genTree(){
root=new Node("jokes");
node1=new Node("improperly");
node2=new Node("told");
node11=new Node("get");
node21=new Node("often");
node22=new Node("uncomfortable");
node212=new Node("silences");
root.left=node1;
root.right=node2;
node1.left=node11;
node2.left=node21;
node2.right=node22;
node21.right=node212;
}
*/
}
class BinTreeAp {
public static void main(String args[]){
BinTree BT=new BinTree();
BT.insert("hello");
BT.insert("there");
BT.insert("this");
BT.insert("is");
BT.insert("a");
BT.insert("test");
BT.insert("for");
BT.insert("a");
BT.insert("binary");
BT.insert("search");
BT.insert("tree");
BT.display();
BT.delete("hello");
BT.delete("there");
BT.display();
}
}
]]>