Reading material

(1st) pages 178-180 (Section 5.4.1), pages 186-187 (Section 5.4.4)

(2nd) pages 263-265 (Section 6.4.1), pages 272-271 (Section 6.4.4)

Additional material

Implementing a general tree with a linked structure

private int size;   // size of this tree
private TNode root; // root of this tree

/**
 * Constructs a tree with a single node containing no element.
 */
public LinkedTree() 
{
    size = 1;
    root = new TNode(null, null, new Vector());
}

/**
 * Constructs a tree consisting of a root containing the specified
 * element and the specified collection of trees as subtrees.
 *
 * @param element The element of the root.
 * @param subtrees The collection of subtrees of the root.
 */
public LinkedTree(Object element, Iterator subtrees) 
{
    size = 1;
    Vector children = new Vector();
    root = new TNode(element, null, children);
    while (subtrees.hasNext()) 
    {
        LinkedTree tree = (LinkedTree) subtrees.next();
        size += tree.size();
        TNode node = (TNode) tree.root();
        node.setParent(root);
        children.addElement(node);
    }
}

/**
 * Returns the children of the specified position.
 *
 * @param position The position the children of which are to be returned.
 * @return The children of the specified position.
 */
public Iterator children(Position position) 
{
    TNode node = (TNode) position;
    return node.getChildren().iterator();
}

/**
 * Returns the positions of this tree.
 *
 * @return The positions of this tree.
 */
public Iterator positions() 
{
    Vector positions = new Vector();
    preorder(root, positions);
    return positions.iterator();
}

/**
 * The positions of the subtree rooted at the specified position are
 * added to the specified vector.
 *
 * @param node Root of the subtree.
 * @param vector Collection of positions to be added to.
 */
private void preorder(TNode node, Vector vector) 
{
    if (node == null) 
    {
        return;
    } 
    else 
    {
        vector.addElement(node);
        Iterator iterator = node.getChildren.iterator();
        while (iterator.hasNext()) 
        {
            preorder((TNode) iterator.next(), vector);
        }
        return;
    }
}

Question

Give the pseudocode for removeAboveExternal in the implementation of a binary tree with an array.