permutation-tree/PermutationTree.java

/**
 * PermutationTree
 * 
 * This data structure builds a binary search tree of all the possible permutations of a given integer
 */

import java.util.Iterator;
import java.util.LinkedList;

public class PermutationTree {
    protected int count;
    protected Node root;
    
    // Constructors
    public PermutationTree() {
        count = 0;
    }
    public PermutationTree(int e) {
        count = 1;
        root = new Node(e);
        this.split(e);
    }
    
    // Getters
    public int getCount() {
        return count;
    }
    
    // Insert
    public void insert(int e) {
        count = 1;
        root = new Node(e);
        this.split(e);
    }
    private void split(int e) {
        int strlen = String.valueOf(e).length();
        for(int mod = 10; mod <= e; mod *= 10) {
            int temp = e;
            for(int c = 0; c < strlen; ++c) {
                this.addElement(temp % mod);
                temp /= 10;
            }
            --strlen;
        }
        // Since we've recreated the root at the bottom-right of the tree,
        // move the root pointer to root's left and delete the old root.
        root = root.getLeftChild();
    }
    private void addElement(int e) {
        Comparable key = e;
        Node element = new Node(e);
        Node current = root;
        boolean added = false;
        
        // Add the new node
        while(!added) {
            if(key.compareTo(current.getElement()) < 0) {
                if(current.getLeftChild() == null) {
                    current.setLeftChild(element);
                    current.getLeftChild().setParent(current);
                    added = true;
                } else {
                    current = current.getLeftChild();
                }
            } else {
                if(current.getRightChild() == null) {
                    current.setRightChild(element);
                    current.getRightChild().setParent(current);
                    added = true;
                } else {
                    current = current.getRightChild();
                }
            }
        }
        
        ++count;
    }
    
    // Find a specific element
    public Node find(int e) throws ElementNotFoundException {
        Node current = locate(e, root);
        if(current == null)
            throw new ElementNotFoundException("Permutation Tree");
        
        return current;
    }
    private Node locate(int e, Node next) {
        if(next == null)
            return null;
        if (next.getElement() == e)
            return next;
        Node temp = locate(e, next.getLeftChild());
        if(next == null)
            temp = locate(e, next.getRightChild());
        return temp;
    }
    
    // Define a way to print the tree
    public String toString() {
        String result = "";
        Node temp = root;
        int spaceCount = 0;
        if(temp.hasLeftChild()) {
            while(temp.hasLeftChild()) {
                spaceCount += 2;
                temp = temp.getLeftChild();
            }
        }
        if (spaceCount > 0) { for(int c = 0; c < spaceCount; ++c) { result += " "; } }
        result += root.getElement();
        result += "\n";
        if (spaceCount > 0) {
            for(int c = 0; c < spaceCount - 1; ++c) { result += " "; }
            result += "/";
            if (root.hasRightChild()) { result += " \\"; }
        }
        
        return result;
    }
}