2015-05-01 BST toString()

posted May 1, 2015, 9:20 AM by Samuel Konstantinovich   [ updated May 1, 2015, 9:26 AM ]
/**
* stolen from: Dennis Yatunin
* (no not really stolen from, donated by)
*/

public int getHeight(){
		return getHeight(root);
}

private int getHeight(BSTreeNode<T> r ){
		if(r == null){
				return 0;
		}else{
				//System.out.println("recursion height");
				return 1 + Math.max(getHeight(r.getLeft()),
					            getHeight(r.getRight()));
		}
}

private int maxLength() {
		// returns the minimum number of characters required
		// to print the data from any node in the tree
		if (root == null)
				return 0;
		return maxLength(root);
}

private int maxLength(BSTreeNode<T> curr) {
		int max = curr.toString().length();
		int temp;
		if (curr.getLeft() != null) {
				temp = maxLength(curr.getLeft());
				if (temp > max)
						max = temp;
		}
		if (curr.getRight() != null) {
				temp = maxLength(curr.getRight());
				if (temp > max)
						max = temp;
		}
		return max;
}

private String spaces(double n) {
		// returns a String of n spaces
		String result = "";
		for (int i = 0; i < n; i++)
				result += " ";
		return result;
}

/*
	getLevel will produce a String for each level of the tree.
	The resulting Strings will look like this:

	._______________________________
	._______________._______________
	._______._______._______._______
	.___.___.___.___.___.___.___.___
	._._._._._._._._._._._._._._._._

	toString will combine those Strings and provide an output that
	will look like this:

	_______________.
	_______._______________.
	___._______._______._______.
	_.___.___.___.___.___.___.___.
	._._._._._._._._._._._._._._._.
	In these diagrams, each dot represents wordLength characters,
	each underscore represents wordLength spaces, and, for any nodes
	that are null, the dots will be "replaced" by underscores.
*/

private String getLevel(BSTreeNode<T> curr, int currLevel, int targetLevel, int height, int wordLength) {
		if (currLevel == 1){
			return curr.toString() + 
                               spaces(wordLength - curr.toString().length()) +
			       spaces(wordLength * 
                                      Math.pow(2, height - targetLevel + 1) - 
                                      wordLength);
		}
		String result = "";
		if (curr.getLeft() != null){
			result += getLevel(curr.getLeft(), currLevel - 1, targetLevel, height, wordLength);
		}else{
			result += spaces(wordLength * Math.pow(2, height - targetLevel + currLevel - 1));
		}
		if (curr.getRight() != null){
			result += getLevel(curr.getRight(), currLevel - 1, targetLevel, height, wordLength);
		}else{ 
			result += spaces(wordLength * Math.pow(2, height - targetLevel + currLevel - 1));
		}
		return result;
}
		
public String toString() {
		if (root == null)
				return "";
		String result = "";
		int height = getHeight();
		int wordLength = maxLength();
		// add the every level of the tree except the last one
		for (int level = 1; level < height; level++){
			// remove extra spaces from the end of each level's String to prevent lines from
			// getting unnecessarily long and add spaces to the front of each level's String
			// to keep everything centered
			result += spaces(wordLength * Math.pow(2, height - level) - wordLength) +
				getLevel(root, level, level, height, wordLength).replaceFirst("\\s+$", "") +
				"\n";
		}
		// now add the last level (level = height)
		result += getLevel(root, height, height, height, wordLength).replaceFirst("\\s+$", "");
				
		return result;
}
Comments