Complete binary search tree in Java



/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package trees;

/**
 *
 * @author wijebandara
 */
public class BinarySearchTrees {

    private NodeBST head;

    /**
     *
     * @param n
     */
    public void insert(int n) {
        if (head != null) {
            NodeBST hold = head;
            while (true) {
                if (hold.data > n) {
                    if (hold.left == null) {
                        hold.left = new NodeBST(n, hold);
                        break;
                    } else {
                        hold = hold.left;
                    }
                } else {
                    if (hold.right == null) {
                        hold.right = new NodeBST(n, hold);
                        break;
                    } else {
                        hold = hold.right;
                    }
                }
            }
        } else {
            head = new NodeBST(n);
        }

    }

    /**
     *
     */
    public void showPostOrder() {
        if (head != null) {
            showPostOrder(head);
            System.out.println();
        } else {
            System.out.println("NULL");
        }
    }

    private void showPostOrder(NodeBST hold) {
        if (hold.right != null) {
            showPostOrder(hold.right);
        }

        if (hold.left != null) {
            showPostOrder(hold.left);
        }

        System.out.print(hold.data + " ");
    }

    /**
     *
     */
    public void showPreOrder() {
        if (head != null) {
            showPreOrder(head);
            System.out.println();
        } else {
            System.out.println("NULL");
        }

    }

    private void showPreOrder(NodeBST hold) {
        System.out.print(hold.data + " ");

        if (hold.left != null) {
            showPreOrder(hold.left);
        }

        if (hold.right != null) {
            showPreOrder(hold.right);
        }
    }

    /**
     *
     */
    public void showInOrder() {
        if (head != null) {
            showInOrder(head);
            System.out.println();
        } else {
            System.out.println("NULL");
        }
    }

    private void showInOrder(NodeBST hold) {
        if (hold.left != null) {
            showInOrder(hold.left);
        }

        System.out.print(hold.data + " ");

        if (hold.right != null) {
            showInOrder(hold.right);
        }
    }

    /**
     *
     * @param x
     * @return
     */
    public boolean search(int x) {
        NodeBST hold = head;

        while (true) {
            if (hold.data == x) {
                return true;
            } else if (hold.data > x) {
                if (hold.left != null) {
                    hold = hold.left;
                } else {
                    return false;
                }
            } else {
                if (hold.right != null) {
                    hold = hold.right;
                } else {
                    return false;
                }
            }
        }
    }

    private NodeBST getNode(int x) {
        NodeBST hold = head;

        while (true) {
            if (hold.data == x) {
                return hold;
            } else if (hold.data > x) {
                if (hold.left != null) {
                    hold = hold.left;
                } else {
                    return null;
                }
            } else {
                if (hold.right != null) {
                    hold = hold.right;
                } else {
                    return null;
                }
            }
        }
    }

    /**
     *
     * @param x
     * @return
     */
    public boolean delete(int x) {
        NodeBST hold = getNode(x);

        if (hold == null) {
            return false;
        }

        if (hold.left == null) {
            transplant(hold, hold.right);
        } else if (hold.right == null) {
            transplant(hold, hold.left);
        } else {
            NodeBST min = minimumNode(hold.right);
            if (!min.parent.equals(hold)) {
                transplant(hold, hold.right);
                hold.right = min.right;
                hold.right.parent = hold;

            } else {
                transplant(min, hold);
                hold.left = min.left;
                hold.left.parent = hold;
            }
        }
        return false;

    }

    private void transplant(NodeBST u, NodeBST v) {
        if (u.parent == null) {
            this.head = v;
        } else if (u == u.parent.left) {
            u.parent.left = v;
        } else {
            u.parent.right = v;
        }

        if (v != null) {
            v.parent = u.parent;
        }
    }

    /**
     *
     * @return
     */
    public int minimum() {
        NodeBST hold = head;

        while (hold.left != null) {
            hold = hold.left;
        }
        return hold.data;
    }

    private NodeBST minimumNode(NodeBST x) {
        NodeBST hold = x;

        while (hold.left != null) {
            hold = hold.left;
        }
        return hold;
    }

    /**
     *
     * @return
     */
    public int maximum() {
        NodeBST hold = head;

        while (hold.right != null) {
            hold = hold.right;
        }
        return hold.data;
    }

    private NodeBST maximum_node(NodeBST x) {
        NodeBST hold = x;

        while (hold.right != null) {
            hold = hold.right;
        }
        return hold;
    }

    private NodeBST successor_node(NodeBST x) {
        if (x.right != null) {
            return minimumNode(x.right);
        }
        NodeBST hold = x.parent;

        while (hold != null && x.equals(hold.right)) {

            x = hold;
            hold = hold.parent;
        }
        return hold;
    }

    /**
     *
     * @param value
     * @return
     * @throws Exception
     */
    public int successor(int value) throws Exception {

        NodeBST x = getNode(value);

        if (x == null) {
            return x.data;
        }

        if (x.right != null) {
            return minimumNode(x.right).data;
        }
        NodeBST hold = x.parent;

        while (hold != null && x.equals(hold.right)) {

            x = hold;
            hold = hold.parent;
        }
        return hold.data;
    }

    private NodeBST predecessor_node(NodeBST x) {

        if (x.left != null) {
            return maximum_node(x.left);
        }
        NodeBST hold = x.parent;

        while (hold != null && x.equals(hold.left)) {

            x = hold;
            hold = hold.parent;
        }
        return hold;
    }

    /**
     *
     * @param value
     * @return
     * @throws Exception
     */
    public int predecessor_node(int value) throws Exception {

        NodeBST x = getNode(value);

        if (x == null) {
            return x.data;
        }
        if (x.left != null) {
            return maximum_node(x.left).data;
        }
        NodeBST hold = x.parent;

        while (hold != null && x.equals(hold.left)) {

            x = hold;
            hold = hold.parent;
        }
        return hold.data;
    }

}

class NodeBST {

    int data;
    NodeBST left;
    NodeBST right;
    NodeBST parent;

    NodeBST(int data) {
        this.data = data;
        left = null;
        right = null;
        parent = null;
    }

    public NodeBST(int data, NodeBST parent) {
        this.data = data;
        this.parent = parent;
    }

    NodeBST() {
        left = null;
        right = null;
        parent = null;
    }

}


Advertisements

2 thoughts on “Complete binary search tree in Java

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s