Homework #6 – Tree

bitree.c

/*
 * bitree.c
 */
#include <stdlib.h>
#include <string.h>

#include "bitree.h"

void bitree_init(BiTree *tree, void(*destroy)(void *data)) {

    /* Initialize the binary tree. */
    tree->size = 0;
    tree->destroy = destroy;
    tree->root = NULL;
}

void bitree_destroy(BiTree *tree) {

    /* Remove all the nodes from the tree. */
    bitree_rem_left(tree, NULL);

    /* No operations are allowed now, but clear the structure as a
     * precaution. */
    memset(tree, 0, sizeof(BiTree));
}

int bitree_ins_left(BiTree *tree, BiTreeNode *node, const void *data) {

    BiTreeNode *new_node, **position;

    /* Determine where to insert the node. */

    if (node == NULL) {

        /* Allow insertion at the root only in an empty tree. */
        if (bitree_size(tree) > 0)
            return -1;

        position = &tree->root;
    }
    else {

        /* Normally allow insertion only at the end of a branch. */
        if (bitree_left(node) != NULL)
            return -1;

        position = &node->left;
    }

    /* Allocate storage for the node. */
    if ((new_node = (BiTreeNode *) malloc(sizeof(BiTreeNode))) == NULL)
        return -1;

    /* Insert the node into the tree. */
    new_node->data = (void *) data;
    new_node->left = NULL;
    new_node->right = NULL;
    *position = new_node;

    /* Adjust the size of the tree to account for the inserted node. */
    tree->size++;

    return 0;
}

int bitree_ins_right(BiTree *tree, BiTreeNode *node, const void *data) {

    BiTreeNode *new_node, **position;

    /* Determine where to insert the node. */
    if (node == NULL) {

        /* Allow insertion at the root only in an empty tree. */
        if (bitree_size(tree) > 0)
            return -1;

        position = &tree->root;
    }
    else {

        /* Normally allow insertion only at the end of a branch. */
        if (bitree_right(node) != NULL)
            return -1;

        position = &node->right;
    }

    /* Allocate storage for the node. */
    if ((new_node = (BiTreeNode *) malloc(sizeof(BiTreeNode))) == NULL)
        return -1;

    /* Insert the node into the tree. */
    new_node->data = (void *) data;
    new_node->left = NULL;
    new_node->right = NULL;
    *position = new_node;

    /* Adjust the size of the tree to account for the inserted node. */
    tree->size++;

    return 0;
}

void bitree_rem_left(BiTree *tree, BiTreeNode *node) {

    BiTreeNode **position;

    /* Do not allow removal from an empty tree. */
    if (bitree_size(tree) == 0)
        return;

    /* Determine where to remove nodes. */
    if (node == NULL)
        position = &tree->root;
    else
        position = &node->left;

    /* Remove the nodes. */
    if (*position != NULL) {

        bitree_rem_left(tree, *position);
        bitree_rem_right(tree, *position);

        if (tree->destroy != NULL) {

            /* Call a user-defined function to free dynamically allocated
             * data. */
            tree->destroy((*position)->data);
        }

        free(*position);
        *position = NULL;

        /* Adjust the size of the tree to account for the removed node. */
        tree->size--;
    }
}

void bitree_rem_right(BiTree *tree, BiTreeNode *node) {

    BiTreeNode **position;

    /* Do not allow removal from an empty tree. */
    if (bitree_size(tree) == 0)
        return;

    /* Determine where to remove nodes. */
    if (node == NULL)
        position = &tree->root;
    else
        position = &node->right;

    /* Remove the nodes. */
    if (*position != NULL) {

        bitree_rem_left(tree, *position);
        bitree_rem_right(tree, *position);

        if (tree->destroy != NULL) {

            /* Call a user-defined function to free dynamically allocated
             * data. */
            tree->destroy((*position)->data);
        }

        free(*position);
        *position = NULL;

        /* Adjust the size of the tree to account for the removed node. */
        tree->size--;
    }
}

int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void *data) {

    /* Initialize the merged tree. */
    bitree_init(merge, left->destroy);

    /* Insert the data for the root node of the merged tree. */
    if (bitree_ins_left(merge, NULL, data) != 0) {

        bitree_destroy(merge);
        return -1;
    }

    /* Merge the two binary trees into a single binary tree. */
    bitree_root(merge)->left = bitree_root(left);
    bitree_root(merge)->right = bitree_root(right);

    /* Adjust the size of the new binary tree. */
    merge->size = merge->size + bitree_size(left) + bitree_size(right);

    /* Do not let the original trees access the merged nodes. */
    left->root = NULL;
    left->size = 0;
    right->root = NULL;
    right->size = 0;

    return 0;
}

bitree.h

/*
 * bitree.h
 */
#ifndef BITREE_H
#define BITREE_H

#include <stdlib.h>

/* Define a structure for binary tree nodes. */
typedef struct BiTreeNode_ {

    void *data;
    struct BiTreeNode_ *left;
    struct BiTreeNode_ *right;

} BiTreeNode;

