Exercise Sheet 10: Arboriculture

1. The file BintreeLinked.java contains code for the methods BintreeLinked, isEmpty, isExternal, isLeaf and initialise for a linked implementation of Bintree with null references representing empty nodes. The corresponding windows should be defined as specified in the DAT Notes:

     public class TreeWindow {
       TreeCell parentnode;
       int childnum;
   
       public TreeWindow () {}
     }
          

   The aim of this practical is to complete the ADT. This will be done in a number of stages (of roughly increasing difficulty). After each stage you should test the ADT operations that you have written to check that they work as expected.

   1. Add code for the examine and insert methods. (These methods were covered in exercises in the lectures.)

   2. Add code for the methods isRoot, child, and replace. (Note that isRoot returns false in the case of an empty tree.)

   3. The following tree is used in the DAT Notes to illustrate traversal techniques:

                 +
               /   \
             *       -
            / \     / \
           +   3   *   6
          / \     /\
         1   2   4  5
      

      Build this tree using your ADT.

   4. Implement the delete method.

   5. Write (private) recursive methods for performing preorder, postorder and inorder depth-first search. The methods should return true if the item being sought is contained in the tree. (You may use as many methods as you wish - it is not required that you use a single method for each traversal.)

      Add a print statement to your code so that the values at the nodes are printed as the nodes are visited. Check that the expressions generated match those given in the Notes for the various traversals.

   6. Challenge: Modify one of the above methods so that it can be used to implement the parent method, and provide an implementation of parent. Are any of the depth-first traversals better than the others for this technique?