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;
}
}