/* Define a structure for binary trees. */
typedef struct BiTree_ {

    int size;

    int (*compare)(const void *key1, const void *key2);
    void (*destroy)(void *data);

    BiTreeNode *root;

} BiTree;

/* Public Interface */
void bitree_init(BiTree *tree, void(*destroy)(void *data));

void bitree_destroy(BiTree *tree);

int bitree_ins_left(BiTree *tree, BiTreeNode *node, const void *data);

int bitree_ins_right(BiTree *tree, BiTreeNode *node, const void *data);

void bitree_rem_left(BiTree *tree, BiTreeNode *node);

void bitree_rem_right(BiTree *tree, BiTreeNode *node);

int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void *data);

#define bitree_size(tree) ((tree)->size)

#define bitree_root(tree) ((tree)->root)

#define bitree_is_eob(node) ((node) == NULL)

#define bitree_is_leaf(node) ((node)->left == NULL && (node)->right == NULL)

#define bitree_data(node) ((node)->data)

#define bitree_left(node) ((node)->left)

#define bitree_right(node) ((node)->right)

#endif

hw6.c

#include <stdbool.h>
#include <assert.h>
#include <stdio.h>
#include "bitree.h"

#define max(a,b) ((a) > (b) ? (a) : (b))

#define bitree_ins_root(tree, data) bitree_ins_left(tree, NULL, data)

static void count_leaves_rec(const BiTreeNode* node, int* count)
{
	if (bitree_is_leaf(node))
	{
		++(*count);
	}
	else
	{
		if (bitree_left(node))
		{
			count_leaves_rec(bitree_left(node), count);
		}

		if (bitree_right(node))
		{
			count_leaves_rec(bitree_right(node), count);
		}
	}
}

int count_leaves(const BiTree* this)
{
	int count = 0;

	count_leaves_rec(bitree_root(this), &count);
	return count;
}

static void count_non_leaves_rec(const BiTreeNode* node, int* count)
{
	if (bitree_is_leaf(node))
	{
		return;
	}
	else
	{
		++(*count);

		if (bitree_left(node))
		{
			count_non_leaves_rec(bitree_left(node), count);
		}

		if (bitree_right(node))
		{
			count_non_leaves_rec(bitree_right(node), count);
		}
	}
}

int count_non_leaves(const BiTree* this)
{
	int count = 0;

	count_non_leaves_rec(bitree_root(this), &count);
	return count;
}

static int get_height_rec(const BiTreeNode* node, int depth)
{
	if (bitree_is_leaf(node))
	{
		return depth;
	}
	else
	{
		++depth;
		const int  left = bitree_left(node)
		                ? get_height_rec(bitree_left(node),   depth)
		                : depth;

		const int right = bitree_right(node)
		                ? get_height_rec(bitree_right(node), depth)
		                : depth;

		return max(left, right);
	}
}

int get_height(const BiTree* tree)
{
	return bitree_root(tree) ? get_height_rec(bitree_root(tree), 1) : 0;
}

int print_pre_order_rec(const BiTreeNode* node, int (*print)(const void *data))
{
	// Display the data part of root element (or current element)
	int count = print(bitree_data(node));;

	// Traverse the left subtree by recursively calling the pre-order function.
	if (bitree_left(node))
	{
		count += print_pre_order_rec(bitree_left(node), print);
	}

	// Traverse the right subtree by recursively calling the pre-order function.
	if (bitree_right(node))
	{
		count += print_pre_order_rec(bitree_right(node), print);
	}

	return count;
}

int print_pre_order(const BiTree *tree, int (*print)(const void *data))
{
	return bitree_root(tree)
	     ? print_pre_order_rec(bitree_root(tree), print)
	     : 0;
}

int print_in_order_rec(const BiTreeNode* node, int (*print)(const void *data))
{
	int count = 0;

	// Traverse the left subtree by recursively calling the in-order function.
	if (bitree_left(node))
	{
		count += print_in_order_rec(bitree_left(node), print);
	}

	// Display the data part of root element (or current element)
	count += print(bitree_data(node));;

	// Traverse the right subtree by recursively calling the in-order function.
	if (bitree_right(node))
	{
		count += print_in_order_rec(bitree_right(node), print);
	}

	return count;
}

int print_in_order(const BiTree *tree, int (*print)(const void *data))
{
	return bitree_root(tree)
	     ? print_in_order_rec(bitree_root(tree), print)
	     : 0;
}

int print_post_order_rec(const BiTreeNode* node, int (*print)(const void *data))
{
	int count = 0;

	// Traverse the left subtree by recursively calling the in-order function.
	if (bitree_left(node))
	{
		count += print_post_order_rec(bitree_left(node), print);
	}

	// Traverse the right subtree by recursively calling the in-order function.
	if (bitree_right(node))
	{
		count += print_post_order_rec(bitree_right(node), print);
	}

	// Display the data part of root element (or current element)
	count += print(bitree_data(node));;

	return count;
}

