BSTFaceIndex.java

// 与同学写的二叉搜索树（Binary Search Tree), 只是一部分用来做一个类似facebook的terminal程序。课程期末项目。

public class BSTFaceIndex {
	
	Node root; //represents the first Profile in the BST

	//constructor to initialize BST 	
	public BSTFaceIndex() {
		root = null; 
	}
	
		
	public class Node {
		String key; // string to represent the full name of the person
		ProfileInfo data; // data is the status and full name of a person
		Node left, right; // place next person in BST according to alphabetical order 
		
		public Node(ProfileInfo data) {
			this.key = data.fullName; //key = full name 
			this.data = data; 
			}
	}


	public void insert(ProfileInfo data) {
		// same as recursive put method from BST 
		root = insert(root, data);
	}
	
	private Node insert(Node x, ProfileInfo data) { 
		if ( x == null) 
			return new Node(data); 
		int cmp = data.fullName.compareToIgnoreCase(x.key); 
		
		if ( cmp < 0) { 
			x.left = insert(x.left, data);
		}
		if (cmp > 0) { 
			x.right = insert(x.right, data); 
		}
			return x; 
	}
	
	public ProfileInfo findPrefix(String prefix) {// different from get
		
		String newprefix = prefix.substring(0, prefix.length()-1); 
		return findPrefix(root, newprefix);
	  }
	
	private ProfileInfo findPrefix(Node x, String prefix){ 
		if (x== null){
			return null;
		}//compareToIgnoreCase is unicode based comparison not length based
		int cmp = prefix.compareToIgnoreCase(x.key.substring(0, prefix.length()));
		if (cmp < 0) { //Ex Karen.ctic.Tom = positive therefore to the left. 
			return findPrefix(x.left, prefix); 
		}
		if (cmp > 0) { //Ex Sam.ctic.Tom = Negative therefore to the right (Tom - Sam = neg) 
			return findPrefix(x.right, prefix); 
		}
		else
			return x.data; 
	}
	
	public ProfileInfo findExact(String exactName){ //exactName is the full name of a person 
		return findExact(root, exactName); 
	}

	public ProfileInfo findExact(Node x, String exactName) {
		if ( x == null) { 
			return null; 
		}
		int cmp = exactName.compareToIgnoreCase(x.key); 
		if (cmp < 0) {
			return findExact(x.left, exactName); 
		}
		if (cmp > 0) {
			return findExact(x.right, exactName); 
		}
		else
		return x.data; 
	}
}