package Tree;

/**
 * 二叉搜索树
 * @author Administrator
 *
 */
public class Tree {
	public node root;
	
	public Tree(int i,double f) {
		this.root = new node(i,f);
	}
	
	/**
	 * 查找
	 * @param key
	 * @return
	 */
	public node find(int key) {
		node current = this.root;
		
		while(current.iData != key) {
			if(key < current.iData) {
				current = current.leftNode;
			}else {
				current = current.rightNode;
			}
			
			if(current == null) {
				return null;
			}
		}
		
		return current;
	}
	
	/**
	 * 插入数据
	 * @param i
	 * @param f
	 */
	public void insert(int i,double f) {
		node newNode = new node(i,f);
		
		if(this.root == null) {
			this.root = newNode;
		}else {
			node current = this.root;
			node parent;
			
			while(true) {
				parent = current;
				if(i < current.iData) {
					current = current.leftNode;
					if(current == null) {
						parent.leftNode = newNode;
						return;
					}
				}else {
					current = current.rightNode;
					if(current == null) {
						parent.rightNode = newNode;
						return;
					}
				}
			}
		}
	}
	
	/**
	 * 中序遍历
	 * @param localRoot
	 */
	public void inOrder(node localRoot) {
		if(localRoot != null) {
			inOrder(localRoot.leftNode);
			System.out.println(localRoot.iData);
			inOrder(localRoot.rightNode);
		}
	}

	/**
	 * 返回最小的值
	 * @return
	 */
	public node minimum() {
		node current,last;
		current = this.root;
		last = null;
		
		while(current != null) {
			last = current;
			current = current.leftNode;
		}
		
		return last;
	}
	
	/**
	 * 二叉搜索树的最大值
	 * @return
	 */
	public node maximun() {
		node current,last;
		current = this.root;
		last = null;
		
		while(current != null) {
			last = current;
			current = current.rightNode;
		}
		
		return last;
	}
	
	/**
	 * 删除拥有两个子节点的节点，要找到当前节点的中序后继节点,如果不是当前节点的右子节点那么还得反转下树
	 * @param delNode
	 * @return
	 */
	private node getSuccessor(node delNode) {
		node successorParent = delNode;
		node successor = delNode;
		node current = delNode.rightNode;
		
		while(current != null) {
			successorParent = successor;
			successor = current;
			current = current.leftNode;
		}
		
		if(successor != delNode.rightNode) {
			successorParent.leftNode = successor.rightNode;
			successor.rightNode = delNode.rightNode;
		}
		
		return successor;
	}
	
	/**
	 * 删除一个节点
	 * @return
	 */
	public boolean delete(int key) {
		node current = this.root;
		node parent = this.root;
		boolean isLeftChild = true;
		
		//找到要删除的节点
		while(current.iData != key) {
			parent = current;
			if(key < current.iData) {
				isLeftChild = true;
				current = current.leftNode;
			}else {
				isLeftChild = false;
				current = current.rightNode;
			}
			
			if(current == null) {
				return false;
			}
		}
		
		//没有子节点的情况下
		if(current.leftNode == null && current.rightNode == null) {
			
			if(current == this.root) {
				//根节点
				this.root = null;
			}else {
				//叶子结点
				if(isLeftChild) {
					parent.leftNode = null;
				}else {
					parent.rightNode = null;
				}
			}
		}else if(current.rightNode == null) {
			//只有一个节点的情况下
			if(current == this.root) {
				//当前结点是根结点
				this.root = this.root.leftNode;
			}else if(isLeftChild) {
				parent.leftNode = current.leftNode;
			}else {
				parent.rightNode = current.leftNode;
			}
		}else if(current.leftNode == null) {
			//只有一个节点的情况下
			if(current == this.root) {
				//当前结点是根结点
				this.root = this.root.rightNode;
			}else if(isLeftChild) {
				parent.leftNode = current.rightNode;
			}else {
				parent.rightNode = current.rightNode;
			}
		}else {
			//两个子节点的情况下
			node successor = this.getSuccessor(current);
			if(current == this.root) {
				root = successor;
			}else if(isLeftChild) {
				parent.leftNode = successor;
			}else {
				parent.rightNode = successor;
			}
			
			successor.leftNode = current.leftNode;
		}
		
		return true;
	}
}