Saturday, September 20, 2014

Binary Search Trees - Insert, Find, Delete, Print Tree Operations [Java]

This program implements Insert, Find, Delete Node and Print operations on a Binary Search Tree. The inorder traversal of a Binary Search Tree yields the elements in ascending order.

This program doesn't use Father field in Node class. Here is another program that has Father field in nodes : Using Father Field BST

Code:

import java.util.Scanner;

public class BinarySearchTree {

    private class Node {

        int key;
        Node left, right;

        Node(int key) {
            this.key = key;
        }
    }

    private Node root;

    /* Adds an item to the BST */
    public void add(int a) {
        if (root == null) { root = new Node(a); } 
        else              { adder(a, root, null, false); }
    }

    private void adder(int a, Node node, Node parent, boolean isLeft) {

        if (node == null) {
            if (isLeft) { parent.left = new Node(a); } 
            else        { parent.right = new Node(a); }
            return;
        }

        if (a >= node.key) { adder(a, node.right, node, false); } 
        else               { adder(a, node.left, node, true); }
    }

    /* Checks whether an item is in the tree */
    public boolean isNode(int a) {
        if(root == null) return false;
        return nodeFinder(a, root);
    }

    private boolean nodeFinder(int a, Node node) {
        if (node.key == a) { return true; }

        if (a >= node.key) { return nodeFinder(a, node.right); } 
        else               { return nodeFinder(a, node.left); }
    }

    /* Deletes a node from the tree */
    public boolean delete(int a) {
        if (root == null) { return false; }
        
        //Target element is the root and either left or right subtree is empty
        if(root.key == a){
            if (root.left == null && root.right == null) 
                { root = null; return true;}
            else if(root.right == null)    //Root with only left subtree 
                { root = root.left; return true;}
            else if(root.left == null)                    //Root with right subtree only
                { root = root.right; return true;} 
        }
        return deleter(a, root, null); 
    }

    private boolean deleter(int a, Node node, Node parent) {  
        
        //Node is not present. Return false. 
        if(node == null){ return false; }
        
        //Node to be deleted is either a leaf or has only one child 
if (node.left != null && node.left.key == a) { if (node.left.left == null) { node.left = node.left.right; return true; } else if (node.left.right == null) { node.left = node.left.left; return true; } } else if (node.right != null && node.right.key == a) { if (node.right.left == null) { node.right = node.right.right; return true; } else if (node.right.right == null) { node.right = node.right.left; return true; } } //Node to be deleted has two children if (node.key == a) { Node smallestNodesParent = smallestNodesParent(node.right); if (smallestNodesParent.left != null) { node.key = smallestNodesParent.left.key; smallestNodesParent.left = smallestNodesParent.left.right; } else { node.key = smallestNodesParent.key; node.right = smallestNodesParent.right; } return true; } //Go left or right? if (a > node.key) { return deleter(a, node.right, node); } else if(a < node.key) { return deleter(a, node.left, node); } //Never gets Returned - One of the three conditions - equal, less or greater //return before reaching here. return false; } /*        returns the smallest nodes parent node, or if the node first passed to        this function has no left child, it just returns the node passed to it     */ private Node smallestNodesParent(Node node) { if (node.left != null) { if (node.left.left == null) { return node; } } else { return node; } return smallestNodesParent(node.left); } /*        Prints the tree contents - Inorder traversal -        Inorder traversal of a BST yields the items in        ascending order     */ public void printTree() { print(root); } private void print(Node node) { if (node == null) { if (root == null) { System.out.println("Tree is empty!"); } return; } print(node.left); System.out.print(node.key + " "); print(node.right); } public static void main(String[] args) { BinarySearchTree bst = new BinarySearchTree(); Scanner scan = new Scanner(System.in); //Display a Console Interface while (true) { System.out.println("\n1.- Add items\n" + "2.- Delete items\n" + "3.- Check items\n" + "4.- Print tree\n"); int choice = scan.nextInt(); int item; switch (choice) { case 1: item = scan.nextInt(); while (item != -999) { bst.add(item); item = scan.nextInt(); } bst.printTree(); break; case 2: item = scan.nextInt(); while (item != -999) { System.out.print("\nDeleting item "+item); if(bst.delete(item)){ System.out.print(": deleted!"); }else System.out.print(": does not exist!"); item = scan.nextInt(); } System.out.println(); bst.printTree(); break; case 3: item = scan.nextInt(); while (item != -999) { System.out.println(bst.isNode(item)); item = scan.nextInt(); } break; case 4: bst.printTree(); break; } } } }

Output: 

1.- Add items
2.- Delete items
3.- Check items
4.- Print tree

1
9 3 14 2 8 12 14 13 112 19 -999
2 3 8 9 12 13 14 14 19 112
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree

2
3 14 14 13 112 -999

Deleting item 3: deleted!
Deleting item 14: deleted!
Deleting item 14: deleted!
Deleting item 13: deleted!
Deleting item 112: deleted!
2 8 9 12 19
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree

2
8 9 12 19 2 -999

Deleting item 8: deleted!
Deleting item 9: deleted!
Deleting item 12: deleted!
Deleting item 19: deleted!
Deleting item 2: deleted!
Tree is empty!

1.- Add items
2.- Delete items
3.- Check items
4.- Print tree

No comments:

Post a Comment