Data Structure Trees

Trees

Recall one of the tree definitions given in class: 

     
enum ABTree_Tag {IS_LEAF, IS_NODE};
     struct ABTree {
        enum ABTree_Tag  tag;
        union {
           int  leaf;
           struct {
              struct ABTree *  left;
              struct ABTree *  right;
           } node;
        } elt;
     };
     typedef  struct ABTree *  BTree;

This is for binary trees of integers, where the data are only at the leaves.
Exercise

  1. Write the constructor, predicate, and selector functions.

  2. Write code using the constructors to create one specific tree: 

               / \
              3  /\
                /\ 9
               2  7

  3. Write a function which returns the sum of the leaves of an arbitrary value of type BTree.

  4. Combine these pieces into a program to compute and print the sum of the example tree.

  5. If you have time, write a function which prints an arbitrary value of type BTree, and add this to your program. The output format should group subtrees, e.g., by parentheses, to indicate the structure. Nice indententation for a visually attractive output is not necessary, because that is somewhat difficult.

  6. If you have time, free all malloc-ed data.

Solutions Here

A Part Of Thiyagaraaj Websites
Comments