Laboratory: Binary Trees

Preparation for lab:

• Review lecture topics on binary trees.

The program below builds a sorted binary tree. Each node holds an integer value. This tree can be used to test your solutions today. The tree is shown on the right.

#include <stdio.h>
#include <stdlib.h>

typedef struct BTree {
    int value;
    struct BTree *left, *right;
} BTree;

BTree *insert(BTree *root, int value) {
    if (root == NULL) {
        BTree *new_node = (BTree*) malloc(sizeof(BTree));
        new_node->value = value;
        new_node->left = new_node->right = NULL;
        return new_node;
    }
    if (value < root->value) {        /* insert left */
        root->left = insert(root->left, value);
    }
    else if (value > root->value) {   /* insert right */
        root->right = insert(root->right, value);
    }
    else {
        /* already in the tree */
    }
    return root;
}


int main(void) {
    int sample[] = {15, 96, 34, 12, 14, 56, 21, 11, 10, 9, 78, 43, 0};
    BTree *root = NULL;
    int i;
    for (i = 0; sample[i] > 0; i++)
        root = insert(root, sample[i]);

    /* Call your functions here! */

    return 0;
}

Write a function that traverses the tree in order (left-root-right), and prints the values. You should see the numbers in growing order.

Write a function to destroy the tree, and call it when necessary from main() to prevent memory leak. This function is recursive, as well.

Write a function that counts and returns the number of nodes in the tree. Check the result.

Write a function that returns the sum of the stored values. Check the result.

Write a function that finds a specific value in the tree and returns a pointer to the found node! Returns NULL, if the value can not be found.

Write a function that negates (multiplies by –1) each value in a tree.

Search in the negated tree

Try to use the previous search function to locate elements in the negated tree (like –14). What happens? Why? How to modify the search function to handle the negated tree? (Print the tree, and/or draw the negated tree, it helps a lot.)

Santa Claus

Santa Claus has been involved in an accident: his sleigh has hit a binary tree and all his presents have been distributed on the "branches" (nodes) of the tree. Santa must climb the tree and gather all the presents into the root node. Each node contains an integer number: the number of presents at that node. Write a function that sums up all values in the tree and returns this sum while setting the numbers stored in the nodes to zero (the presents have been collected). Collect the sum in the root node.

List or tree?

A binary tree stores integer values. Define the necessary C data structure. Write a function that, can tell whether the tree is a list, or not. See the trees below that are indeed lists. Return a logical value: true for a list. Write a short program that builds a tree and demonstrates the usage of this function.

    o      or      o        or        o
   /                \                /
  o                  o              o
 /                    \              \
o                      o              o

Exactly two or zero children

A binary tree stores words of max. 50 letters. Define the necessary C data structure. Write a function that can decide whether each node in the tree has either 0 or 2 children. Return a logical value. Write a short program that builds a tree and demonstrates the usage of this function.

     o                                  o
    / \    true                        / \    false     
   /   \                              /   \
  o     o                            o     o
 / \   / \                          / \     \
o   o o   o                        o   o     o