Outline of Class 42: Implementing Trees, Continued

Miscellaneous

• Don't forget Friday's talk at 2:15 on chaos theory.
• On Monday, November 24, at 7:00pm in ARH 224 there will be two short talks on CS-related summer internships: one on engineering Java applets, the other on a FreeNet project.
• Today's class has the special number of 42.
• Assignment nine is now ready. It is due after Thanksgiving break, but you should begin it before Thanksgiving break.
• Start reading chapter 12 of Bailey.

Traversing Trees

• Each of our iterators returns the elements of the tree in a slightly different order.
• A traversal of a tree is a policy for visiting the nodes of the tree. There are a variety of traversal strategies.
• Traversal strategies can be organized along three dimensions:
  • Primary direction (down vs. across)
  • When is a node visited with respect to children?
  • In what order are the children visisted?
• The two primary directions are depth-first and breadth-first
  • In a depth-first traversal, you complete each subtree before going on to the next subtree.
  • In a breadth-first traversal, you complete each level before going on to the next level.
• The current node may be visited before, after, or between the children.
  • preorder: before
  • postorder: after
  • inorder: in between (for binary trees)
• Sometimes this ordering is limited to depth-first traversals.
• The children may be visited left-to-right or right-to-left.
• Consider the tree

      A
     / \
    B   C
   / \  |
  D   E F
  

• In a depth-first, preorder, left-to-right traversal, we would visit the nodes in the order A, B, D, E, C, F.
• In a depth-first, postorder, left-to-right traversal, we would visit the nodes in the order: D, E, B, F, C, A.
• In a depth-first, inorder, left-to-right traversal, we would visit the nodes in the order D, B, E, A, F, C (the order of the last two is vague as inorder is only defined for binary trees).
• In a depth-first, preorder, right-to-left traversal, we would visit the nodes in the order A, C, F, B, D, E.
• In a breadth-first, preorder, left-to-right traversal, we would visit the nodes in the order A, B, C, D, E, F.
• In a breadth-first, postorder, left-to-right traversal, we would visit the nodes in the order D, E, F, B, C, A.

Adding a Parent Link

• If we wanted to support parent() and root() methods like those Bailey recommends, it becomes necessary for nodes to include links to parents, and not just children.
• The addition of this link can significantly complicate our methods, as each time we change a child link, we'll also need to worry about changing a parent link.
• As we'll see later, providing a parent() method may require some serious thought as to precise meaning.
• We would begin by adding the parent field.

  /** The unique parent of the current node. Set to null for the root. */
  TreeNode parent;
  

• Each of the constructors would need to set this field for the current node. Initially, we'll assume that any newly constructred node is the root of a tree.

    parent = null;
  

• Most constructors will also need to set the parent field for each of the newly added children. We'll do this with a helper function. Note that we need to check whether or not our children are null.

  /**
     Set the parent link of all of our children.
     pre: The children array is initialized.
     post: Each child in that array considers the current node
           to be its parent.
   */
  private void claimPaternity() {
    for(int i = 0; i < children.length; ++i) {
      if (children[i] != null) {
        children[i].parent = this;
      }
    } // for
  } // claimPaternity
  

• setChild() will clearly need to be modified to make this same link to the parent (and unlinking for the old child).

  public void setChild(int childnum, TreeNode child) {
    // Unlink the old child
    if (children[childnum] != null)
      children[childnum].parent = null;
    // Insert the child
    children[childnum] = child;
    // Update the child's paternity
    child.parent = this;
  } // setChild
  

• parent() is as simple as the other basic access methods.

  public TreeNode parent() {
    return this.parent();
  } //  parent()
  

• root() requires us to continue to use the parent link until we reach a node without a parent link.

  /**
     Return the root node of the tree that contains the current
     node.
     pre: The tree is cycle-free (no node is its own ancestor).
     post: The root node is returned.
   */
  public TreeNode root() {
    // Base case
    if (parent == null) return this;
    // Recursive case
    else return parent.root();
  } // root
  

An Alternate Interface

• Where should we go from here to improve our interface? As we did with lists, we might
  • Add a wrapper class so that we can more easily support some other operations (such as counting the number of elements in the tree).
  • Add a cursor or current element that we'll move around the tree.
  • Revise out iterators to better support the various traversal strategies.
• These are some of the choices Bailey makes.
• Again, we have some general design decisions.
  • Do we give users direct access to nodes? No, as it biases the implementation.
  • Do we allow underfined/null children? It may be hard not to, however, we may also need to change our tree node implementation to permit underfined or null children.
  • Do we allow loops in the trees? Probably not, since we won't be giving the user explicit access to tree nodes.
  • Do we allow deletion of the current node? If so, what does such deletion mean? Delete the subtree rooted at this node? Delete this node and move everything else up? We'll allow deletion of subtrees.
  • Do we have an explicit setArity() function, or do we use setChild() and removeChild() to change the arity? I'm in favor of an explicit setArity() function.
  • Do we want root-specific functions? It seems wasteful to have them, although we may want a setRoot(). I've decided not to have root-specific functions, and to make the others behave appropriately.
  • Do we allow the user to move the cursor off of the tree, like Bailey does? No.
• Here's a variant of Bailey's interface.
  • Tree() -- Create a new tree with no elements.
  • Tree(Object rootvalue) -- Create a new tree with a root element.
  • Object getContents() -- Get the contents of the current node, if there is one.
  • Object getArity() -- Get the arity of the current node, if there is one.
  • void reset() -- Move the cursor to the root of the tree.
  • void down(int childnum) -- Move the cursor down to one of the subtrees, given that the subtree exists.
  • void up() -- Move the cursor up in the tree.
  • void setChild(int childnum, Object value) -- Set one of the children of the current node to a new leaf with the given value.
  • void setContents(Object value) -- Set the contents of the current node to the given value. If the tree is empty, sets the value of the root node to the given value.
  • void setArity(int arity) -- Set the arity of the current node.
  • void removeChild(int childnum) -- Remove one of the children of a node. Note that this is different than setChild(childnum,null), which creates a child with value null.
• We haven't yet considered all the reasonable preconditions and exceptions we might throw, but will do so in the implementation.
• We might also want to provide mechanisms that allow programmers to test whether each operation is reasonable. However, we could also throw exceptions for any illegal operations, which is more in keeping with the Java error checking strategy.
  • boolean isEmpty() -- Test whether or not the tree is empty. Test before reset(), setChild(), and more.
  • boolean hasParent() -- Test whether the current node has a parent node. Test before calling up().
  • boolean hasChild(int childnum) -- Test whether the current node has a particular child. Test before calling down(childnum).