Reading material

If you use the first edition of the textbook, follow the reading material in orange. If you use the second edition, follow the reading material in brown.

(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

Implementation of a general tree with a binary tree in pseudocode: PostScript and PDF

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.