int print_post_order(const BiTree *tree, int (*print)(const void *data))
{
	return bitree_root(tree)
	     ? print_post_order_rec(bitree_root(tree), print)
	     : 0;
}

static void destroy(void*data)
{
	(void)data;
}

static int print(const void *data)
{
	return printf("[%i]", *(int*)data);
}

bool bitree_fill_1(BiTree* tree, int* iterator)
{
	assert(bitree_ins_root(tree,                                          iterator++) == 0);
	assert(bitree_ins_left(tree,  bitree_root(tree),                      iterator++) == 0);
	assert(bitree_ins_right(tree, bitree_root(tree),                      iterator++) == 0);
	assert(bitree_ins_left(tree,  bitree_root(tree)->left,                iterator++) == 0);
	assert(bitree_ins_left(tree,  bitree_root(tree)->right,               iterator++) == 0);
	assert(bitree_ins_right(tree, bitree_root(tree)->right,               iterator++) == 0);
	assert(bitree_ins_left(tree,  bitree_root(tree)->left->left,          iterator++) == 0);
	assert(bitree_ins_right(tree, bitree_root(tree)->right->right,        iterator++) == 0);
	assert(bitree_ins_right(tree, bitree_root(tree)->right->right->right, iterator)   == 0);
	return true;
}

bool bitree_fill_2(BiTree* tree, int* iterator)
{
	assert(bitree_ins_root(tree,                                 iterator++) == 0); // 6
	assert(bitree_ins_left(tree,  bitree_root(tree),             iterator++) == 0); // 4
	assert(bitree_ins_left(tree,  bitree_root(tree)->left,       iterator++) == 0); // 2
	assert(bitree_ins_right(tree, bitree_root(tree)->left,       iterator++) == 0); // 5
	assert(bitree_ins_left(tree,  bitree_root(tree)->left->left, iterator++) == 0); // 1
	assert(bitree_ins_right(tree, bitree_root(tree)->left->left, iterator++) == 0); // 3
	assert(bitree_ins_right(tree, bitree_root(tree),             iterator++) == 0); // 8
	assert(bitree_ins_left(tree,  bitree_root(tree)->right,      iterator++) == 0); // 7
	assert(bitree_ins_right(tree, bitree_root(tree)->right,      iterator)   == 0); // 9
	return true;
}

void remove_leaves_rec(BiTree* tree, BiTreeNode* node)
{
	if (bitree_left(node))
	{
		if (bitree_is_leaf(bitree_left(node)))
		{
			bitree_rem_left(tree, node);
		}
		else
		{
			remove_leaves_rec(tree, bitree_left(node));
		}
	}

	if (bitree_right(node))
	{
		if (bitree_is_leaf(bitree_right(node)))
		{
			bitree_rem_right(tree, node);
		}
		else
		{
			remove_leaves_rec(tree, bitree_right(node));
		}
	}
}

void remove_leaves(BiTree* tree)
{
	if (bitree_root(tree))
	{
		if (bitree_is_leaf(bitree_root(tree)))
		{
			bitree_rem_left(tree, NULL);
		}
		else
		{
			remove_leaves_rec(tree, bitree_root(tree));
		}
	}
}


int main(int argc, char const *argv[])
{
	// --------------------------------------------------------------------
	// Tree 1
	// --------------------------------------------------------------------
	{
		int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
		BiTree* tree = alloca(sizeof(*tree));

		bitree_init(tree, destroy);
		assert(bitree_fill_1(tree, data) == true);
		assert(count_leaves(tree) == 3);
		assert(count_non_leaves(tree) == 6);
 		assert(get_height(tree) == 5);

 		printf("pre: ");  print_pre_order(tree,  print); printf("\n");
 		printf("in: ");   print_in_order(tree,   print); printf("\n");
 		printf("post: "); print_post_order(tree, print); printf("\n");

 		printf("before: "); print_in_order(tree,   print); printf("\n");
 		remove_leaves(tree);
		assert(count_leaves(tree) == 2);
 		printf("after:  "); print_in_order(tree,   print); printf("\n");
		bitree_destroy(tree);
	}

	// --------------------------------------------------------------------
	// Tree 2
	// --------------------------------------------------------------------
	{
		int data[] = {6, 4, 2, 5, 1, 3, 8, 7, 9};
		BiTree* tree = alloca(sizeof(*tree));

		bitree_init(tree, destroy);
		assert(bitree_fill_2(tree, data) == true);
		assert(count_leaves(tree) == 5);
		assert(count_non_leaves(tree) == 4);
 		assert(get_height(tree) == 4);

 		printf("pre: ");  print_pre_order(tree,  print); printf("\n");
 		printf("in: ");   print_in_order(tree,   print); printf("\n");
 		printf("post: "); print_post_order(tree, print); printf("\n");

 		printf("before: "); print_in_order(tree,   print); printf("\n");
 		remove_leaves(tree);
		assert(count_leaves(tree) == 2);
 		printf("after:  "); print_in_order(tree,   print); printf("\n");
		bitree_destroy(tree);
	}
	return EXIT_SUCCESS;
}

hw6.pdf