CSE 321 Homework 6

1. Read the description of the Tree component (from Volume 2 of Software Component Engineering with Resolve/C++).
   
   
2. The height of a Tree t can be defined just like the height of a Binary_Tree, i.e., the number of items on the longest path from the root to some leaf. Here is a formal definition:

       math definition HEIGHT (
               t: tree of Item
           ): integer satisfies
           there exists x: Item, str: string of tree of Item
               (t = compose (x, str)  and
                HEIGHT (t) = 1 + STRING_HEIGHT (str))
   
       math definition STRING_HEIGHT (
               str: string of tree of Item
           ): integer satisfies
           if str = empty_string
           then STRING_HEIGHT (str) = 0
           else there exists t: tree of Item,
                             rest: string of tree of Item
                    (str = <t> * rest  and
                     STRING_HEIGHT (str) =
                         max (HEIGHT (t), STRING_HEIGHT (rest)))
   

   Please take some time to read and understand these math definitions. See if you can recognize why the intuitive, informal definition of the height of a tree matches the formal definition. This is a typical definition on mathematical trees, and you will see many more throughout the rest of the quarter. It is really important that you learn to understand such definitions.

   Then, provide an implementation for the following global function.

    global_function Integer Height (
            preserves Tree_Of_Item& t
        );
    /*!
        ensures
            Height = HEIGHT (t)
    !*/

3. Implement the following global function that returns the largest integer in a given tree:

       global_function Integer Max (
               preserves Tree_Of_Integer& t
           );
       /*!
           ensures
               Max = [the largest integer in t]
       !*/