linkedbinarytree.java

真的很麻烦也

public class LinkedBinaryTree implements BinaryTree {
  private Position root; // reference to the root
  private int size; // number of nodes
  public LinkedBinaryTree() {
    root = new BTNode(null,null,null,null);
    size = 1;
  }
  
  public int size() { return size; }
  public boolean isEmpty() { return (size==0); }
  public boolean isInternal(Position v) {
    return (((BTNode) v).getLeft()!=null && ((BTNode) v).getRight()!=null);
  }
  public boolean isExternal(Position v) {
    return (((BTNode) v).getLeft()==null && ((BTNode) v).getRight()==null);
  }
  public boolean isRoot(Position v) { return (v==root()); }

  public Position root() { return root; }
//  public PositionIterator positions() {  
//    Position[] positions = new Position[size()];
//    inorderPositions(root(), positions, 0);
//    return new ArrayPositionIterator(positions);
//  }
  public Position leftChild(Position v) { return ((BTNode) v).getLeft(); }
  public Position rightChild(Position v) { return ((BTNode) v).getRight(); }
  public Position sibling(Position v) {
    Position p = parent(v);
    Position lc = leftChild(p);
    if (v == lc)
      return rightChild(p);
    else
      return lc;
  }
  public Position parent(Position v) { return ((BTNode) v).getParent(); }
  public Object  replaceElement(Position v, Object o) {
    Object temp = ((BTNode) v).element();
    ((BTNode) v).setElement(o);
    return temp;
  }
  public void swapElements(Position v, Position w) {
    Object temp = w.element();
    ((BTNode) w).setElement(v.element());
    ((BTNode) v).setElement(temp);	
  }
  public void expandExternal(Position v) {
    if (isExternal(v)) {
      ((BTNode) v).setLeft(new BTNode(null,(BTNode) v, null, null));
      ((BTNode) v).setRight(new BTNode(null,(BTNode) v, null, null));
      size += 2;
    }
  }
  public void removeAboveExternal(Position v) {
    if (isExternal(v)) {
      BTNode p = (BTNode) parent(v);
      BTNode s = (BTNode) sibling(v);
      if (isRoot(p)) {
        s.setParent(null);
        root = s;
      }
      else {
        BTNode g = (BTNode) parent(p);
        if (p == leftChild(g))
          g.setLeft(s);
        else
          g.setRight(s);
        s.setParent(g);
      }
      size -= 2;
    }
  }
}