Labels

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

Binary Search Tree in Java

public class BinarySearchTree<Key extends Comparable<Key>, Value> {
    Node<Key, Value> root;
    public void addNode(Key key, Value val) {
        addNode(this.root, key, val);
    }
    public Node addNode(Node<Key, Value> node, Key key, Value value) {
        if (node == null) {
            Node<Key, Value> nodeTemp = new Node<Key, Value>(key, value);
            if (this.root == null) {
                this.root = nodeTemp;
            }
            return nodeTemp;
        }
        int compareTo = key.compareTo((Key) node.keyT);
        if (compareTo < 0) {
            node.left = addNode(node.left, key, value);
        } else if (compareTo > 0) {
            node.right = addNode(node.right, key, value);
        } else {
            node.keyT = key;
            node.value = value;
        }
        return node;
    }
    Node<Key, Value> getNode(Key key) {
        Node<Key, Value> node = this.root;
        while (node != null) {
            int cmp = key.compareTo((Key) node.keyT);
            if (cmp < 0) {
                node = node.left;
            } else if (cmp > 0) {
                node = node.right;
            } else if (cmp == 0) {
                return node;
            }
        }
        return null;
    }
    private static void printInOrder(Node<Integer, String> node) {
        if (node == null) {
            return;
        }
        printInOrder(node.left);
        System.out.println(node.value);
        printInOrder(node.right);
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        BinarySearchTree<Integer, String> bst = new BinarySearchTree<Integer, String>();
        bst.addNode(new Integer(7), "seven");
        bst.addNode(new Integer(8), "eight");
        bst.addNode(new Integer(9), "nine");
        bst.addNode(new Integer(5), "five");
        bst.addNode(new Integer(6), "six");
        bst.addNode(new Integer(4), "four");
        bst.addNode(new Integer(3), "three");
        bst.addNode(new Integer(10), "ten");
        bst.addNode(new Integer(2), "two");
        bst.addNode(new Integer(1), "one");
        printInOrder(bst.root);
    }
}
class Node<T extends Comparable<T>, Value> {
    T keyT;
    Value value;
    Node<T, Value> left;
    Node<T, Value> right;
    Node(T key, Value val) {
        this.keyT = key;
        this.value = val;
    }
}

1 comment:

Search 24 Bytes

Loading...