ProperLinkedBinaryTree.java
import dsa.iface.IPosition;
import dsa.impl.AbstractBinaryTree;

public class ProperLinkedBinaryTree<T> extends AbstractBinaryTree<T> {

	/**
	 * Constructor - create an empty tree
	 */
	public ProperLinkedBinaryTree() {
		// Part 1
		root = newPosition(null, null);  // root an external node
		size = 1;
	}

	/**
	 * Expand an external node - Store a value in the external node - Create two
	 * external nodes as children, making {@code n} an internal node
	 *
	 * @param p
	 *            The position (node) to expand. An exception will be thrown if it is not
	 *            external.
	 * @param e
	 *            The element to be stored in position {@code p}.
	 */
	public void expandExternal(IPosition<T> p, T e) {
		// Part 2
		BTPosition nodeP = (BTPosition) p;

		// if p is internal node
		if (isInternal(p)) {
			throw new RuntimeException("Position is not external");
		}

		replace(p, e);  // 将e添加到这个节点中

		// 新建两个外部节点,将原有的节点扩展
		BTPosition left = newPosition(null, nodeP);
		BTPosition right = newPosition(null, nodeP);

		nodeP.left = left;
		nodeP.right = right;

		size = size + 2;

	}


	/**
	 * Remove a node from the tree
	 *
	 * @param p
	 *            The position (node )to be removed. An exception will be thrown if it cannot
	 *            be removed (i.e. if it has two internal children).
	 * @return The element that was stored in the removed position.
	 */
	public T remove(IPosition<T> p) {
		// Part 3
		// P节点有两个内部节点,无法删除
		if (isInternal(left(p)) && isInternal(right(p))) {
			throw new RuntimeException("Position has two internal children");
		}

		// 转为BT型,因为有上下连接关系,LEFT,RIGHT,PARENT
		BTPosition node = (BTPosition) p;
		BTPosition parent = node.parent;
		T temp = node.element();

		if (isRoot(node)) {               // 若删除根节点,则需要调整Root指向
			if(isInternal(node.left)) {   // 判断树的结构。将Root指向非空节点
				root = node.left;
				node.left.parent = null;
			} else {
				root = node.right;
				node.right.parent = null;
			}
		} else {                          // 删除非根节点。需要判断,被删除节点与父节点的位置关系。
			if(isInternal(node.left)) {   // 以此决定父节点连接新子节点的位置关系
				BTPosition child = node.left;
				child.parent = parent;
				if(parent.left.equals(node)) {
					parent.left = child;
				} else {
					parent.right = child;
				}
			} else {
				BTPosition child = node.right;
				child.parent = parent;
				if(parent.left.equals(node)) {
					parent.left = child;
				} else {
					parent.right = child;
				}
			}
		}

		size--;
		return temp;
	}



}