CIS 260 BST.java

Code

/*
   BST.java
   CIS 260
   Dave Klick
   4/4/09

   Implementation of a binary tree class using generics.
*/

class BST<T extends Comparable<? super T>> {
    private class Node {
        T data;
        Node left, right;
        public Node(T val) { data = val; }
        T getData() { return data; }
        public int compareTo(Node n) { return data.compareTo(n.data); }
        public String toString() { return data.toString(); }
    }
   
    private Node root = null;
    public BST() {}

    public boolean find(T val) {
        Node cur = root;
        while (cur != null) {
            int comp = val.compareTo(cur.data);
            if (comp < 0) cur = cur.left;
            else if (comp > 0) cur = cur.right;
            else return true;
        }
        return false;
    }

    public boolean insert(T val) {
        Node parent, cur;
        Node n = new Node(val);
        if (root == null) root = n;
        else {
            cur = root;
            while (true) {
                parent = cur;
                int comp = val.compareTo(cur.data);
                if (comp < 0) {
                    cur = cur.left;
                    if (cur == null) { parent.left = n; break; }
                } else if (comp > 0) {
                    cur = cur.right;
                    if (cur == null) { parent.right = n; break; }
                } else { 
                    // Here is where you would increment the count
                    // if utilizing a count for duplicates.
                    // No duplicates allowed in this case.
                    return false;
                }
            }
        }
        return true;
    }

    public void inorder() { inorder(root); System.out.println(); }

    public void inorder(Node node) {
        if (node != null) {
            inorder(node.left);
            System.out.println(node);
            inorder(node.right);
        }
    }

    public void preorder() { preorder(root); System.out.println(); }

    public void preorder(Node node) {
        if (node != null) {
            System.out.println(node);
            preorder(node.left);
            preorder(node.right);
        }
    }

    public void postorder() { postorder(root); System.out.println(); }

    public void postorder(Node node) {
        if (node != null) {
            postorder(node.left);
            postorder(node.right);
            System.out.println(node);
        }
    }

    public boolean delete(T val) {
        // escape quickly if tree is empty
        if (root == null) return false;
   
        Node cur = root;
        Node parent = root;

        boolean leftChild = true;

        // search for node to delete
        while (val.compareTo(cur.data) != 0) {
            parent = cur;
            if (val.compareTo(cur.data) < 0) {
                cur = cur.left;
                leftChild = true;
            } else {
                cur = cur.right;
                leftChild = false;
            }   
            if (cur == null) return false;
        }

        // Here is where you would check the count if utilizing
        // a count for duplicates. The count would be decremented
        // if it was greater than 1, otherwise the node would be
        // deleted as usual. In this case, no duplicates are
        // allowed.
      
        // check for delete with no children
        if ((cur.left == null) && (cur.right == null)) {
            if (cur == root) root = null;
            else if (leftChild) parent.left = null;
            else parent.right = null;
        }
        // check for delete with one child
        else if (cur.right == null) {
            if (cur == root) root = cur.left;
            else if (leftChild) parent.left = cur.left;
            else parent.right = cur.left;
        }
        else if (cur.left == null) {
            if (cur == root) root = cur.right;
            else if (leftChild) parent.left = cur.right;
            else parent.right = cur.right;
        }

        // must be delete with two children
        else {

            // get successor to delete node
            Node delNode = cur;
            Node suc = cur;
            Node sucParent = cur;

            Node tmp = delNode.right;
            while (tmp != null) {
                sucParent = suc;
                suc = tmp;
                tmp = tmp.left;
            }
            if (suc != delNode.right) {
                sucParent.left = suc.right;
                suc.right = delNode.right;
            }

            if (cur == root) root = suc;
            else if (leftChild) parent.left = suc;
            else parent.right = suc;

            suc.left = cur.left;
        }
        return true;
    }
}