CPS 100 -- Fall 1995

Group Assignment: Trees

Assume the following declarations have been made 
    struct Tree
    {
       int info;
       Tree * left,* right;
       Tree(int val, Tree * lbranch = 0, Tree * rbranch = 0);
    };
    Tree::Tree(int val, Tree * lbranch, Tree * rbranch)
    {
        info = val;
        left = lbranch;
        right = rbranch;
    }
The following function returns the height of a tree. 
    int TreeHeight(Tree * t)
    // postcondition: returns height of tree with root t
    {
        if (t == 0)
        {
            return 0;
        }
        else
        {
            return 1 + Max(TreeHeight(t->left),TreeHeight(t->right));
        }
    }
where the function 
 Max
returns the largest of its two integer parameters.
Problem 1 Write a function NonLeafCount that has a single parameter of type Tree * and that returns the number of non-leaf nodes in the tree whose root is pointed to by the parameter. You may find it useful to write a boolean-valued function IsLeaf.

Problem 2

Write a function Tree2List that converts a binary search tree into a sorted linked list. You may find it useful to write auxiliary function(s) called by Tree2List . 

    Node * Tree2List(Tree * t)
    // precondition: t is the root of a binary search tree
    // postcondition: returns a pointer to the first node of a
    //                sorted linked list containing same values as t