Wednesday, December 8, 2010

Generic Binary Search Tree

Tree Node
public class TreeNode<T extends Comparable<T>> {
    TreeNode<T> leftNode;
    TreeNode<T> rightNode;
    T data;
    public TreeNode(T nodeData) {
        data = nodeData;
        leftNode = rightNode = null;
    }
    public void insert(T insertValue) {
        if (insertValue.compareTo(data) < 0) {
            if (leftNode == null) {
                leftNode = new TreeNode<T>(insertValue);
            } else {
                leftNode.insert(insertValue);
            }
        }else if (insertValue.compareTo(data) > 0) {
            if (rightNode == null) {
                rightNode = new TreeNode<T>(insertValue);
            } else {
                rightNode.insert(insertValue);
            }
        }
    }
}

Binary Search Tree

public class Tree<T extends Comparable<T>>      {
    private TreeNode<T> root;
    public Tree() {
        root = null;
    }
    public void insertNode(T insertValue) {
        if (root == null) {
            root = new TreeNode<T>(insertValue);
        } else {
            root.insert(insertValue);
        }
    }
    public void preOrderTraversal() {
        preOrderHelper(root);
    }
    private void preOrderHelper(TreeNode<T> node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrderHelper(node.leftNode);
        preOrderHelper(node.rightNode);
    }
    public void inOrderTraversal() {
        inOrderHelper(root);
    }
    private void inOrderHelper(TreeNode<T> node) {
        if (node == null) {
            return;
        }
        inOrderHelper(node.leftNode);
        System.out.print(node.data + " ");
        inOrderHelper(node.rightNode);
    }
    public void postOrderTraversal() {
        postOrderHelper(root);
    }
    private void postOrderHelper(TreeNode<T> node) {
        if (node == null) {
            return;
        }
        postOrderHelper(node.leftNode);
        postOrderHelper(node.rightNode);
        System.out.print(node.data + " ");
    }
}

No comments:

Post a Comment